# RTTR

## About

### Theory

Rounds will be held on the Vjudge Group.

After doing 100 rounds of these, you will get the Grandmaster on Codeforces. It is 100% guaranteed, trust me.

I'll try to do these often and post little hints and solutions afterwards.

## RTTR #1

Result:

Didn't solve the first problem because of a silly implementation mistake. (Granted I did overcomplicated a little).

Overall really great problems, highly recommend solving all of them.

### Fib-Tree

## Hint 1

For a given Fibonacci number, there is a single way of decomposing it into smaller Fibonacci numbers.

## Hint 2

For a given tree of fibonacci size, there are at most two ways of decomposing it into smaller trees of fibonacci size.

## Hint 2.1

It doesn't matter which of the ways you pick.

## Solution

- Create some function
`fibtree(v)`

which will return a bool if the tree that contains v is a Fib-Tree. - Root the tree in v and get all the subtree sizes.
- Iterate through the tree until you find someone with size \(F_{i-1}\) or \(F_{i-2}\).
- Remove the edge connecting that vertex to its parent.
- This is possible by making G a
`vector<set<int>>`

- This is possible by making G a
- When you get to a subtree of size at most 3, return true.

## Thoughts

- Really great problem, but it pretty easy to guess the solution without understanding why it works.
- I ended up using the trees' centroids, which wasn't too bad but unnecessary.
- Silly implementation mistake, was returning too eagerly in the
`get_need`

function.

### Are You Fired?

## Hint 1

If a solution with some length works. A solution with double that length also works.

## Hint 2

That means that there is a solution with length at least \(N/2+1\).

## Hint 3

That makes the case \(X > 0\) really easy.

## Hint 2.1

Just pick N. Check if that works.

## Solution

- We're down to the case \(X \leq 0\) and we know the length is at least \(N/2+1\).
- Document for each position from the first half how long the range starting at it can be.
- The length must be at least \(N/2+1\). As the range grows the sum decreases, so it is a prefix.
- Therefore we can binary search for that.
- To check if some length len works overall, check if all the indices where ranges would be starting can handle ranges that big.

## Thoughts

- Did this problem pretty quickly.
- Did the right choice of dividing it into cases and analysing.

### DeadLee

## Hint 1

Work with the concept of having "enough" of a given food. Count how many people want each food. You have enough of it if you have more of it than people want.

## Solution

- What can you do if you have enough of some food \(f\)?
- Give it to everyone who wants it, then remove these people.
- By "remove" I mean put them in the back of the order and make them "not want" the rest of the food.
- You can do that by keeping a
`vector<set<int>>`

with the people that want each food.

- If by removing people you now have enough of some other food, put that food on the queue and repeat the process.
- It is kinda like a BFS
- Implementation for reference

## Thoughts

- Really nice problem but also quite easy. Not sure why it is rated 2400.
- Once you create the concept of having "enough" of some food the solution flows pretty naturally.