Привет!
В субботу 23 июня в 18:35 (Московское время) начнется Codeforces Round #491 (Div.2). Раунд будет рейтинговым для участников с рейтингом менее 2100, остальные участники могут решать задачи вне конкурса.
Раунд во многом пересекается с задачами олимпиады по программированию ННГУ 2018 года. Если вы принимали участие в олимпиаде или дорешивали задачи, просьба не участвовать в раунде.
В задачах раунда вам нужно будет помочь студенту Васе справиться с трудностями, вызванными окончанием учебного года. Всего будет предложено 6 задач и 2 часа на их решение. Если же вы решите все задачи за 25 минут, то успеете посмотреть второй тайм матча Южная Корея — Мексика на чемпионате мира FIFA.
Разбалловка немного нестандартная: 500-1000-1250-1500-2000-2750
Выражаю максимальную благодарность Михаилу MikeMirzayanov Мирзаянову за всем известные платформы; Николаю KAN Калинину — за помощь в подготовке задач и координацию раунда; Михаилу mike_live Кривоносову, Алексею Livace Илюхову, Никите FalseMirror Босову, Андрею GreenGrape Райскому и Алексею Aleks5d Упирвицкому — за тестирование задач; Арсению arsor Сорокину — за перевод условий. А всем участникам желаю удачи на раунде!
UPD: Раунд завершен, всем спасибо за участие!
UPD: Поздравляем победителей!
Div. 1:
Div. 2:
- King — решил все задачи, отличный результат!
- Daniar
- Saidjamol
- shoemakerjo
- Toki_Time-Tinker
UPD: Опубликован разбор задач
Автокомментарий: текст был обновлен пользователем ashmelev (предыдущая версия, новая версия, сравнить).
Auto comment: topic has been updated by ashmelev (previous revision, new revision, compare).
Why its not in the home page yet !!!!
Второй тайм матча Южная Корея — Мексика. Появилась еще одна мотивация сдать все задачи быстро.
is that from the new Justice League movie?
It's from the movie of land of the free and the home of the brave
Спасибо за контест в день Алых Парусов ^_^
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.
Then, you should solve all the problems within 15 minutes to watch second half of the match fully. :D :D
I think for koreans is very possible xd
will-know platforms??
Corrected, thank you!
statemnts ???
Fixed, thanks!
Кстати, если ставить контесты по утрам или ночам, они не будут пересекаться с матчами
Short task statement == Watch the world cup earlier
skip .. skip hard hard
bey
Bingo!
Round.id() % 100 == Contest.id() % 100
Solving all problems in 25 minutes (me) VS Scoring 1 point in 90 minutes (South Korea)
I'm seriously wondering which one is harder.
The RED coders can watch it easily. :)
The captions may be reversed. :P
Is that from the Iran-Spain match? That nutmeg/tunnel? Never have seen PIQE wondering like that... LOL
CF + Fifa WC = just WOW
is it rated?
"rated for the participants with rating lower than 2100"
Copied from the blog!!! Please read carefully!!
during world cup : contests should start earlier (before matches)
i love this score distribution.
If you continue to post this sort of stuff then soon your absolute value of contribution will be highest lol.
This is the most interesting sentence I have over seen in Codeforces:)
We will reach soon Codeforces #500 !!
NNSU Programming Contest 2018 ??
I think " NNSU " stands for " Nizhny Novgorod State University " , There was a programming contest there this year. I THINK
Yes, you are right!
Only Gods will solve all 6 problems and watch FIFA. XD
Do you know Gods of Death love apples.
Take it easy Kira xD
I wanna hack you!
try me
I will!
you are welcomed to do
But you didn't hack anyone, what happened?
tasks aren't rather friendly to hack lover :)
Also, the challenger, Wael.Al.Jamal failed to solve a problem
i love green babe
You have my respect Wael.Al.Jamal.
try with Trainee by me: Daniar <3 FIRST_GRAND_MASTER_MADE_IN_HOMS
Daniar good job man
thank you coach
pls make extended registration I was not able to register
I wonder the time when problem 1000A appears.
Oh no! Queue again!
i just don't like the problems
Me too, ABCDE looks too easy, and F is much harder than E.
why F must be such a shit
This really feels like Div3 except F which is Div1 :(
Worst contest I have ever written actually
Problem A is an extremely intelligent problem, it tests creative skills...
did b,c,d,e wa at a twice. please explain A
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 ||....
i was bounding c by using c!>(a+b)
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)
I understood DP with bitmask solution of problem E. But your solution had less time complexity. Could you please explain your solution?
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:
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).
Very beautiful solution. Thanks a lot for the nice explanation.
Is it a better div3 contest rather than the previous two?
Is it a div3 contest rather than the previous 2 ?
Vasya from problem E
anant_k_singh
hahaha!!!
2k accepted solutions for a D-problem during the contest, first time when I see something like this
Yes, it is not very difficult, so it is only 1500 points comparing to standard 2000.
anyway, this round trained solvers' speed so it compensated
Contest does not seem like div 2..!!
What is Testcase 7 for E?
987654320023456789
I think it is 100
one of the best rounds I tried thanks ashmelev
Codeforces Round #491 (Div.3)
Exactly Bro.Though I wasted a lot of time proving that C can be done by Binary Search within the time limit.
How to solve C?
Binary Search for the answer
Binary search over k. Validate using a simple loop. 1e18 will take ~300 iterations of multiplying by 0.9 to reach 1.
Who else felt that the author was talking about Messi in problem E :D ??
Actually I have a Messi t-shirt :)
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 ?
Binary search is log. Check in bs: if at some step there are k candies, at next step it will be less then 0.9k. So check takes <= log(n) base 10/9 steps. Overall complexity is O(log^2).
On day d, Vasya will have ((9/10)^{d-1})*n — k(1 + (9/10) + (9/10)^2 ... d times) = ((9/10)^{d-1})*n — 10*k(1 — (9/10)^d) candies. Make this 0 and solve for d, we see that d is logarithmic in n. So we can use binary search.
Even if we assume that only 10% candies will be eaten each day(90% will be left next day), and Vasya does not eat any candy on any day, (10/9)^r * n <= 1 ( Assuming after r days candies left<=1 ) we need to find r, put n = 10^18(for worst case), you get maximum days (r = no. of days candies will last), which is <=500. So in binary search, this bruteforce takes <= 500 computations, so Overall it takes c*500*log(10^18) computations using binary search on k..
Suppose k was 0 (it's obviously the worst case).
Each day, we have n decreasing by 10%, i.e, it becomes
. So after m days, it's 
. For n = 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.
in every iteration either
which converges giving
Mathematical Proof of convergence ?
Test 7 for problem E??
987654320023456789
does D need dp ?
Yes
What? Damn it!! You mean I'm gonna get a wrong answer?
But my greedy passed.
It can be proved that the greedy approach is correct. Of course, it can be solved by DP too.
Not necessary.I solved using Greedy..My solution --> http://mirror.codeforces.com/contest/991/submission/39570625
no it doesn't. At least my sol passed without it
My greedy passed pretests, so maybe not?
I solved without DP. Normal implementation.
I guess greedy will work just fine. Cause length of square is just 2. So greedy will work perfectly fine.
Float operations....we meet again -_-
Actually no need in floats for B. You just check that 2 * sum >= 9 * n.
What is test 9 of problem F?
2846161151=7*9^9+8^9
Last Div3 was harder than this.
Yeah EXACTLY...
DP round :o
What's the problem-C's idea? Just hate these kind of mathematical questions...
It's simple binary search. Nothing mathematical.
I guessed, but not tried...
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.
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
It won't take much time if you code in python... LOL
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.
What exactly are you referring to? I used a recursive function for that.
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.
It's brute force anyway. It's called backtracking if I remember correctly.
What's "variable level nested looping" ? Can u explain in brief?
My code was quite short. Maybe because of the nifty macros http://mirror.codeforces.com/contest/991/submission/39568678
"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://mirror.codeforces.com/contest/991/submission/39577766
Focus on "next_variant" function.
c++ be like
It does not have long code time, I did it in less than half an hour, and I'm not even a very good programmer.
Read about recursive backtracking. It's a very useful technique when generating permutations or generating subsets of a set.
I would suggest using competitive programming 3 (by Steven and Felix halim), chapter on programming paradigms, complete search. It also has exercises at the end of the section for each topic.
That being said, in this problem, you only had to generate subsets, number permutations of one subset can be calculated using a combinatorics formula. (Check out my solution)
What is test 9 of problem C?
1000000000000000000
what's the answer ?
39259424579862572
got it. 'x * 0.1' is not equals to 'x / 10'. long long is 64 bits and double use 11 bits for exponent.
My solution also produced wrong answer due to same issue. Could you explain a bit what do you mean by 11 bit of exponent?
you can read this https://en.wikipedia.org/wiki/Double-precision_floating-point_format
you could get correct ans with x*0.1L which uses long double with 64 bit precision.
can anyone tell me whats wrong with my solution of problem C. i was getting wa on pretest 6. link to my solution — http://mirror.codeforces.com/contest/991/submission/39576641
I was getting WA6, then added additional check for ans — 1, ans + 1, cuz binary search can give a wrong answer sometimes (well if implemented badly).
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.
You'd better take a look on the problemset than a contest... There are many good problems specially in sgu problems.
I do solve problems other than contests, but IMHO a contest serves its own purpose.
Secondly, this nowhere looks like a Div2 standard contest.
How do you mean ?
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.
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 ?
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)
Is there any hack against my solution for problem D, can someone please confirm? Code
No, the greedy approach works. Your solution is correct
Does any one think that this contest had difficulty of div 3 and previous div 3 had difficulty of div 2?
Completed E with 1 min to go and then remembered that I hadn't handled numbers beginning with 0.
How to prove monotonicity in problem C.I just tried, and I cannot figure out a proof.
Let's assume that K is our optimal answer.
We can prove that K+1 would hold good to get more than N/2 candies.
Similarly, we can prove that 1,2,....,K-1 won't hold good. So it's like shifted unit step function (considering >=0 part only) if you observe carefully. And I guess, we can run binary search to find the starting point of that step.
The amount of chocolates he collected at each turn monotonically decreases.Now, when vasya increases the value of k the rate of vasya collecting chocolates at each turn further reduces. Finally, total chocolates collected by petya in the end for a given n decreases with increase in k. Thus, chocolates collected by Vasya is also monotonic.This was my way to convince myself with a logical inference.
I think it helps to look at it from Petya's perspective — there's still just one hole which I can't fill in though.
Suppose, eating k candies daily, Vasya cannot reach
, and the process takes d days. The candies Peyta gets are 
With k - 1, he gets 
Basically, with Vasya eating k - 1 each day, and taking into account that we're flooring, Petya gets at least as many as he does as when Vasya eats k daily. Now, if with k - 1 the process takes ≤ d days, Vasya has less candies than he first did, so certainly not
. If it takes > d days, Petya has at least as many on each day as he had previously, so he ends up with at least as many as he had previously, which means Vasya can't have 
anyway.
The only irregularity here is the last 9 candies — and even that disappears once d is high enough ( ≥ 9). Probably, that case can be worked out separately or something. Or maybe my logic can be modified a bit to take care of that, I'm just not seeing it.
Edit: Small mistake in the numbers, fixed now.
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 ._.
the bus's number must have full type of digits in N
full type of digits ???? Did not get... :(
all distinct digits must be in number
ok I got that :D
0, 2 & 8 all 3 types of digits in N should appear in the bus number.
I m sry but I didnt get u.
What could be the pretest 9 of problem D?
2 lines, 100 randomly generated 0 and X each
Task C, WA 8 anyone?
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
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.
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 :)
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.
maybe, problem D needs a illustration i think:)
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.
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).
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.
anyone else not satisfied with the difficulty of the round ?
Can someone explain how to solve E ?
DP with bitmasks
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).
I did it this way too (hopefully no bugs), but it seems some people did bitmask DP? Can someone explain how that works?
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.
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.
Auto comment: topic has been updated by ashmelev (previous revision, new revision, compare).
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.
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.
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 :)
Thanks a lot :) May God bless you :)
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.
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.
Even a really naive solution passes: https://mirror.codeforces.com/contest/991/submission/39578686
This problem is just ridiculous handling of cases, and tests your endurance more than your competitive programming skill :(
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.
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.
Ughhh not a good round -_-
I solved E(pretests) using 10 nested for loops, is there any nicer solution?
recursive
dpmask — number of ways to place digits of n (mask < 2len(n))
Not exactly... Maybe a recursive with the same idea.
Oh, really, thanks.
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 .
But how to make every possible combination of occurrences for each number ?? I didn't got that.deepak1527
you can do it recursively.
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
Recursively
What's the test case 8 for problem E?
1000000000000000000
Автокомментарий: текст был обновлен пользователем ashmelev (предыдущая версия, новая версия, сравнить).
Amongst all the criticism of the round, I must say, problem A was hilarious xD ("BugDonalds", "Kilogramm", etc)
What's the test case 8 for problem E?
Reading the comments, feeling so stupid that I didn't solved C...
Me too. Just solved 2 problems :(
I am so baddd T^T
Me too. For an hour I was trying to find a formula for (n, k), because I was sure that simulation is too long...
Also Me....During Contest I Was Thinking of Formula To Solve Problem C...I thought That Simulation + Binary Search Will lead to TLE.
i implemented a simulation for extreme cases, and it throws that it does at most 328 iterations or something like
Люди, почему в задаче С ответ 3. Если Вася будет брать по 2, то счёт будет 35 : 33.
68 — 66 — 60 — 58 — 53 — 51 — 46 — 44 — 40 — 38 — 35 — 33 — 30 — 28 — 26 — 24 — 22 — 20 — 18 — 16 — 15 — 13 — 12 — 10 — 9 — 7 — 5 — 3 — 1 — 0
Счёт будет 33:35 в пользу Васи. 33 = 12 * 2 + 9.
Применительно к k = 2 можем написать
Я уже сам такое написал, но спасибо что ответили. Считал руками, сбился при подсчёте двоек у Васи :-( Петю высчитал n — Вася и залет.
~~~~~
А чем плох Паскаль в данном случае? Рассматривайте это как псевдокод
-
Не понял, что вы хотите мне донести, я контест решал на С++, а тестовую программу написал на Паскале (у меня нет фантомных болей от него).
Зато у меня есть РЕАЛЬНАЯ БОЛЬ от С++, в том месте, где сишка забывает проверить выход за пределы массива или строки, или подобном, Паскаль в этом случае более строг.
Реальное преимущество С++ на контестах — STL. Хотя я вас понимаю, если в школе вы работали на Turbo Pascal. :-)
Да ничего донести особо то и не хотел, просто пошутил.
забывает проверить выход за пределы массива или строкиВы недооцениваете возможности C++.Думаю, эта статья будет вам полезна.
for F, does there exist a case where you need to do a^b * c^d ????
not sure but it is possible to test this case within time so it is better to test 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.
this can be 9*63^5 though (sorry i meant to say b, d >= 2)
1067311732=6^4*7^7+4
unlucky :(((
What is 8th testcase in problem F? I think it's (x >= 100) ^ y + a ^ b
387426044=5555+9^9
The correct score distribution 750 250 750 125 1500 3000
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 !
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.
Why Stupid ??
Well, there is 7 cases of positions of X:
X...
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.
Agreed it is boring but why stupid?
For me, "stupid problem" (or stupid solution) means problem there I don't have to think much, so.
Okay.Yup C was much better.
Whoever hacked my solution A will hopefully not live to see tomorrow;)
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.
hm yes it helped actually, i fixed it though. wo so many downvotes silly joke chill people.
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.
He has to bear us XD.
good idea $
Unfortunately, Unread never changes to Read :(
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.
Honestly, this attitude will lead you to nowhere, not mentioning the fact they were actually helping you out.
Its good that someone hacked your solution as you still had time to correct you code which is definitely not possible during system testing.
It was one hell of an implementation_based round :O
Though they weren't bad problems IMO
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 .
"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
In C, I got WA on 28th case. Please any one will help me, where I did wrong? code
me too
me too. Kindly tell me the reason once someone figures it out .
used (2*temp>=ans) instead of (temp>=ceil(ans/2.0)) and AC
But ceil(N/2.0) >= N/2 ... ?
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 . :(
It's better to check
2*val >= nrather thanval>=half.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
The name of problem A is perfect :P
Was it really necessary to have 222 System Tests for Problem F?
Just wanted to share with you guys a nice way to solve problem E in Python:
http://mirror.codeforces.com/contest/991/submission/39579019
This contest was all about speed and accuracy. One WA and you are doomed.
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.
Well if you get WA during system tests I think morale will not help you
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://mirror.codeforces.com/contest/991/submission/39575936
I ran your code again on the test case #16. It says 67.
your character array size is 100. make it 101 and it will pass :) Link to ac solution : http://mirror.codeforces.com/contest/991/submission/39580573
But it has been mentioned that size wont exceed 100, then why is it so?
you need an additional byte for null character, right?
well i don't see why codeforces have BUG/ERROR on judging solutions.here is the link to my solution to 2nd question http://mirror.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.
https://ideone.com/fNrNDf its same ideone submission is showing 75 answer
( 75*5+3*25 )/100 = 4.5. There is nothing wrong.
so why it is telling me a wrong answer so who's fault is this
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...
its floating point precision issue. Instead of checking avg>=4.5 check 2*sum>=9*n
So why its running perfectly on other platforms
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.
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.
never use round function in any language. even better never use floating point numbers unless it's inevitable.
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.
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.
991C - Эклеры
for Test case #7:Input: 999999972Jury'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?
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
To
and you will have the correct answer.
Will this contest have tutorial?
Yeah,what about the editorials?
Now it is published, in several hours, as promised :)
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 ?
Send your code. I think, you forgot next string: value=constant.
39573171
Use long long.
In the above submission, I have defined a macro that reads #define int ll
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.
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.
Is it just floating point precision issue that :
39569964 got WA and
39589278 got accepted ??
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://mirror.codeforces.com/contest/991/submission/39556881
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.