Today I was running in the forest, did pull-ups on the tree branches, drank spring water from my hands, watched squirrel removing shell from a nut... but I had been interrupted by an alarm on my phone which reminded me of the contest =)

They can move div 1 contestant from div 2 registration to div 1 manually. "it's already done before" too.

Vs Wael.Al.Jamal

And vs EvenImage and vs dotorya, I think.

Eat fast like Major Payne.

Thank you, Cpt. Obvious. We would never have noticed that without you. You are truly the hero we need, although not the hero we deserve. /s

The condition for increasingness is "when xor-ing X with b_i such that the highest set bit of b_i is the d-th, the d-th bit of X must be 0". Therefore, we can group b_i-s by the highest set bit.

We can go from the highest to the lowest bit d and build the final sequence by merging everything with a given highest set bit with the sequence obtained in the previous step. We can't break that previous sequence this way and we only need to stuff the new b_i-s at the beginning / after each 1 as the d-th bit; whether this is possible doesn't depend on what we did before.

I've proved that it's always smaller than or equal to 5, or no solution exists.

There are two cases(excluding the trivial ones when you can go to n using a short simple path):

1) If the connected component of 1 in the original graph is not a complete graph, we can go 1->a->x->1->n, where x is not connected to 1 in original graph, but a is.

2) If connected component of 1 is a complete graph not a triangle, we can go 1->x->y->z->x->1, where all x, y, z are in a's component. EDIT : This is incorrect.

2 5 1 0 1

2

1

1 4 1 5

Now, I regret why my solution wasn't hacked so that I can check this case! My solution will be wrong now! :(

I am guessing it is: one's connected component is a triangle, not containing n. Answer is -1 then. BTW, Is the answer always <= 5?

I got WA on the same pretest. My solution was to do a DFS for paths of length no more than 3. If we are able to reach N than that is the solution. Otherwise if there is a path of length 2 from 1 to some other node X, then we can go from X to 1 (because the tunnel is now open) and then from 1 to N.

What is the flaw in this logic?

I treated the case correctly but forgot to add line separators :/

I also forgot the

if(r1==r2) {
    printf("%d\n", abs(c1-c2));
}

Yes, I did it that way, but I handled the binary search part by using Java's TreeSet (which internally is a red-black tree implementation). A special case is when the starting and the ending rooms are on the same floor — in that case you don't need any stairs, nor elevators. :)

we both are winning or losing together today.

yes if you consider a stair being an elevator with maximum speed 1

I have written a greedy solution which passed pretests:

chose larger x (from x1 and x2).

Try to assign them greedily from larger server size. Choose lower server till it works (v/2, v/3, v/4..).

Then do the same with remaining one.

if any one doesn't work, swap x1, x2. Repeat.

Edit: It failed on test 40. Not sure why. Take this solution with a grain of salt.

Edit2: Okay, Algorithm is 100% correct. My http://codeforces.me/contest/967/submission/37727934 was also correct for test40. I switched the order while printing the answer, Also it was last damn test case.

this is my Alg "not greedy"

https://ideone.com/kCGiVY

Sort the array elements in pairs(ar[i],i). Now assuming each array element of the sorted array s_ar[i] as the minimum element for two types of services separately, find j so that (j-i+1)*s_ar[i].first >= x1 and store in cal[i] for 1st type and similarly store for 2nd type in val[i] . Now check if there exists i<cal[i]<j<val[j] or i<val[i]<j<cal[j].

Yes (sadly)

It should be "Yes"

Дорешать можно практически любую задачу любого контеста на кф.

I think almost every CF contest have "pratice". But there is some time after the contest (approximately 30 minutes) when you can't submit your solutions

You know you solved it, right?

you solved it :)

Split queries in blocks of size k. For each block build compressed tree consisting of vertices that change in this block, their lcas and the root. For each edge in this compressed tree, store all balances for vertices on that edges in sorted order. When some vertex changes, change all its ancestors and for each edge on the path to root you need to add\subtract 1 from all balances on that edge. You need binary search for it so this solution works in . But you can get rid of it if you notice that you don't need to store balances with absolute value greater that k. Then it will work in . I had no time to implement this optimisation and got OK without it. Sadly I spent 40 minutes solving B, so I wrote E few minutes before the end and had no time to debug it.

Closest may not be optimal. You have to check closest on both sides of your current location.