ashmelev's blog

By ashmelev, history, 4 months 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 neckbosov 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. adamczh218 — solved all the problems, well done!
  2. Daniar
  3. Help.me
  4. shoemakerjo
  5. Toki_Time-Tinker

UPD: The editorial is published

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

»
4 months 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).

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +77 Vote: I do not like it

!

»
4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -27 Vote: I do not like it

    codeforces hacks world cup .. <3

  • »
    »
    4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    I think for koreans is very possible xd

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -18 Vote: I do not like it

    15 min challenge

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

will-know platforms??

»
4 months ago, # |
  Vote: I like it +5 Vote: I do not like it

statemnts ???

»
4 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Short task statement == Watch the world cup earlier

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The RED coders can watch it easily. :)

»
4 months ago, # |
  Vote: I like it +129 Vote: I do not like it

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    haha codeforces hacks world cup .. <3

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The captions may be reversed. :P

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it -48 Vote: I do not like it

is it rated?

  • »
    »
    4 months 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!!

  • »
    »
    4 months ago, # ^ |
      Vote: I like it -24 Vote: I do not like it

    hope that ..if problem not accrued

    in general YES Please read carefully!!

»
4 months 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.

»
4 months 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:)

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

We will reach soon Codeforces #500 !!

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

NNSU Programming Contest 2018 ??

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

pls make extended registration I was not able to register

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wonder the time when problem 1000A appears.

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

Oh no! Queue again!

»
4 months ago, # |
  Vote: I like it +99 Vote: I do not like it

i just don't like the problems

  • »
    »
    4 months 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.

»
4 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

for problem D is example input 3 right??

»
4 months ago, # |
  Vote: I like it +66 Vote: I do not like it

why F must be such a shit

»
4 months ago, # |
  Vote: I like it +135 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +121 Vote: I do not like it

Worst contest I have ever written actually

»
4 months ago, # |
  Vote: I like it +43 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months 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 ||....

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      we know A, know the value of B and A intersection B. We find out A union B by using A+B-(A inter B). After this test if this is >1, the answer is total-A union B else -1. Only one check needed that B>=C and A>=C to make all tests pass. 39559022

    • »
      »
      »
      4 months 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)

  • »
    »
    4 months 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?

    • »
      »
      »
      4 months 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).

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

»
4 months ago, # |
  Vote: I like it +17 Vote: I do not like it

Is it a div3 contest rather than the previous 2 ?

»
4 months ago, # |
  Vote: I like it +101 Vote: I do not like it
»
4 months 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

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

Contest does not seem like div 2..!!

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

What is Testcase 7 for E?

»
4 months ago, # |
  Vote: I like it +27 Vote: I do not like it

one of the best rounds I tried thanks ashmelev

»
4 months ago, # |
  Vote: I like it +45 Vote: I do not like it

Codeforces Round #491 (Div.3)

  • »
    »
    4 months 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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Codeforces Round #495 (Div. 4)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Binary Search for the answer

  • »
    »
    4 months 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.

»
4 months 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 ??

»
4 months 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 ?

  • »
    »
    4 months 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).

  • »
    »
    4 months 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.

  • »
    »
    4 months 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..

  • »
    »
    4 months 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.

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

    in every iteration either

    which converges giving

»
4 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Test 7 for problem E??

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

does D need dp ?

»
4 months ago, # |
  Vote: I like it +7 Vote: I do not like it

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

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it +19 Vote: I do not like it

What is test 9 of problem F?

»
4 months ago, # |
  Vote: I like it +116 Vote: I do not like it

Last Div3 was harder than this.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

DP round :o

»
4 months 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...

»
4 months 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.

»
4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months 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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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.com/contest/991/submission/39568678

    • »
      »
      »
      4 months 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.com/contest/991/submission/39577766

      Focus on "next_variant" function.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    c++ be like

  • »
    »
    4 months 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)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is test 9 of problem C?

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months 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 ?

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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 ?

        • »
          »
          »
          »
          »
          4 months 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)

»
4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No, the greedy approach works. Your solution is correct

»
4 months 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?

»
4 months 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.

»
4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

»
4 months 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 ._.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What could be the pretest 9 of problem D?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    2 lines, 100 randomly generated 0 and X each

»
4 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

Task C, WA 8 anyone?

»
4 months 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

»
4 months 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.

  • »
    »
    4 months 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 :)

    • »
      »
      »
      4 months 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.

»
4 months ago, # |
  Vote: I like it -9 Vote: I do not like it

maybe, problem D needs a illustration i think:)

»
4 months 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.

  • »
    »
    4 months 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).

    • »
      »
      »
      4 months 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.

»
4 months ago, # |
  Vote: I like it +10 Vote: I do not like it

anyone else not satisfied with the difficulty of the round ?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain how to solve E ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP with bitmasks

  • »
    »
    4 months 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).

    • »
      »
      »
      4 months 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?

      • »
        »
        »
        »
        4 months 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.

»
4 months 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.

»
4 months 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).

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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 :)

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +32 Vote: I do not like it

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

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

        • »
          »
          »
          »
          »
          4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Ughhh not a good round -_-

»
4 months 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?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    recursive

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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 .

    • »
      »
      »
      4 months 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_

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        you can do it recursively.

      • »
        »
        »
        »
        4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Recursively

»
4 months 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)

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the test case 8 for problem E?

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

  • »
    »
    4 months 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...

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

»
4 months 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 ????

  • »
    »
    4 months 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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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)

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1067311732=6^4*7^7+4

»
4 months 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

»
4 months ago, # |
  Vote: I like it +60 Vote: I do not like it

The correct score distribution 750 250 750 125 1500 3000

  • »
    »
    4 months 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 !

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Why Stupid ??

        • »
          »
          »
          »
          »
          4 months 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.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Agreed it is boring but why stupid?

            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

              • »
                »
                »
                »
                »
                »
                »
                »
                4 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Okay.Yup C was much better.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            how to solve this using dp i think you have considered all the possible states,thus making dp useless

»
4 months ago, # |
  Vote: I like it -121 Vote: I do not like it

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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

      • »
        »
        »
        »
        4 months 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.

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +47 Vote: I do not like it

      He has to bear us XD.

      image

    • »
      »
      »
      4 months 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.

  • »
    »
    4 months 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.

  • »
    »
    4 months 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.

»
4 months 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

»
4 months 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 .

»
4 months 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

»
4 months 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

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    me too

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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 . :(

  • »
    »
    4 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

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

  • »
    »
    4 months 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

»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

The name of problem A is perfect :P

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 months 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.com/contest/991/submission/39579019

»
4 months 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.

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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

»
4 months 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.com/contest/991/submission/39575936

»
4 months 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.com/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.

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        4 months 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

        • »
          »
          »
          »
          »
          4 months 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...

        • »
          »
          »
          »
          »
          4 months 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

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            So why its running perfectly on other platforms

            • »
              »
              »
              »
              »
              »
              »
              4 months 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.

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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.

  • »
    »
    4 months 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.

»
4 months 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?

  • »
    »
    4 months 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.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Your crafting.oj.uz ratings are updated!

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will this contest have tutorial?

»
4 months 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 ?

  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    4 months 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.

    • »
      »
      »
      4 months 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.

»
4 months 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 ??

»
4 months 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.com/contest/991/submission/39556881

  • »
    »
    4 months 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.