ashmelev's blog

Codeforces Round #491 (Div.2)
By ashmelev, history, 6 years ago, translation, In English

Hello!

Codeforces Round #491 (Div.2) will start this Saturday, June 23, 18:35 (UTC+3). This round will be rated for the participants with rating lower than 2100 and other contestants can join it out of competition.

This round problems have a significant intersection with NNSU Programming Contest 2018. Please do not participate in the round if you participated in the NNSU contest or tried to upsolve the problems.

During the round you have to help student Vasya to manage the difficulties caused by the end of the academic year. There will be 6 problems and 2 hours to solve them. If you solve all the problems in 25 minutes you will be able to watch the second half of South Korea — Mexico at the FIFA World Cup.

The scoring is unusual a bit: 500-1000-1250-1500-2000-2750

Great thanks to Mikhail MikeMirzayanov Mirzayanov for the well-known platforms; Nikolay KAN Kalinin — for the help with problems and the round coordination; Mikhail mike_live Krivonosov, Alexey Livace Ilyukhov, Nikita FalseMirror Bosov, Andrew GreenGrape Rayskiy and Alexey Aleks5d Upirvitskiy — for the round testing; Arseniy arsor Sorokin — for the statements translation. And good luck to all contestants!

UPD: The round is over, thank you for the participation!

UPD: Congratulations to the winners!

Div. 1:

  1. nuip
  2. krijgertje
  3. qoo2p5
  4. hohomu
  5. neal

Div. 2:

  1. King — solved all the problems, well done!
  2. Daniar
  3. Saidjamol
  4. shoemakerjo
  5. Toki_Time-Tinker

UPD: The editorial is published

  • Vote: I like it
  • +380
  • Vote: I do not like it

Comments Comments (274)
| Write comment?
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Why its not in the home page yet !!!!

→ Reply
»
6 years ago, # |
  Vote: I like it +77 Vote: I do not like it

!

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Can't you push the contest start just 10 minutes? Give us Mexicans and Koreans a chance to watch at least the full first half. Finishing in 25 minutes is a little impossible btw.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think for koreans is very possible xd

    → Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

will-know platforms??

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

statemnts ???

→ Reply
»
6 years ago, # |
  Vote: I like it +26 Vote: I do not like it

Short task statement == Watch the world cup earlier

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Round.id() % 100 == Contest.id() % 100

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

Solving all problems in 25 minutes (me) VS Scoring 1 point in 90 minutes (South Korea)

I'm seriously wondering which one is harder.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The RED coders can watch it easily. :)

→ Reply
»
6 years ago, # |
  Vote: I like it +129 Vote: I do not like it

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The captions may be reversed. :P

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it -48 Vote: I do not like it

is it rated?

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it -15 Vote: I do not like it

    "rated for the participants with rating lower than 2100"

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

    → Reply
»
6 years ago, # |
  Vote: I like it -31 Vote: I do not like it

during world cup : contests should start earlier (before matches)

i love this score distribution.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +41 Vote: I do not like it

If you solve all the problems in 25 minutes you will be able to watch the second half of South Korea — Mexico at the FIFA World Cup.

This is the most interesting sentence I have over seen in Codeforces:)

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

We will reach soon Codeforces #500 !!

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

NNSU Programming Contest 2018 ??

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Only Gods will solve all 6 problems and watch FIFA. XD

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

pls make extended registration I was not able to register

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder the time when problem 1000A appears.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Oh no! Queue again!

→ Reply
»
6 years ago, # |
  Vote: I like it +99 Vote: I do not like it

i just don't like the problems

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +66 Vote: I do not like it

why F must be such a shit

→ Reply
»
6 years ago, # |
  Vote: I like it +135 Vote: I do not like it

