Recent actions

They add all succesful hacks' cases to system tests in practice.

When would Solution of this problem be provided?

i guess on stronger tests but still people can hack you:)

-7

hmm, could be!

+22

I don't see any rating, i think you have some rating predictor extension installed.

-10

Why are they showing rating change on the right hand side??????!!!!!! its so sad that we cant get that!! its like they are teasing us!

Sorry I'm not sure. Let's check in this round.

Also can you please tell me that if I submit a solution now does it run on stronger test cases or the pretests from the edu round?

Ohh ok alright. I'll do that. Thanks!

+4

During hacking time, only hackers know the case. I think it is good to send message to the hacker.

Auto comment: topic has been updated by PikMike (previous revision, new revision, compare).

Created or updated the text

If our code is hacked then can we see the hack case? If so how?

what is hack test for D except this one :

3 2

4 10 25

Thanks PikMike :)

Why it should be slower? It's absolutely normal time for such amount of simple operations.

+1

In couple of hours

so have you figured out why is it so fast?

Nice! Sorry for the confusion, my solution got accepted on the normal tests so thought I was good. Guess I'll go with the N^3 DP. Initial logic is flawed on cases with separate twos and fives :D. Edited my comment. Thanks!

+2

When do we get editorials for this contest ?

+6

you can't say only 2-3 :v your rate is (77-55)/60s which is less than (2)/2s So I am ahead of you in observing this phenomenon 8-)

+7

Only 2-3? Sometimes before I saw uwi had +55 hacks .. Just after 1 minute I refreshed page and saw +77 :| Now it is +124+ \m/

+4

Do red coders use some kind of script for hacking or something?

One refresh in my status page shows 2-3 hacks by halyavin

(please tell me your secret :v )

When n = 3 and arr = [a, b, c], on m-th iteration we have third number in array equal to , so we can use binary search to find first m, for which this value is  ≥ k.

Max number is rightmost. It is just sum of elements using binomial coefficients. It comes from pascals triangle property what A[i, j]=A[i-1, j]+A[i, j-1].

Can D be solved faster than O(Cn^3), where C is log5(1e18)?

It can't work because you cannot count dp with only those informations. You don't know what is best pair. Maybe optimal solution is take one number power of two and next one power of 5.

How exactly the binary search part works?

+4

Hacked you with this case:

3 2
1024 1000 9765625
+20

A better bound than on the number of iterations is as in ever step gcd gets multiplied by some integer >= 2.

+5

UPD: The following is wrong. The solution is an N^3 DP.

I just tried the problem, did the following DP.

The first observation is that, for any point, the total number of zeroes = min(number of twos, number of fives).

Let twos[i] = number of twos in the number at the ith index, fives[i] = number of fives in the number at the ith index.

Declare dp[i][j] as a pair, dp[i][j].f = number of twos in our set, dp[i][j].s = number of fives in our set.

dp[i][j] = best subset we can make until index i with j numbers in our subset.

If min(dp[i — 1][j].f, dp[i — 1][j].s) > min(dp[i — 1][j — 1].f + twos[i], dp[i — 1][j — 1].s + fives[i]), dp[i][j] = dp[i-1][j].

Else, dp[i][j].f = dp[i — 1][j — 1].f + twos[i], dp[i][j].s = dp[i — 1][j — 1].s + fives[i].

Answer is min(dp[N][K].f, dp[N][K].s). Complexity is O(N^2).

+5

there's a 'G' at the end of the last row...because of that there are not three stripes of different colors to make a valid flag

+6

It has G in a row of R.

can you tell me why it is no for test#10?

3 100 BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB GGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGGG RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRG why answer is no for this test case??

We can do binary search every time if we succeed to calculate binomial coefficients :D

Any test with n = k = 200(test #21) should be the slowest for my code.

I think brute-force can solve F, for the answer won't be too large if n>3 (after removing leading zeros). When n=2 or n=3, we can use binary search. However, the overflow problem troubled me a lot, so I didn't complete this method during the contest :(

+2

Well, mostly I can agree with you, 20 minute penalty for any little bug, is a bit too huge, but on the other hand, it's EDUCATIONAL round, so scores doesn't really matter. Here the only goal is to improve, not to compete with others.

Hints for F?

Is it because they haven't included stronger test cases yet?

Hey, Can anyone tell me why my code failed in Test #15 of Problem B. Here's a link : My Solution

+10

I was enjoying this contest. Short description and interesting problems. :)

+5

Oh its F :D

+6

notice that gcd(a , b) always increases in this process , so for a particular value of b , find the max b' < b where gcd(a , b') > gcd(a, b) , this can be done in O(P) time where P is the number of distinct prime factors of a , and since number of distinct gcds are , total complexity is

OK, I had a bug.

I was thinking is the max number in array A^j is sum A[i]*binomial(j+n-i, n-i)? How to calculate binomials fast enought?

dp[i][j][L] = max number of 2 when choosing j numbers from the first i numbers, with a total of L 5's. L won't be larger than 5000 (5^26>10^18).

By the way, that's 200*200*5000=2*10^8 operations, why it works so fast(under 200ms)?

29170931

very nice problem indeed...I couldn't solve it during the contest..any hints???

+9

Problem E is so interesting and I think it's original problem, it would be better if it was used in rated contest (if it's indeed original)

