Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

ashmelev's blog

By ashmelev, history, 6 months ago, translation, ,

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:

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

•
• +380
•

 » 6 months ago, # |   0 Auto comment: topic has been updated by ashmelev (previous revision, new revision, compare).
 » 6 months ago, # |   0 Why its not in the home page yet !!!!
 » 6 months ago, # |   +77 !
•  » » 6 months ago, # ^ |   +13 is that from the new Justice League movie?
•  » » » 6 months ago, # ^ |   +11 It's from the movie of land of the free and the home of the brave
•  » » 6 months ago, # ^ |   -30 hacks adds more fun to contests
•  » » 6 months ago, # ^ |   +40
 » 6 months ago, # |   +15 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.
•  » » 6 months ago, # ^ |   -27 codeforces hacks world cup .. <3
•  » » 6 months ago, # ^ |   +20 Then, you should solve all the problems within 15 minutes to watch second half of the match fully. :D :D
•  » » 6 months ago, # ^ |   +13 I think for koreans is very possible xd
•  » » 6 months ago, # ^ |   -18 15 min challenge
 » 6 months ago, # |   +4 will-know platforms??
•  » » 6 months ago, # ^ |   +30 Corrected, thank you!
 » 6 months ago, # |   +5 statemnts ???
•  » » 6 months ago, # ^ |   +20 Fixed, thanks!
 » 6 months ago, # |   +26 Short task statement == Watch the world cup earlier
•  » » 6 months ago, # ^ |   +1 skip .. skip hard hard bey
•  » » » 6 months ago, # ^ |   0 Bingo!
 » 6 months ago, # |   +17 Round.id() % 100 == Contest.id() % 100
 » 6 months ago, # | ← Rev. 2 →   +20 Solving all problems in 25 minutes (me) VS Scoring 1 point in 90 minutes (South Korea)I'm seriously wondering which one is harder.
 » 6 months ago, # |   0 The RED coders can watch it easily. :)
 » 6 months ago, # |   +129
•  » » 6 months ago, # ^ |   -34 haha codeforces hacks world cup .. <3
•  » » 6 months ago, # ^ |   +8 The captions may be reversed. :P
•  » » 6 months ago, # ^ |   +6 Is that from the Iran-Spain match? That nutmeg/tunnel? Never have seen PIQE wondering like that... LOL
 » 6 months ago, # |   -48 is it rated?
•  » » 6 months ago, # ^ | ← Rev. 2 →   -15 "rated for the participants with rating lower than 2100"Copied from the blog!!! Please read carefully!!
•  » » 6 months ago, # ^ |   -24 hope that ..if problem not accruedin general YES Please read carefully!!
 » 6 months ago, # |   -31 during world cup : contests should start earlier (before matches)i love this score distribution.
•  » » 6 months ago, # ^ |   +9 If you continue to post this sort of stuff then soon your absolute value of contribution will be highest lol.
•  » » » 6 months ago, # ^ |   0 lol
 » 6 months ago, # |   +41 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:)
 » 6 months ago, # |   +17 We will reach soon Codeforces #500 !!
 » 6 months ago, # |   +6 NNSU Programming Contest 2018 ??
•  » » 6 months ago, # ^ | ← Rev. 2 →   +8 I think " NNSU " stands for " Nizhny Novgorod State University " , There was a programming contest there this year. I THINK
•  » » » 6 months ago, # ^ |   +8 Yes, you are right!
 » 6 months ago, # |   +6 Only Gods will solve all 6 problems and watch FIFA. XD
