is that from the new Justice League movie?

Then, you should solve all the problems within 15 minutes to watch second half of the match fully. :D :D

I think for koreans is very possible xd

Corrected, thank you!

Fixed, thanks!

skip .. skip hard hard

bey

The captions may be reversed. :P

Is that from the Iran-Spain match? That nutmeg/tunnel? Never have seen PIQE wondering like that... LOL

"rated for the participants with rating lower than 2100"

Copied from the blog!!! Please read carefully!!

If you continue to post this sort of stuff then soon your absolute value of contribution will be highest lol.

I think " NNSU " stands for " Nizhny Novgorod State University " , There was a programming contest there this year. I THINK

Do you know Gods of Death love apples.

Me too, ABCDE looks too easy, and F is much harder than E.

did b,c,d,e wa at a twice. please explain A

I understood DP with bitmask solution of problem E. But your solution had less time complexity. Could you please explain your solution?

anant_k_singh

Yes, it is not very difficult, so it is only 1500 points comparing to standard 2000.

987654320023456789

I think it is 100

Exactly Bro.Though I wasted a lot of time proving that C can be done by Binary Search within the time limit.

Binary Search for the answer

Binary search over k. Validate using a simple loop. 1e18 will take ~300 iterations of multiplying by 0.9 to reach 1.

Actually I have a Messi t-shirt :)

Binary search is log. Check in bs: if at some step there are k candies, at next step it will be less then 0.9k. So check takes <= log(n) base 10/9 steps. Overall complexity is O(log^2).

On day d, Vasya will have ((9/10)^{d-1})*n — k(1 + (9/10) + (9/10)^2 ... d times) = ((9/10)^{d-1})*n — 10*k(1 — (9/10)^d) candies. Make this 0 and solve for d, we see that d is logarithmic in n. So we can use binary search.

Even if we assume that only 10% candies will be eaten each day(90% will be left next day), and Vasya does not eat any candy on any day, (10/9)^r * n <= 1 ( Assuming after r days candies left<=1 ) we need to find r, put n = 10^18(for worst case), you get maximum days (r = no. of days candies will last), which is <=500. So in binary search, this bruteforce takes <= 500 computations, so Overall it takes c*500*log(10^18) computations using binary search on k..

Suppose k was 0 (it's obviously the worst case).

Each day, we have n decreasing by 10%, i.e, it becomes . So after m days, it's . For n = 10¹⁸, something like m = 400 will bring this value down to below 10 — actually something a bit less, like m = 380 works.

Having a higher k will simple accelerate this.

Final complexity is O(log(10¹⁸) * 380), which isn't really a problem.

in every iteration either

which converges giving

987654320023456789

Yes

no it doesn't. At least my sol passed without it

My greedy passed pretests, so maybe not?

I solved without DP. Normal implementation.

I guess greedy will work just fine. Cause length of square is just 2. So greedy will work perfectly fine.

Actually no need in floats for B. You just check that 2 * sum >= 9 * n.

2846161151=7*9^9+8^9

Yeah EXACTLY...

It's simple binary search. Nothing mathematical.

It won't take much time if you code in python... LOL

My code was quite short. Maybe because of the nifty macros http://mirror.codeforces.com/contest/991/submission/39568678

c++ be like

It does not have long code time, I did it in less than half an hour, and I'm not even a very good programmer.

Read about recursive backtracking. It's a very useful technique when generating permutations or generating subsets of a set.

I would suggest using competitive programming 3 (by Steven and Felix halim), chapter on programming paradigms, complete search. It also has exercises at the end of the section for each topic.

That being said, in this problem, you only had to generate subsets, number permutations of one subset can be calculated using a combinatorics formula. (Check out my solution)

1000000000000000000

I was getting WA6, then added additional check for ans — 1, ans + 1, cuz binary search can give a wrong answer sometimes (well if implemented badly).

You'd better take a look on the problemset than a contest... There are many good problems specially in sgu problems.

Secondly, this nowhere looks like a Div2 standard contest.

How do you mean ?

No, the greedy approach works. Your solution is correct

Let's assume that K is our optimal answer.

We can prove that K+1 would hold good to get more than N/2 candies.
Similarly, we can prove that 1,2,....,K-1 won't hold good. So it's like shifted unit step function (considering >=0 part only) if you observe carefully. And I guess, we can run binary search to find the starting point of that step.

The amount of chocolates he collected at each turn monotonically decreases.Now, when vasya increases the value of k the rate of vasya collecting chocolates at each turn further reduces. Finally, total chocolates collected by petya in the end for a given n decreases with increase in k. Thus, chocolates collected by Vasya is also monotonic.This was my way to convince myself with a logical inference.

I think it helps to look at it from Petya's perspective — there's still just one hole which I can't fill in though.

Suppose, eating k candies daily, Vasya cannot reach , and the process takes d days. The candies Peyta gets are With k - 1, he gets

Basically, with Vasya eating k - 1 each day, and taking into account that we're flooring, Petya gets at least as many as he does as when Vasya eats k daily. Now, if with k - 1 the process takes  ≤ d days, Vasya has less candies than he first did, so certainly not . If it takes  > d days, Petya has at least as many on each day as he had previously, so he ends up with at least as many as he had previously, which means Vasya can't have anyway.

The only irregularity here is the last 9 candies — and even that disappears once d is high enough ( ≥ 9). Probably, that case can be worked out separately or something. Or maybe my logic can be modified a bit to take care of that, I'm just not seeing it.

Edit: Small mistake in the numbers, fixed now.

the bus's number must have full type of digits in N

2 lines, 100 randomly generated 0 and X each

C required binary search idea. I don't think it's that obvious to beginners.

I don't quite know how to do D, E and F :)