It wasn't too slow, you got mle, so you just needed to keep the only last layer of dp.

+3

i did the same and my solution works under 100ms.

First: the number of trailing 0's is the minimum number of 2-factors or 5-factors.
So now we just have to pick a subset to maximize this minimum. I solved it via a knapsack with 2 states, the number of element in the subset, and the number of 5-factors.

+7

You can notice that the roundness is equal min(v1, v2) where v1 = number of 5 in a number, and v2 is number of 2 in a number. So just do dp[size_of_subset][number_of_5] = max_number_of_2.

is solution for D Dp state reduction?

How to solve D?

I did DP[i][k][s] — a maximal number of 2 in prefix [1..i] when we take k numbers and product of those numbers has s factors equal 5.

1 <= i,k <= n , 0 <= s <= 5000

It was too slow.

+4

How to solve D, I think it's dp but I can't find it. :'(

I have known how to solve E,but it's too late!

Still a minute to go.

+2

How to solve E?

+29

20 minutes penalty for wrong submit is too much for 2-hours contest, don't you think? What about decreasing this value for educational rounds?

maybe someone schedule for the time :)

maybe they focus on the problems not announcement :)

+19

why not?:)

I thought no one has noticed the delay because until 4 min ago there is no comment but it was delayed 10 min before original starting time

Hi first thx for preparing the contest But Why So delay?!

+5

delayed by 10 minutes

Thanks for your time, I get that but I submitted a code which goes until m and breaks when a correct solution is found. But I only check m/i and m/i+1, whereas for it to mathematically be correct, I have to check for i+1 and i as well, however I don't and it still works, what am I missing? Edit: This is my submission (28747357)

+1

We don't iterate from i = 1 to , instead it's up to . When you want to divide some ai into k sets, each set will be of size . Therefore or . Thus, it's possible to check every case by checking up to the root. Since on each iteration we iterate over our array of size n, the time complexity of the solution is

Could someone please explain this to me: In problem E, I used the solution to go from i to min in array a, and then check min/i and min/i + 1... I understand why and why we check these things ( for every element in a, x1 = a[j]/x, mod = a[j]%x, and if(!mod) just add x to ans, if not, check if(x1+mod<=x-1) add x+1... otherwise... return 0, it's not possible for this x). Now, my question is, is there a proof why this never exceeds the time limit (in fact, it doesn't seem to even get close to exceeding it)? Because the smallest element can be larger than 10^8?

I got judgement failed in problem G constantly.

How to solve it(?

Here is my submission -> 28719413

Last year we had a few ACM-ICPC finalists, including the U. of Tokyo and Waterloo, so rating ranges from 2100 to 3000.

-10

Good that's informative blog ! Songspk

Can I get All links to Educational Round?

The Workshop customarily has groups from 20 distinct nations of Europe, Asia and the United States, and the quantity of taking part colleges develops with every year. Many groups that taken an interest in the Workshop moved toward becoming members and prize-champs of ACM ICPC Finals. Whiteboard Animation Services Just to give some examples, 8 out of 13 prize winning groups of ACM ICPC Finals 2016 taken part in Moscow Workshops ACM ICPC, held by MIPT in a joint effort with University ITMO in Dolgoprudny.

And problem C is much harder than problem D.

I think problem D is so easy.

i am not able to understand the question B permutation game how many ever times i try to read it.i cant understand the test case explanation also..can some1 please help me regarding this??..thannk you

thanks got it

Integer overflow. You are storing values in long data types but they can exceed the maximum permissible limit.

eg. If you have an array of length 100 in which all elements are 2, s[99] will supposedly store 2^100 which will overflow.

can someone tell what is wrong in 28167345

+3

Is really F so easy ?

+65

When you think you've used the same (maybe sub-optimal) algorithm as everyone, but the only solution you're able to hack is your own. :(

+9

me :)
any n and k such that should work.

Who hacked me? I try it with several cases :c

+22

Oh, wow, I guess we were not that creative. Sorry, none of authors and testers heard about this one and we weren't able to google anything.

Created or updated the text

Actually flag is not causing the TLE, the problem is after erasing the color, whe should update its hash in h[] array, coz it can't be part of ans anymore.

AC code: 28157043

+15

When you find a hack in your solution!

Why your solution doesn't get overflow in big cases? 28143158

I just tried to hack but failed

Hack for A?

Actually, i don't think reinitialise of flag is required. Once flag is is set while should run for every iteration. The point is while will never run more than n times, so won't cause any problem, even there is no need of flag in while's condition. 28156733 (submission without flag in while's condition) .

I am really sorry.

You are right your code complexity is nlogn.

I think what you are missing is to reinitialise flag = 0. Once your flag is set to it never becomes 0 again causing the while loop to run in every loop after that, hence causing TLE.

There is a simple O(1) solution: 28142651

like this xd 28143158

+5

Or with division.

-14

problem A can be solvable using binary search . Equation is k*x+x<=n/2. Now search on x. Here x is number of diplomas. Here is my AC code : http://codeforces.com/contest/818/submission/28144078

The while loop will erase elements atmost n times, coz i am always erasing previously inserted elements, so the time complexity is nlongn for insertion + nlogn for erasing n elements! Total time complexity: nlogn

+13

The most simple solution is binary search with segment tree of multiplication modulo k

submit: http://codeforces.com/contest/818/submission/28143128