•  » » 6 months ago, # ^ |   +22 Do you know Gods of Death love apples.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +9 Take it easy Kira xD
•  » » » » 6 months ago, # ^ |   +8 I wanna hack you!
•  » » » » » 6 months ago, # ^ |   0 try me
•  » » » » » » 6 months ago, # ^ |   +3 I will!
•  » » » » » 6 months ago, # ^ |   +3 you are welcomed to do
•  » » » » » 6 months ago, # ^ |   +3 But you didn't hack anyone, what happened?
•  » » » » » » 6 months ago, # ^ |   0 tasks aren't rather friendly to hack lover :)
•  » » » » » » » 6 months ago, # ^ |   +9 Also, the challenger, Wael.Al.Jamal failed to solve a problem
•  » » » » » » » » 6 months ago, # ^ |   0 i love green babe
•  » » » » » » » » » 6 months ago, # ^ |   +4 You have my respect Wael.Al.Jamal.
•  » » » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   +2 try with Trainee by me: Daniar <3 FIRST_GRAND_MASTER_MADE_IN_HOMS
•  » » » » » » » » » 6 months ago, # ^ |   0 wonderful @_@ 
•  » » » » » » » » » 6 months ago, # ^ |   +8 Daniar good job man
•  » » » » » » » » » 6 months ago, # ^ |   +5 thank you coach
•  » » » » » » » » » 6 months ago, # ^ |   0 no more Div2 babe
 » 6 months ago, # |   +1 pls make extended registration I was not able to register
 » 6 months ago, # |   0 I wonder the time when problem 1000A appears.
 » 6 months ago, # |   +1 Oh no! Queue again!
 » 6 months ago, # |   +99 i just don't like the problems
•  » » 6 months ago, # ^ |   +46 Me too, ABCDE looks too easy, and F is much harder than E.
 » 6 months ago, # | ← Rev. 2 →   0 for problem D is example input 3 right??
 » 6 months ago, # |   +66 why F must be such a shit
 » 6 months ago, # |   +135 This really feels like Div3 except F which is Div1 :(
 » 6 months ago, # |   +121 Worst contest I have ever written actually
 » 6 months ago, # |   +43 Problem A is an extremely intelligent problem, it tests creative skills...
•  » » 6 months ago, # ^ |   0 did b,c,d,e wa at a twice. please explain A
•  » » » 6 months ago, # ^ |   +13 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 ||....
•  » » » » 6 months ago, # ^ |   0 i was bounding c by using c!>(a+b)
•  » » » » 6 months ago, # ^ |   0 so you have creative skills... i see
•  » » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 I simply did this:A-=CB-=Cif(A<0||B<0||N-A-B-C<=0) print(-1) else print(N-A-B-C)
•  » » 6 months ago, # ^ |   0 I understood DP with bitmask solution of problem E. But your solution had less time complexity. Could you please explain your solution?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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: frequency[i] = 0. In this case, we obviously can't use digit i. So DP[i][j] = DP[i + 1][j]. 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).
•  » » » » 6 months ago, # ^ |   0 Very beautiful solution. Thanks a lot for the nice explanation.
 » 6 months ago, # |   +17 Is it a div3 contest rather than the previous 2 ?
 » 6 months ago, # |   +101
•  » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ |   0 hahaha!!!
 » 6 months ago, # |   0 2k accepted solutions for a D-problem during the contest, first time when I see something like this
•  » » 6 months ago, # ^ |   +20 Yes, it is not very difficult, so it is only 1500 points comparing to standard 2000.
•  » » » 6 months ago, # ^ |   0 anyway, this round trained solvers' speed so it compensated
 » 6 months ago, # |   +12 Contest does not seem like div 2..!!
 » 6 months ago, # |   +3 What is Testcase 7 for E?
•  » » 6 months ago, # ^ |   +3 987654320023456789
•  » » 6 months ago, # ^ |   0 I think it is 100
 » 6 months ago, # |   +27 one of the best rounds I tried thanks ashmelev
 » 6 months ago, # |   +45 Codeforces Round #491 (Div.3)
•  » » 6 months ago, # ^ |   +4 Exactly Bro.Though I wasted a lot of time proving that C can be done by Binary Search within the time limit.
•  » » 6 months ago, # ^ |   0 Codeforces Round #495 (Div. 4)
 » 6 months ago, # |   0 How to solve C?
•  » » 6 months ago, # ^ |   0 Binary Search for the answer
•  » » 6 months ago, # ^ | ← Rev. 2 →   +11 Binary search over k. Validate using a simple loop. 1e18 will take ~300 iterations of multiplying by 0.9 to reach 1.
 » 6 months ago, # |   +21 Who else felt that the author was talking about Messi in problem E :D ??