This really feels like Div3 except F which is Div1 :(

→ Reply
»
6 years ago, # |
  Vote: I like it +121 Vote: I do not like it

Worst contest I have ever written actually

→ Reply
»
6 years ago, # |
  Vote: I like it +43 Vote: I do not like it

Problem A is an extremely intelligent problem, it tests creative skills...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      Sure, just write this...

      int grad = a + b — c; if (grad >= n || a >= n || b >= n || c >= n || n == 0 || c > a || c > b) cout << -1;

      For every WA I got, I added one more instruction with ||....

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        i was bounding c by using c!>(a+b)

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I simply did this:

      A-=C

      B-=C

      if(A<0||B<0||N-A-B-C<=0) print(-1) else print(N-A-B-C)

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      Sure! I use some sort of knapsack-like DP.

      Let frequency[i] be the number of times digit i appears in the input. I calculated DP[i][j] = in how many ways I can get a number of length j using only digits {i, i+1, ...., 9}.

      There are two cases:

      1. frequency[i] = 0. In this case, we obviously can't use digit i. So DP[i][j] = DP[i + 1][j].
      2. frequency[i] > 0. Here, I'm forced to use digit i at least once. Let's iterate the number of times I'll actually want to use digit i. I iterate this with a variable k which goes from 1 to frequency[i]. Now, I want to obtain length j, and exactly k digits are forced to be equal to i. We only have to decide in which positions will be those k digits. It's not hard to see we have j available positions and we have to choose k of them, so the answer is Comb(j, k), a binomial coefficient. We're left with j-k positios to fill using digits {i+1, i+2, ...., 9}.

      So we have DP[i][j] += DP[i + 1][j — k] * Comb(j, k).

      There is a special case when i = 0. Then, I won't be able to put a 0 on the first positions, so I'm only left with j — 1 positions to choose from.

      So DP[0][j] += DP[1][j — k] * Comb(j — 1, k).

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Very beautiful solution. Thanks a lot for the nice explanation.

        → Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it a div3 contest rather than the previous 2 ?

→ Reply
»
6 years ago, # |
  Vote: I like it +101 Vote: I do not like it

Vasya from problem E

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

2k accepted solutions for a D-problem during the contest, first time when I see something like this

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      anyway, this round trained solvers' speed so it compensated

      → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Contest does not seem like div 2..!!

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

What is Testcase 7 for E?

→ Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

one of the best rounds I tried thanks ashmelev

→ Reply
»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

Codeforces Round #491 (Div.3)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary Search for the answer

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Who else felt that the author was talking about Messi in problem E :D ??

→ Reply
»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

What a joke of a contest ! D is not a 1500 problem. Can someone prove that C lies within time bounds using a binary search ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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).

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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..

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 = 1018, 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(1018) * 380), which isn't really a problem.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    in every iteration either

    which converges giving

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Test 7 for problem E??

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

does D need dp ?

→ Reply
»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Float operations....we meet again -_-

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +32 Vote: I do not like it

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

    → Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

What is test 9 of problem F?

→ Reply
»
6 years ago, # |
  Vote: I like it +116 Vote: I do not like it

Last Div3 was harder than this.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

DP round :o

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the problem-C's idea? Just hate these kind of mathematical questions...

→ Reply
»
6 years ago, # |
  Vote: I like it +45 Vote: I do not like it

One of the worst contests I have seen. Maybe it is time for codeforces team to consult atcoder coordinators about how to arrange quality contests.

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +2 Vote: I do not like it

I feel so bad. Problems which have long code-time make me crazy (I am talking about problem E ToT). Problem E has not very much brainstorm, just long code ToT

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It has nothing to do with python it's just that not many people know about variable level nested looping(even I didn't until today). So I guess at least I learnt something new from this contest.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        What exactly are you referring to? I used a recursive function for that.

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          That's what I called variable level nested looping. In each level of recursion there is a for loop.

          The brute force way to do it would be to use 10 nested loops or so. I didn't know that it could actually be implemented easily with recursion until today.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it +1 Vote: I do not like it

            It's brute force anyway. It's called backtracking if I remember correctly.

            → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What's "variable level nested looping" ? Can u explain in brief?

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      "My code was quite short"

      Me: hmm, interesting

      "Maybe because of the nifty macros"

      Me: hmm, okay, let's see...

      "FOR(a0, 0) FOR(a1, 1) FOR(a2, 2) FOR(a3, 3) FOR(a4, 4) FOR(a5, 5) FOR(a6, 6) FOR(a7, 7) FOR(a8, 8) FOR(a9, 9){"

      Me: ... rotfl

      Actually I had an idea of doing just that, but couldn't make myself write such an abomination of all coding principles I've been taught to follow :) So, 23 seconds (yes, seconds! :) ) before the contest was over, I ended up getting AC with something way cleaner imho:

      http://codeforces.net/contest/991/submission/39577766

      Focus on "next_variant" function.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    c++ be like

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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)

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 9 of problem C?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This is just sad. I used to participate in CF rounds to learn something new, but the past few contests have focused way too much on just implementation. Disappointed! :/

