()

Is it rated?

Yep,but for me it is a right time to have supper,so maybe I'll be hungry solving the problems.

Even I'm Chinese, I still want the round to be later. The darkness has given me dark eyes, but I use them to find bugs.

Thanks to the time,I can participate for an official contest after a long period of time.

Thanks to the contest writers.

You can simply just open the "Complete Problemset" page!

you too

The solution is max{N, 2 * (N — positionOfTheFirstStaircase), 2 * (positionOfTheLastStaircase + 1)}

I used BFS and start point is (floor,room)=(0,0)(0,s.size()-1)(1,0)(1,s.size()-1)

there are only two possible cases either you start from leftmost room and use rightmost stair or start from rightmost room and use leftmost stair. ans is maximum of these two cases.

:(

I can totally feel you bro... i wrote a solution which worked for 10^6 test cases that I randomly generated using Chelper and my code passed without any error, but this case 5 totally took my life.

try this if you use exgcd approach:

1000000000000 90000000000000007 100000 77777

Answer should be

899999922230 99991 99999977779

My exgcd template failed on this because of long long overflow when multiplying

If you really want to solve that equation, maybe you could try something like this:

The goal is to find the smallest possible $$$y$$$ such that $$$wx+dy=p$$$.

We could first divide both $$$w$$$, $$$d$$$ and $$$p$$$ by $$$gcd(w, d)$$$ then $$$w$$$ and $$$d$$$ become coprimes.

We take $$$mod\ w$$$ and the equation becomes something like $$$dy=p \ (mod\ w)$$$. Thus $$$y=p\times {d}^{-1}\ (mod\ w)$$$.

For coprimes, modular inverse always exists and could be found by extended euclidean algorithm.

first check if the (p % (gcd of(w,d) != 0) then the answer -1.

then you should know the min number of draw matches you need cuz of (d<w) and more number of winning matches.

so you should precalculate this : Mod[ (i*d) % w ] = min ( Mod[ (i*d) % w ] , i ) for each (0 <= i <= w-1) calculate def=(p%w) and now you know the min number of draw matches you need to achieve ( def = (Mod[def] * d) % w )

the number of draw matches is Mod[def] and the number of winning matches is ( ( p — (Mod[def]*d) ) / w ) just make sure the sum of them less or equal to n then print them

Diophantine equations i guess.

I have tried the diophantine equation but no luck. What a bad problem for C..

I tried to solve it using extended GCD algorithm. This helps you to find (x, y) such what:

wx + dy = p, though after finding a initial value of (x, y) you need to somehow convert it into a valid solution (Here is where I got totally stuck)

You can use extended Euclidean algorithm to find x and y(keep in mind there can be more than one solution to the linear combination, so you need to take the one where y is minimal while still being >= 0).

brute force would work cuz small contraints on w or d

binary search and binary search and more binary search... no number theory no nothing only binary search... at least that's how I did it

https://codeforces.net/blog/entry/70516?#comment-549838

After contest, I solve F and G by myself, so C is the hardest for me...

We ca use Binary Search to find minimum difference, The Min. element or Max. element in the final array after applying operations will be from the original array.

I guess, E is ternary search within binary search.

i solved it greedy

increase / decrease elements which frequency is less to the next element

I solved it by greedy.I hope it passes the main system cases too!

We also need 30 more minutes to submit more problems :)

so is the system testing delayed by 30 minutes or it'll start normally?

We can employ brute force. Iterate over all possible numbers of draws from zero to $$$W-1$$$. We can easily compute the number of wins necessary with a given number of draws and whether this configuration is possible (this requires that $$$P = Di$$$ mod $$$W$$$, where $$$i$$$ is the number of draws, and that $$$(P - Di) / W + D$$$ is at most $$$N$$$, since we need to have an integer number of wins and can have at most $$$N$$$ wins and draws). As soon as we find a working configuration, just print it and exit.

We now prove that this is optimal--in other words, this will find a solution if one exists. Note that if there exists a solution $$$(x, y, z)$$$ with $$$y \geq W$$$, $$$(x+D, y-W, z)$$$ is also a valid solution. Moreover, the total number of wins and draws in the second solution is lower than in the first, meaning the second solution is more likely to fit within our $$$N$$$ game limit. Thus, any optimal solution will have $$$0 \leq y < W$$$, as desired, so our solution will find a solution if one exists.

the z is variable, u should just minimize y due to w > d (it should be correct, but i had wa5 too :(

find solution with minimum x+y such that x,y >= 0.

It is the core part of my submission code with some comment. due to overflow issue, you should use python.

if n-(x+y)<0:

//n-(x+t*d/g + y-t*w/g) >= 0

//n >= (x+y)+t(d-w)/g

//(n-(x+y))*g/(d-w) <= t (inversed ineq because d-w<0)

t=(n-(x+y))*g//(d-w) + (0 if (n-(x+y))*g%(d-w)==0 else 1);

x+=t*d//g;

y-=t*w//g;

I have an solution: the problem can become this: xa+yb=c (a&b&c are known)

And make y+x as minimum as possible (z = n-x-y)

to achieve this we must let y as small as possible (since a>b) ,so (c-yb)%a=0

because y must <a so try all the y,the smallest is the answer.

Yes it troubles many people!

First, the answer is $$$-1$$$ unless the tree is a line (i.e. all vertices have degree $$$2$$$, except for two, which have degree $$$1$$$). Proof: suppose vertex $$$A$$$ is connected to vertices $$$B, C,$$$ and $$$D$$$. By considering the paths $$$B-A-C$$$, $$$C-A-D$$$, and $$$D-A-B$$$, we see that all four of these vertices must have different colors, but with only three colors, this is impossible.

If the tree is a line, then there are six possible configurations, each of which results from fixing the colors of one of the endpoints and the vertex adjacent to it. We can simply brute-force all six configurations and print the best one.

The tree has to be a straight line to have any solution, since if it has more than 2 degree it can't be satisfied with 3 colors. After that the color has only 6 possibility: $$$[1,2,3,1,2,3,..]$$$ $$$[2,3,1,2,3,1,..]$$$ .. and all other permutations of $$$(1,2,3)$$$ repeated

We employ a greedy approach. Start by sorting the data. Then, until we're out of moves and in increasing order of $$$i$$$, increase elements $$$0$$$ through $$$i$$$ to the value of element $$$i+1$$$ and decrease elements $$$N-1$$$ through $$$N-1-i$$$ to the value of element $$$N-2-i$$$.

On our first iteration our answer decreases by one with each of our moves (since we are increasing/decreasing the minimum/maximum with every move), on our second iteration our answer decreases by one after every other move (since we need to increase the lowest two elements now each time we want to raise the minimum, and similarly for the maximum), and so on. It's relatively easy to see that we can't do any better, since at each step we're choosing the most efficient possible way of closing the gap.

I tried Binary Search for y inside a binary search for x .. i got a WA on test 4 :\

Observation: If there is a node with more than/equal to three edges, whatever you paint you will get a path of three nodes with "only two" colours. So any valid painting must be a list/degenerate tree. The colour pattern must be a sequence of "RGB"/"RBG"/...

tree is a line if not answer = -1. After that you calculate all case and chose a best case =))

For number theory solution, one may need to solve a diophantine equation $$$xw + yd = p$$$. Take mod and we have $$$yd=p$$$ mod $$$w$$$. This "small" constraints enable brute force solving but not taking modular inverse.

That will not work.

tyr out this one 30 60 9 4 one of the answer would be 4 6 20

I don't like this round

??

+1. DEF are all at same level.

I think you misread E. E was not easy

$$$Y$$$ can be at most $$$w - 1$$$, if its more than $$$w$$$, then transform them to $$$d$$$ wins instead of $$$w$$$ draws.

the (p — d * i) % w will form a cycle and you just need to find the i that (p — d * i) % w equal to zero