•  » » 6 months ago, # ^ |   0 Actually I have a Messi t-shirt :)
 » 6 months ago, # |   +5 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 ?
•  » » 6 months ago, # ^ |   +1 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).
•  » » 6 months ago, # ^ |   +1 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.
•  » » 6 months ago, # ^ |   +3 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..
•  » » 6 months ago, # ^ |   +3 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.
•  » » » 6 months ago, # ^ |   0 good observation
•  » » 6 months ago, # ^ |   +6 in every iteration either which converges giving
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 Mathematical Proof of convergence ?
 » 6 months ago, # |   +3 Test 7 for problem E??
•  » » 6 months ago, # ^ |   0 987654320023456789
 » 6 months ago, # |   0 does D need dp ?
•  » » 6 months ago, # ^ |   -8 Yes
•  » » » 6 months ago, # ^ |   0 What? Damn it!! You mean I'm gonna get a wrong answer?
•  » » » 6 months ago, # ^ |   +19 But my greedy passed.
•  » » » » 6 months ago, # ^ |   +24 It can be proved that the greedy approach is correct. Of course, it can be solved by DP too.
•  » » » 6 months ago, # ^ |   0 Not necessary.I solved using Greedy..My solution --> http://codeforces.com/contest/991/submission/39570625
•  » » 6 months ago, # ^ |   +1 no it doesn't. At least my sol passed without it
•  » » 6 months ago, # ^ |   0 My greedy passed pretests, so maybe not?
•  » » 6 months ago, # ^ |   +1 I solved without DP. Normal implementation.
•  » » 6 months ago, # ^ |   0 I guess greedy will work just fine. Cause length of square is just 2. So greedy will work perfectly fine.
 » 6 months ago, # |   +7 Float operations....we meet again -_-
•  » » 6 months ago, # ^ |   +32 Actually no need in floats for B. You just check that 2 * sum >= 9 * n.
 » 6 months ago, # |   +19 What is test 9 of problem F?
•  » » 6 months ago, # ^ |   -6 2846161151=7*9^9+8^9
 » 6 months ago, # |   +116 Last Div3 was harder than this.
•  » » 6 months ago, # ^ |   -8 Yeah EXACTLY...
 » 6 months ago, # |   0 DP round :o
 » 6 months ago, # |   0 What's the problem-C's idea? Just hate these kind of mathematical questions...
•  » » 6 months ago, # ^ |   +1 It's simple binary search. Nothing mathematical.
•  » » » 6 months ago, # ^ |   0 I guessed, but not tried...
 » 6 months ago, # |   +45 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.
 » 6 months ago, # | ← Rev. 3 →   +2 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
•  » » 6 months ago, # ^ |   +3 It won't take much time if you code in python... LOL
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   +3 What exactly are you referring to? I used a recursive function for that.
•  » » » » » 6 months ago, # ^ |   0 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.
•  » » » » » » 6 months ago, # ^ |   +1 It's brute force anyway. It's called backtracking if I remember correctly.
•  » » » » 6 months ago, # ^ |   0 What's "variable level nested looping" ? Can u explain in brief?
•  » » 6 months ago, # ^ |   0 My code was quite short. Maybe because of the nifty macros http://codeforces.com/contest/991/submission/39568678
•  » » » 6 months ago, # ^ |   +6 "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: ... rotflActually 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/39577766Focus on "next_variant" function.
•  » » 6 months ago, # ^ |   0 c++ be like
•  » » 6 months ago, # ^ |   +3 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)
 » 6 months ago, # |   0 What is test 9 of problem C?