Secondly, this nowhere looks like a Div2 standard contest.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I do solve problems other than contests, but IMHO a contest serves its own purpose.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Secondly, this nowhere looks like a Div2 standard contest.

    How do you mean ?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What I mean is, an average Div2 contest does not having the problems of this difficulty (I'm talking about D,E,F), and the AC solutions in this proportion.
      It looks more like a Div3 contest.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Did you find all the problems easy ?

        I was very happy I got the binary search idea for C. I didn't think it was obvious. I wasn't able to do D, E and F :) Were you ?

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, I knew the algorithm for both C and E, but made silly mistakes while implementing it during contest (Got it for E, looking into C's bug)

          → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there any hack against my solution for problem D, can someone please confirm? Code

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, the greedy approach works. Your solution is correct

    → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Does any one think that this contest had difficulty of div 3 and previous div 3 had difficulty of div 2?

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Completed E with 1 min to go and then remembered that I hadn't handled numbers beginning with 0.

→ Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

How to prove monotonicity in problem C.I just tried, and I cannot figure out a proof.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain to me why 80 cannot be the number of the bus? 2028 has '8' and '0' both. I guess I have misunderstood the whole thing ._.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What could be the pretest 9 of problem D?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    2 lines, 100 randomly generated 0 and X each

    → Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Task C, WA 8 anyone?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F ? i made an assumption that the optimal is either 1- take the number as it is 2- take a set of divisors and multiply them and for each number i used DP to find the minimum length to represent it, either : 1- its length 2- multiplication of prime factors 3- x*10^p + .....

However seems am missing sth or maybe buggy code :3

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was the worst round I ever took part in. Each problem can be solved by a monkey without creative thinking. To solve everything, it was necessary to have hands for realization.There was none idea problem. Also problem D should not be solved by 65% of participants.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    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 :)

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I wrote this because I was very angry. I had found the solutions of E and F for 5 minutes after reading legend but didn't found the bugs in the code for an hour.

      → Reply
»
6 years ago, # |
  Vote: I like it -9 Vote: I do not like it

maybe, problem D needs a illustration i think:)

→ Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

Instead of ranting at the level or quality of questions, spare some time to appreciate the efforts of the authors for conducting it. Weird how only handful of guys got all of them correct but almost everyone is lashing out here about the quality of problems.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Tbh it's the difficulty of the questions which is low quality of questions is decent enough(apart from F which I don't know about).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can't complain when the contest problems were directly picked from some third party contest. The original problem setters were probably not aware that the contest will be used as a Div 2 contest on codeforces in future.

      → Reply
»
6 years ago, # |
  Vote: I like it +10 Vote: I do not like it

anyone else not satisfied with the difficulty of the round ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve E ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP with bitmasks

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    First, you can easily store the number of appearance of every digit.

    Let's calculate through every case that, in each, the number of used digit of each value (from 0 to 9) is either zero if there isn't any of such at first, or any positive value not higher than its initial appearance count. This could be implemented via backtracking.

    To calculate the value for each case, you need to know the number of distinct permutations and distinct permutations with leading zero(s).

    The number of distinct permutations is the factorial of the total digit count, divided by the factorial of each digit's appearance count.

    e.g.: with 2344, the number of permutations is 4! / 1! / 1! / 2! = 12.

    If there is no zeros in the case, obviously there would be no permutations with leading zeros. Otherwise, subtract one from the appearance count of 0, and calculate the number similar to above.

    The result for each case is of course, the number of permutations, subtracted by the number of permutations with leading zero(s).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I did it this way too (hopefully no bugs), but it seems some people did bitmask DP? Can someone explain how that works?

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Basic outline is this:-
        Use your mask on digits of the number to determine whether you are picking that digit or not. Check if the masked digits contains all distinct digits that appear or not, and then find all valid permutations for the mask. To avoid recounting, you can hash the digits obtained in the mask and store it.

        → Reply
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

I was super proud that I finished 5 out of 6 problems! Then I took a look at Codeforces predictor and realized that at least 500 other people did as well and that my rating is probably going to go down.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
6 years ago, # |
  Vote: I like it +70 Vote: I do not like it