•  » » 6 months ago, # ^ |   0 1000000000000000000
•  » » » 6 months ago, # ^ |   0 what's the answer ?
•  » » » » 6 months ago, # ^ |   0 39259424579862572
•  » » » » » 6 months ago, # ^ | ← Rev. 3 →   +3 got it. 'x * 0.1' is not equals to 'x / 10'. long long is 64 bits and double use 11 bits for exponent.
•  » » » » » » 6 months ago, # ^ |   0 My solution also produced wrong answer due to same issue. Could you explain a bit what do you mean by 11 bit of exponent?
•  » » » » » » » 6 months ago, # ^ |   +3 you can read this https://en.wikipedia.org/wiki/Double-precision_floating-point_format
•  » » » » » » 6 months ago, # ^ |   +4 you could get correct ans with x*0.1L which uses long double with 64 bit precision.
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 You'd better take a look on the problemset than a contest... There are many good problems specially in sgu problems.
•  » » » 6 months ago, # ^ |   0 I do solve problems other than contests, but IMHO a contest serves its own purpose.
•  » » 6 months ago, # ^ |   0 Secondly, this nowhere looks like a Div2 standard contest.How do you mean ?
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 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 ?
•  » » » » » 6 months ago, # ^ |   0 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)
 » 6 months ago, # |   0 Is there any hack against my solution for problem D, can someone please confirm? Code
•  » » 6 months ago, # ^ |   0 No, the greedy approach works. Your solution is correct
 » 6 months ago, # |   +22 Does any one think that this contest had difficulty of div 3 and previous div 3 had difficulty of div 2?
 » 6 months ago, # |   +11 Completed E with 1 min to go and then remembered that I hadn't handled numbers beginning with 0.
 » 6 months ago, # |   +15 How to prove monotonicity in problem C.I just tried, and I cannot figure out a proof.
•  » » 6 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ |   0 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.
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
 » 6 months ago, # |   0 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 ._.
•  » » 6 months ago, # ^ |   -8 the bus's number must have full type of digits in N
•  » » » 6 months ago, # ^ |   0 full type of digits ???? Did not get... :(
•  » » » » 6 months ago, # ^ |   +8 all distinct digits must be in number
•  » » » » » 6 months ago, # ^ |   0 ok I got that :D
•  » » » » 6 months ago, # ^ |   0 0, 2 & 8 all 3 types of digits in N should appear in the bus number.
•  » » » 6 months ago, # ^ |   0 I m sry but I didnt get u.
 » 6 months ago, # |   0 What could be the pretest 9 of problem D?
•  » » 6 months ago, # ^ |   +16 2 lines, 100 randomly generated 0 and X each
 » 6 months ago, # | ← Rev. 3 →   0 Task C, WA 8 anyone?
 » 6 months ago, # |   0 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
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   -9 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 :)
•  » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   -9 maybe, problem D needs a illustration i think:)
 » 6 months ago, # |   +27 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.
•  » » 6 months ago, # ^ |   +11 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).
•  » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   +10 anyone else not satisfied with the difficulty of the round ?
 » 6 months ago, # |   0 Can someone explain how to solve E ?
•  » » 6 months ago, # ^ |   0 DP with bitmasks
•  » » 6 months ago, # ^ |   +8 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).
•  » » » 6 months ago, # ^ |   0 I did it this way too (hopefully no bugs), but it seems some people did bitmask DP? Can someone explain how that works?
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 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.
 » 6 months ago, # |   +36 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.
 » 6 months ago, # |   0 Auto comment: topic has been updated by ashmelev (previous revision, new revision, compare).
 » 6 months ago, # |   +70 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.
•  » » 6 months ago, # ^ |   +40 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.
•  » » » 6 months ago, # ^ |   +22 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 :)
•  » » » » 6 months ago, # ^ |   +5 Thanks a lot :) May God bless you :)
•  » » 6 months ago, # ^ |   -10 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.
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   +32 Even a really naive solution passes: https://codeforces.com/contest/991/submission/39578686This problem is just ridiculous handling of cases, and tests your endurance more than your competitive programming skill :(
•  » » » » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 Ughhh not a good round -_-
 » 6 months ago, # |   +17 I solved E(pretests) using 10 nested for loops, is there any nicer solution?
•  » » 6 months ago, # ^ |   +21 recursive
•  » » 6 months ago, # ^ |   +23 dpmask — number of ways to place digits of n (mask < 2len(n))
•  » » 6 months ago, # ^ |   0 Not exactly... Maybe a recursive with the same idea.
•  » » » 6 months ago, # ^ |   +6 Oh, really, thanks.
•  » » 6 months ago, # ^ |   +5 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 .
•  » » » 6 months ago, # ^ |   0 But how to make every possible combination of occurrences for each number ?? I didn't got that.deepak1527_
•  » » » » 6 months ago, # ^ |   0 you can do it recursively.
•  » » » » 6 months ago, # ^ | ← Rev. 4 →   0 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- 39567146Upd: It failed systests. AC with very small change- 39603957
•  » » 6 months ago, # ^ |   0 Recursively
 » 6 months ago, # |   +51 Amongst all the criticism of the round, I must say, problem A was hilarious xD ("BugDonalds", "Kilogramm", etc)
 » 6 months ago, # |   0 What's the test case 8 for problem E?
 » 6 months ago, # |   0 Reading the comments, feeling so stupid that I didn't solved C...
•  » » 6 months ago, # ^ |   +2 Me too. Just solved 2 problems :(I am so baddd T^T
•  » » 6 months ago, # ^ |   +1 Me too. For an hour I was trying to find a formula for (n, k), because I was sure that simulation is too long...
•  » » 6 months ago, # ^ |   0 Also Me....During Contest I Was Thinking of Formula To Solve Problem C...I thought That Simulation + Binary Search Will lead to TLE.
•  » » » 6 months ago, # ^ |   0 i implemented a simulation for extreme cases, and it throws that it does at most 328 iterations or something like
 » 6 months ago, # |   0 for F, does there exist a case where you need to do a^b * c^d ????
•  » » 6 months ago, # ^ |   0 not sure but it is possible to test this case within time so it is better to test it
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   0 this can be 9*63^5 though (sorry i meant to say b, d >= 2)
•  » » 6 months ago, # ^ |   0 1067311732=6^4*7^7+4
•  » » » 6 months ago, # ^ |   0 unlucky :(((
 » 6 months ago, # |   0 What is 8th testcase in problem F? I think it's (x >= 100) ^ y + a ^ b
•  » » 6 months ago, # ^ |   +13 387426044=5555+9^9
 » 6 months ago, # |   +60 The correct score distribution 750 250 750 125 1500 3000
•  » » 6 months ago, # ^ |   0 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 !
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 Why Stupid ??
•  » » » » » 6 months ago, # ^ |   0 Well, there is 7 cases of positions of X: SpoilerX...X... O...X... OX...OX... OO...OX... OOX...OOX... OOO...OOX... OOO...OOO... 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.
•  » » » » » » 6 months ago, # ^ |   0 Agreed it is boring but why stupid?
•  » » » » » » » 6 months ago, # ^ | ← Rev. 2 →   +3 For me, "stupid problem" (or stupid solution) means problem there I don't have to think much, so.
•  » » » » » » » » 6 months ago, # ^ |   0 Okay.Yup C was much better.
•  » » » » » » 6 months ago, # ^ |   0 how to solve this using dp i think you have considered all the possible states,thus making dp useless
 » 6 months ago, # |   -121 Whoever hacked my solution A will hopefully not live to see tomorrow;)
•  » » 6 months ago, # ^ |   +56 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.
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -28 hm yes it helped actually, i fixed it though. wo so many downvotes silly joke chill people.
•  » » » » 6 months ago, # ^ |   +25 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.
•  » » » 6 months ago, # ^ |   +47 He has to bear us XD.
•  » » » » 6 months ago, # ^ |   +4 good idea \$
•  » » » » 6 months ago, # ^ |   +3 Unfortunately, Unread never changes to Read :(
•  » » » 6 months ago, # ^ |   +3 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.
•  » » 6 months ago, # ^ |   +8 Honestly, this attitude will lead you to nowhere, not mentioning the fact they were actually helping you out.
•  » » 6 months ago, # ^ |   0 Its good that someone hacked your solution as you still had time to correct you code which is definitely not possible during system testing.
 » 6 months ago, # |   0 It was one hell of an implementation_based round :OThough they weren't bad problems IMO
 » 6 months ago, # |   +30 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 .
 » 6 months ago, # | ← Rev. 2 →   +40 "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
 » 6 months ago, # | ← Rev. 3 →   +1 In C, I got WA on 28th case. Please any one will help me, where I did wrong? code