I am not a big fan of criticising contests, but this is a bit too far. None of the problems require any kind of creative problem solving, being obvious applications of the techniques. (side note: "Obvious" is a strong word, but given that more than 600 people solved ABCDE, I think it is used properly). Given that more than 600 people out of 6000 solved ABCDE, this cannot qualify as more than a speed coding contest. For speed coding contests, I recommend the codeforces team not to give div4 problems to a div2 competition and mess our ratings, but to just redirect people to websites like typing.io or codefights.com :)

I do not think there is anything good to say about problem F. It was simply disgusting to say the least.

I do not wish to make anyone feel bad trough my comment, but this is the first time I actually comment anything negative on a contest announcement and I really feel it points out some issues that really have to be fixed.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +40 Vote: I do not like it

    You are a Candidate Master. So, you may fell all the problems were easy.

    However, when programmers such as me solve C, we feel happy. Then reading comments like this telling that the problems were all very 'obvious' are demotivating :)

    I don't quite think C is obvious. The binary search idea is not obvious to beginners.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      I see your point. I clearly do not wish to demotivate anyone with less experience, that is for certain :) The problem is that this was theoretically a contest for all div2 users, but it certainly didn't act like one. A div2 contest should have problems that feel very easy and very hard, but this one certainly didn't have the latter. The only reason problem F had so few AC submissions is that it was a hard implementation problem. This might have been a very good contest for beginners but it definitely wasn't for more experienced users. In the same way that my comment may be sadly demotivating for "younger" competitive coders, this contest was for the good ones. It is horrible to be on #600 when you solved 5/6 problems and see your rating drop badly. Anyway, keep up the good work. One day these problems will seem "obvious" to you too, it is just a matter of experience :)

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    I agree that problems were a little bit too easy but it is not right to compare this to a type race. I am sure that people did not come with solution in instants after reading the statements, competitive programming is also about proving things fast.

    For example in problem E I was hesitant to just "bruteforce" it, becuase it was not clear what was the complexity to me. But it turns out that the compexity is proportional to nd0*nd1*nd2*...*nd9 where nd0+nd1+...nd9=18 The worst case for this is when 18 is evenly distributed among ndi's, which means that the worst case is proportional to less than 2^10. Which is a cool proof to keep in mind I believe.

    Also if you did not solve problem F how do you say that it is disgusting? It may have a cool proof that you do not know about.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      imho F is an amazing problem. you could start with a really naive soution (that TLE's) then slowly prune the stuff you have to test.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

        Even a really naive solution passes: https://codeforces.net/contest/991/submission/39578686

        This problem is just ridiculous handling of cases, and tests your endurance more than your competitive programming skill :(

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, due to the dynamics of the round the faster you do A-E the more time you could put on F. But it's also not impossible to do F quickly if you see a bunch of clever stuff.

          → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      also this round is good for the majority of people (who normally solve the first two in a regular round then that's all). Here there's a better differentiation between a 1700 (who'll get 4-5) and a 1300 (who'll get 2-3). In many other rounds both the 1700 and the 1300 will get 2 problems and it's up to speed. So I think the speed aspect is much smaller here for most of the people, except for the tippy top.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ughhh not a good round -_-

→ Reply
»
6 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I solved E(pretests) using 10 nested for loops, is there any nicer solution?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    recursive

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

    dpmask — number of ways to place digits of n (mask < 2len(n))

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Not exactly... Maybe a recursive with the same idea.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    first count the occurrences of each digit from 0 to 9, Now take every possible combination of occurrences of each number such that each number occurs atleast once. now for each case it becomes a combinatorics problem to count possible no. of ways to arrange digits such that zero does not come on first place .

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But how to make every possible combination of occurrences for each number ?? I didn't got that.deepak1527

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you can do it recursively.

        → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 4   Vote: I like it 0 Vote: I do not like it

        It can also be done iteratively you can mask the occurrence of each number by first creating a prefix multiplication array of occurrences of every number is original number. Then masking them as occurence of 0 in current mask*1+occurence of 1 in current mask*pre[1]+..... Implementation of the idea- 39567146

        Upd: It failed systests. AC with very small change- 39603957

        → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Recursively

    → Reply
»
6 years ago, # |
  Vote: I like it +51 Vote: I do not like it

Amongst all the criticism of the round, I must say, problem A was hilarious xD ("BugDonalds", "Kilogramm", etc)

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the test case 8 for problem E?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Reading the comments, feeling so stupid that I didn't solved C...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Me too. Just solved 2 problems :(
    I am so baddd T^T

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Me too. For an hour I was trying to find a formula for (n, k), because I was sure that simulation is too long...

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also Me....During Contest I Was Thinking of Formula To Solve Problem C...I thought That Simulation + Binary Search Will lead to TLE.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i implemented a simulation for extreme cases, and it throws that it does at most 328 iterations or something like

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

for F, does there exist a case where you need to do a^b * c^d ????

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    not sure but it is possible to test this case within time so it is better to test it

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't solve F, but there exists a number 9^6*7^5 = 8931928887. But I'm not sure, there may be exists shorter answer.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      this can be 9*63^5 though (sorry i meant to say b, d >= 2)

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1067311732=6^4*7^7+4

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What is 8th testcase in problem F? I think it's (x >= 100) ^ y + a ^ b

→ Reply
»
6 years ago, # |
  Vote: I like it +60 Vote: I do not like it

The correct score distribution 750 250 750 125 1500 3000

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    D was not that easy... It was really easy(the ones who did not take the case 000 000 when d[i] = 2 + d[i — 3] are stupid including me) but not easier than C man !

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      There is very stupid greedy solution of this problem. I think it's really that easy. In C you actually have to think more than one minute.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why Stupid ??

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, there is 7 cases of positions of X:

          Spoiler

          each case have 1-2 lines of code inside, cases itself are simple to find. If you don't consider this kind of problem easy and boring, I do.

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Agreed it is boring but why stupid?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
              ← Rev. 2   Vote: I like it +3 Vote: I do not like it

              For me, "stupid problem" (or stupid solution) means problem there I don't have to think much, so.

              → Reply
»
6 years ago, # |
  Vote: I like it -121 Vote: I do not like it

Whoever hacked my solution A will hopefully not live to see tomorrow;)

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +56 Vote: I do not like it

    You actually should be gratefull when someone hacks you. If your solution can be hacked, you most likely will get WA after the systests. But if you got hacked, you can fix your mistake.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
      ← Rev. 2   Vote: I like it -28 Vote: I do not like it

      hm yes it helped actually, i fixed it though. wo so many downvotes silly joke chill people.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +25 Vote: I do not like it

        I consider wishing someone to die not as a joke, not even close. I can understand black humor, if it's funny and creative, but this is just disgusting.

        → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      He has to bear us XD.

      image

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      I totally agree. My solution for problem D was hacked before 2 minutes of contest end. I somehow managed to fix the bug in last minute and got accepted. If my solution wouldn't have hacked, I would not even got a single point for problem D. Something is better than nothing. :)
      Sorry, for my poor english.

      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Honestly, this attitude will lead you to nowhere, not mentioning the fact they were actually helping you out.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Its good that someone hacked your solution as you still had time to correct you code which is definitely not possible during system testing.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It was one hell of an implementation_based round :O

Though they weren't bad problems IMO

→ Reply
»
6 years ago, # |
  Vote: I like it +30 Vote: I do not like it

The problems are kind of too easy for Div2 (except for F) . Thanks for preparing the contest anyway . It could be a very nice contest if F is easier and let D,E be harder .

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

"If you solve all the problems in 25 minutes you will be able to watch the second half of South Korea — Mexico at the FIFA World Cup."

Well I guess he wasn't joking after all! :D

→ Reply
»
6 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

In C, I got WA on 28th case. Please any one will help me, where I did wrong? code

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    me too

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    me too. Kindly tell me the reason once someone figures it out .

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    ll half = ceil(N/2.0) ; this line might be giving precision error, I also got the wa verdict on this test case , now i changed my code to keep the count of both vasya and petya , it got accepted . :(

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    It's better to check 2*val >= n rather than val>=half.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ll half = ceil(N/2.0) ; is causing precision error for larger value of N (N > 10^15); for N = 999999999999999973; half should be 499999999999999987 but ceil gives 500000000000000000 using ll half = (N+1)/2; fixes this

    → Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

The name of problem A is perfect :P

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Was it really necessary to have 222 System Tests for Problem F?

→ Reply
»
6 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Just wanted to share with you guys a nice way to solve problem E in Python:

http://codeforces.net/contest/991/submission/39579019

→ Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

This contest was all about speed and accuracy. One WA and you are doomed.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I think there might be other factors in it.

    I got WA in A incredibly early (and only got to solve it 1 hour later), though after solving 5 problems and got 2 successful hacks, my final standing is quite decent.

    A WA-verdict might not be the worst thing happened here — lose your morale and you are doomed.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well if you get WA during system tests I think morale will not help you

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I have been judged wrongly regarding question D.Bishwock for test case 16 It is showing that the correct answer is 66 and on runnning my code for the given test case, i am getting the answer as 66, but the status shows "Wrong answer on test 16". Please help!

Here is the link to my submission:

http://codeforces.net/contest/991/submission/39575936

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

well i don't see why codeforces have BUG/ERROR on judging solutions.here is the link to my solution to 2nd question http://codeforces.net/contest/991/submission/39564485 and at test case 29 i see no problem at all on getting answer 75. so why is it showing 76 there. i have rechecked it again and again.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    https://ideone.com/fNrNDf its same ideone submission is showing 75 answer

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ( 75*5+3*25 )/100 = 4.5. There is nothing wrong.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        so why it is telling me a wrong answer so who's fault is this

        → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          using divide by n is a bit risky because it might give u 4.49999 instead of 4.5 I dont know if the same in happening in ur solution... but this happened for me .....

          Had a reaally bad contest tonight...

          → Reply
        • »
          »
          »
          »
          »
          6 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          its floating point precision issue. Instead of checking avg>=4.5 check 2*sum>=9*n

          → Reply
          • »
            »
            »
            »
            »
            »
            6 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            So why its running perfectly on other platforms

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              6 years ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              when you have something like 1.5 it may not be stored exactly as 1.5. some systems take it as 1.4999999999 others have it as 1.50000000001 so that tiny change might result in completely different output and which one happens is compiler dependent. So it's a good practice to never use floating point numbers unless it's inevitable.

              → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Never use Python round function ever!!!! It F**KS you bad. Got WA in main tests for 2 questions(B and C) and I have learnt my lesson. Just avoid.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    never use round function in any language. even better never use floating point numbers unless it's inevitable.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I do not get the hate against the setter. It was clearly mentioned it had an intersection with some other contest and the problems might have been taken from there. Even if not, if someone has a problem then I would love to see a contest from them.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    If you blame a cook for cooking bad food that doesn't mean you can cook better than him it means that he didn't do his job properly.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

991C - Candies

for Test case #7: Input: 999999972 Jury's answer: 39259423

My exactly same submitted code is giving different output on CodeForces and IdeOne.

CodeForces: 39581649 Output: 39259426

IdeOne: ideone Output: 39259423

ashmelev Can you please check?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    It seems that problem is in float type which handles big integers poorly. Probably exact precision is compiler-dependent; anyway I recommend you to avoid non-integer operations in such problems.

    Just replace 

    if (k * days + m >= ceil((float)n / 2))

    To

    if (k * days + m >= (n + 1) / 2)

    and you will have the correct answer.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this contest have tutorial?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In C, instead of m = (lo + hi) / 2, I wrote m = floor((lo + hi) / 2.0), but my submission gave tle for n = 1000000000000000000. When I tried to find out the reason, I figured out that for lo = 39259424579862569 and hi = 39259424579862576, m came out to be = 39259424579862576. Can anyone explain the reason for this ?

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Send your code. I think, you forgot next string: value=constant.

    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It is due to the ceil and floor functions being so slow! Check this submissions : 1 2. The only difference here is in ceil function. I generally try to avoid ceil and floor function now! I found a discussion here but am unable to get it. It would be great if anyone can explain some concrete reason behind this.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I think you misunderstood my problem, I tested it locally by printing the values of lo and hi and found that for the value I mentioned in my comment at the top of this discussion, m was coming out the same as hi and so hi was not decreasing at all. That was the reason for tle.

      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it just floating point precision issue that :
39569964 got WA and
39589278 got accepted ??

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In B, I got WA on 18th test case. Can anyone explain what is wrong with my code? I can't understand I got correct answer on other online IDEs. here is my code http://codeforces.net/contest/991/submission/39556881

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Here is the AC version of your code: 39603674. The WA was because of precision issues with floating point numbers, which relates to the way they are stored in the memory. Rather than directly comparing them for being less than 0, it is a good practice to check that they are less than a very small value like 1e-9. Because of the way they are stored, a value that is very very small and can be treated as a 0, might compare greater than 0, so it is better to compare them to a smaller value and not 0. I have even seen some compilers giving warning msgs when I tried to apply comparison operations to floating pt numbers.

    → Reply