•  » » 6 months ago, # ^ |   +1 me too
•  » » 6 months ago, # ^ |   0 me too. Kindly tell me the reason once someone figures it out .
•  » » » 6 months ago, # ^ |   +4 used (2*temp>=ans) instead of (temp>=ceil(ans/2.0)) and AC
•  » » » » 6 months ago, # ^ |   0 But ceil(N/2.0) >= N/2 ... ?
•  » » 6 months ago, # ^ |   +3 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 . :(
•  » » 6 months ago, # ^ |   +4 It's better to check 2*val >= n rather than val>=half.
•  » » 6 months ago, # ^ |   0 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
 » 6 months ago, # |   +1 The name of problem A is perfect :P
 » 6 months ago, # |   0 Was it really necessary to have 222 System Tests for Problem F?
 » 6 months ago, # |   +24 Just wanted to share with you guys a nice way to solve problem E in Python:http://codeforces.com/contest/991/submission/39579019
 » 6 months ago, # |   +12 This contest was all about speed and accuracy. One WA and you are doomed.
•  » » 6 months ago, # ^ |   +3 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.
•  » » » 6 months ago, # ^ |   0 Well if you get WA during system tests I think morale will not help you
 » 6 months ago, # | ← Rev. 2 →   0 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
•  » » 6 months ago, # ^ |   0 I ran your code again on the test case #16. It says 67.
•  » » » 6 months ago, # ^ |   0 I ran the same code on C++ 14(Gcc 5.4) and it is producing 66
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 your character array size is 100. make it 101 and it will pass :) Link to ac solution : http://codeforces.com/contest/991/submission/39580573
•  » » » 6 months ago, # ^ |   0 But it has been mentioned that size wont exceed 100, then why is it so?
•  » » » » 6 months ago, # ^ |   +9 you need an additional byte for null character, right?
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   0 https://ideone.com/fNrNDf its same ideone submission is showing 75 answer
•  » » » 6 months ago, # ^ |   0 ( 75*5+3*25 )/100 = 4.5. There is nothing wrong.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 so why it is telling me a wrong answer so who's fault is this
•  » » » » » 6 months ago, # ^ |   0 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...
•  » » » » » 6 months ago, # ^ |   +3 its floating point precision issue. Instead of checking avg>=4.5 check 2*sum>=9*n
•  » » » » » » 6 months ago, # ^ |   0 So why its running perfectly on other platforms
•  » » » » » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   +17 never use round function in any language. even better never use floating point numbers unless it's inevitable.
 » 6 months ago, # |   0 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.
•  » » 6 months ago, # ^ |   +9 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.
 » 6 months ago, # |   0 991C - Candiesfor Test case #7: Input: 999999972 Jury's answer: 39259423My exactly same submitted code is giving different output on CodeForces and IdeOne.CodeForces: 39581649 Output: 39259426IdeOne: ideone Output: 39259423ashmelev Can you please check?
•  » » 6 months ago, # ^ |   +21 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.
•  » » » 6 months ago, # ^ |   0 Yes, it is fixed now. Thanks!
 » 6 months ago, # |   0 Your crafting.oj.uz ratings are updated!
 » 6 months ago, # |   0 Will this contest have tutorial?
•  » » 6 months ago, # ^ |   0 Yeah,what about the editorials?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +9 Now it is published, in several hours, as promised :)
 » 6 months ago, # |   0 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 ?
•  » » 6 months ago, # ^ |   0 Send your code. I think, you forgot next string: value=constant.
•  » » » 6 months ago, # ^ |   0
•  » » » » 6 months ago, # ^ |   0 Use long long.
•  » » » » » 6 months ago, # ^ |   0 In the above submission, I have defined a macro that reads #define int ll
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 Is it just floating point precision issue that : 39569964 got WA and 39589278 got accepted ??
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   0 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.
•  » » » 6 months ago, # ^ |   0 Thanks.