(Translation: Hello)
We are very happy to invite you to take part in our contest, Codeforces Round 666 (Div. 1) and Codeforces Round 666 (Div. 2). The contest starts on 30.08.2020 17:35 (Московское время) and lasts 2 hours. In both divisions, there will be 5 problems for you to solve.
The problems were authored and prepared by ruanxiaoyu, DatVu, MofK, and me.
We are very grateful and would like to sincerely thank the following people for their assistance in preparing the round:
300iq for coordinating our round and for reviewing and helping us with the problems.
minhtung04042001, TomOwO, SeehtEntity for their problem ideas and for helping us prepare the problemset.
EternalFire, SucculentLover, DeadlyCritic, coderz189, VietCT, EdBarge, hugopm, Combi, TechNite, thenymphsofdelphi, mdinh, Tech.Maniac, mzen, quanpham0805, user202729, Jarjit_sigh, Kuroni, dorijanlendvaj, neko_nyaaaaaaaaaaaaaaaaa, Jatana for testing the problems and providing helpful feedback and suggestions.
MikeMirzayanov for the amazing platforms Codeforces and Polygon.
Finally, we would like to thank all of you for participating in the contest!
We have spent many months to brainstorm ideas, ended up discarding most of them, and finally chosen our best ideas to compose together this contest, so we hope you will enjoy our round! (and hope the Devil's Number won't haunt our round XD)
Good luck, have fun!
The score distribution will be announced later.
UPD1: Here is the score distribution:
Div. 1: 500 — 1000 — 1750 — 2250 — 2500
Div. 2: 500 — 1000 — 1250 — 1750 — 2500
Hope the long queue disappears soon :'(.
UPD2: Congratulations to the winners:
Div.1
Div.2
We apologize for the late editorial. Anyway, here it is: Editorial
Auto comment: topic has been updated by ruanxiaoyu (previous revision, new revision, compare).
how do you edit others post?
I'm coauthor
I was not aware of this feature, but indeed you can now add co-authors of the blog post. Thanks
The question levels jumped a lot from 1st to 2nd. 2 Div.
Hoping gradual increase next time.
Do co-authors receive upvote contribution?
Good question! But the answer is no. I also hope cf will have this feature.
But there are many problems with that. For example, someone may write a blog post and put all his friends as co-authors and they all get free contribution.
The total contribution should be divided among the author and co-authors in some ratio, that will solve the problem :3
https://mirror.codeforces.com/contest/1397/submission/91390761 This is my submission of question div2 B, and it returned the wrong answer in the eighth test case. I changed the compiler to VS C++ 2017, and the result was ACCEPTED! Can this question be judged again?At least, can you tell me where is my mistake? thank you very much. UPD:I changed the compiler to GNU C++14 and GNU C++17, and the results are accepted.
There is one abs() outside namespace std and that abs() doesn’t support long long as argument. Change your code to std::abs() and it should work fine. 91432176
Finally I know where the problem is,It took 421 ms on test case 5, and I finally know why. thank you very much.
hey i have the doubt ,during contest my submission 91394398 got passed through pretest and i got the points of the 2nd question but after the contest ended it says your code fails at test case 27 and the points of 2nd question were removed . So the problem is that if during contest it didn't shows that code is wrong and pretests are passed then how would i able to correct it.
There are pretests(which are tested during contest) and system test (real test, which are tested after contest is over). Pretest passed does not guarantee solution being accepted(= accepted in system test), since latter has larger test set.
my code I get a strange bug in my code: In for loop,I wrote "if(temp<=0)break" to avoid overflow, but it doesn't work. Hope someone can give me explanation,thanks in advance.
Signed integer overflow is undefined behaviour in the c++ specification. This lets the compiler prove that for all defined behaviour that if statement is true (as both temp and p are always >= 1) and optimises the check away (as either the values are small enough to be defined behaviour or it's undefined and the compiler can do whatever it wants).
As a Maripium fan, I want to start an orz chain.
Maripium orz.
Maripium orz
Maripium orz
Maripium orz
Maripium antiorz
Maripium orz
Maripium orz
Maripium orz
Maripium orz
Maripium orz
Maripium orz
Maripium orz
redditforces
Maripium orz
Maripium orz
Maripium orz
Maripium orz
Number of votes are so random
Maripium orz
whoever invented the 'downvote number generator', I'm probably gonna hate him :(
rip contribution
Maripium orz
Hope for strong pretests.
Maripium orz
Will this contest be Lucifer themed?
Unfortunately, this contest won't have any theme.
Shame on you, ruined such a chance
The greatest trick devil ever pulled was convincing the world that the devil's theme doesn't exist :XD
Another missed opportunity...
*Fortunately
I tested this round when I was blue!!! xD
After this round I will be blue!!! xD
666 is the devils number, you will become orange :XD
How many devils do you know that are orange instead of red?
Devil
I guess this is saffron!
How good it'll be if you and me will have the same colour after this round.
Almost impossible! As max rating change for him as per his current performances will be in rang almost -200 to +200 . Same applies to you as well Thus you were close to make that change , for you to reach blue and for him to reach blue there is a sufficient gap of 40 to 50 points. Anyways good luck to you for a big delta change !
positive or negative change :XD
Devil knows!
I tested this round when I was blue (well I still am).
I am curious that how different country people conduct around together! As you are an Indian, the coordinator is from Canada, and the other guy belongs to a different country too!
Well, there are specific Discord servers set up for co-ordination.
its because we people have a wonderful sleep schedule :)
As an author of Round 666, I just want to say that right now I have exactly 666 friends on Codeforces!
Edit: Wow, it lasted a whole 3 minutes! Now I have 667...
Plot Twist: This was a plan to get more friends using reverse psychology
OMG!!!! 666 round, so scared!! OMG
♫ 666 the Number of the Beast
Sacrifice is going on tonight ♫
WOW! palindrome round.
What’s devil’s number?
666 is the devil's number or also referred to as 'number of the beast'
300iq seems like having an Asia tour on Internet and now he is arriving at Vietnam.
Others: " I know coding "
LGMs: " Coding knows me "
Also, 666 is the sum of squares of first seven primes
One more, 666 is the sum of the first 144 decimals of π.
Also 666 is the smallest positive number to have 3 sixes.
Also, rotating 666 by 180 degrees clockwise/counterclockwise gives us 999 which is the smallest positive number to have 3 nines.
And also , (180 degrees rotated 666)-(666) gives us 333 , which is the smallest positive number to have 3 threes.
And also, ((180 degrees rotated 666)-(666))*666/(180 degrees rotated 666) gives us 222 which is the smallest positive number to have 3 twos.
Okay,Now I'm tired. Basically we can generate all smallest numbers having 3 same digits using 666 and it's rotation. :P
left-handed? cringe
Right-handed gang aaaoooohhh! aaaooooh!
You use the mouse with your left hand, on the right side of the keyboard???
Wakanda Style!
I think his right hand was holding the camera.
Hexakosioihexekontahexaphobia is the fear of the number "666."
Hippopotomonstrosesquippedaliophobia is the fear of long words
5 problems and div.1 & div.2 looks like round is going to be tough.
hope pretests passed => main tests passed
It is almost impossible to do that unless you have pretests=tests and 0 hacks or the problem was solved by a very small number of people. For example, look at Codeforces Global Round 9. Here are the FST rates:
A: 24/7357
B: 10/6890
C: 81/5225
D: 35/2046
E: 0/352(pretests=tests)
F: 3/263
G: 1/97
H: 0/7(7 is a very small sample size)
I: 0/0(duh)
Overall, it makes sense to wish for strong pretests(but don't do it in a cf comment unless you want downvotes), but pretests passed -> main tests passed has almost no chance of happening.
Does all hack-Cases are included in main tests or it depends on setter committee to decide which tests to include for system tests?
One of the contest managers needs to press a button to add a hack into the system tests, but I don't think there's any case where that button wasn't pressed.
Thanks for the reply!
rip Devil
six six six
six six six, nice round, :) from VietNam with love <3
nice round :) from LeToan Fan Club <3
How many languages does 300iq plan to master?
atoiz orz
Wow Rated contest after a long gap,Contest is seems to be very Interesting...
Hope for strong pretests.
This is the last contest I can play before school starts. (T_T)
Then I will become Candidate Master!
yo man! i'm still newbie here T.T how can i be like you? :<
YO man! i'm STill mAStER heRe T.t hOw caN i BE Like you? :<
You will see, once you go to school you will learn many new things!
Many new useless things
me when i see the image: chrome translate can translate image ???? :D ???? what is going on ????
Ya, From VietNam with Love. Good luck to the contest and for all
excited for vietnamese contest
vietnamese nha bro :))
ok fine :)
u'll get many downvotes because of speaking vietnamese here bro :v
I didn't think that it's that big of a problem, based on this situation that they can easily find out that I was pointing out his spelling mistake :(
I won't make that mistake again :))
húuuuuuuuu!!!!!!!!
If this round isn't DOOM themed I will lose all hope in humanity.
What is codeforces Round X? is it a new type of round?
I think it implies that the date is decided for the contest but they still don't know if there will be additional rounds before that round, hence they have just named it Round X for the moment. If you see there is 18 days gap between Round 669 and Round X and most probably more rounds will be added in those 18 days gap, hence the name X.
It is 2.5 hr long, so it is most probably a different type of round.
I hope to get the 666th place :)
Here it is! +666
Why score distributions are announced later? I don't know the reason. Can anyone tell me?
Again,the long queue issue ..Waiting my solution to be executed...[user:MkeMirzayanov] Please look into it
Is the codeforces queue long just to make it feel like a bad omen?
Hope your first contest will not be ruined by the long queue issue. I have submitted a solution one hour ago and still, it's in the queue. Hope it will be solved before the contest.
Looks like problems from hell.
Auto comment: topic has been updated by atoiz (previous revision, new revision, compare).
The queue disappeared!
Score distribution looks very scary.
B and C have difference of 250 points only
This indicates two types of round
1. Speed-forces
2. The hard one or unbalanced
Fingers crossed....
round-666 will be my 66 contest :DAren't you and Rudro25 same person?
Queue disappeared :) All the best everyone for the round.
To do well in this contest you have to listen to Iron Maiden not TWICE :P
Hakuna Matata!!
I had already got a correct answer in B at 34 minutes , I resubmitted now and it also passed but my timing has been updated according to present timing. PLease look into this
you'd be judged based on your last submission time for any problem. it's part of the rules
Why this rule? It just screwed my contest.
Why did you resubmit?
It makes sense in ICPC style contests where you get your submission's final verdict instantly to make your submissions past the AC submission irrelevant.
Here, the final verdict is supposed to be kind of hidden until the end of the contest (you might get pretests passed on a wrong solution). Only last submission counts rule is to stop the abuse of submitting multiple solutions hoping one of them would pass.
Meanwhile I cant even solve B
Is there a way to find the number of pretests in a problem?
You can see it in http://m2.codeforces.com/.
Reading E is so fun. haha
This really is a cursed round
Upd: I had insane skill-issue at the time. My bad : )
After this round, I hate 666.
finally some interesting problems i love it!!
Duh
ques2: 2 test case:: if c is 31625 then answer is 1999827749 (10^9-1+10^9-31625^1+10^9-31625^2)
(it is less than given one and it also fulfill all condition)
Are you sure 10^9-31625^2 is positive?
But we can either increase or decrease the number so 10^9 can be raised to 31625^2 by adding 140625
But the cost is 31625^2 — 10^9
Not 10^9 — 31625^2
Pretests for B :(
Wrong answer on pretest 4 :( As the contest is finished, I tried finding a number such that (num^(n-1))>=(biggest element of the array) using binary search and then using this num as C to calculate the answer. Can anyone help.
I did the same! I also tried for mean and weighted mean. What my friend did was nice. From the constraints it can be seen that ans lies from 1 to 1e6, he just did binary search in the entire range.
I used 1e6, still WA
Did the same bro, WA on pretest 4, my output comes smaller :D
Div1 C was really painful
Agreed, statement was very long.
The statement looked so painful that after solving all the other tasks in div2 I decided to quit without approaching it
Disagree. The first impression was indeed painful, but the seemingly annoying parts disappeared quickly. Code is short and contains no strange special cases.
Hmm, my code doesn't look that short. Maybe I'we just done things in a too complex way
contains no strange special cases
I'm very curious as to how you solved this problem, because my solution is case whack after case whack.
Are the cases only on paper or in the code too? Now I'm kind of worried that I'll fail system tests.
The cases are in my code, but I'm not sure if they're actually necessary or I'm just being a clown as usual.
I dare to disagree with you. I think Div1 C was a beautiful dp problem.
what is the pretest 4 of B.. Any guess ???
a really cursed pretest lol
How to solve B?? Should we brute force all possible values of c and then find minimum cost??
Yes
Yeah but how do you set the limit on maximum value of c.My logic gave WA on pretest 4.
Because c^i increases very fast, and the largest value of c is about sqrt(1e9). I brute force all value and exit when the cost is stop decreasing. View submission 91363571
How to solve D?
Greedily. Actually I think it was easier than C
Passed pretest by always choosing the pile with the biggest value. Let's see if it passes the system test.
UPD: It passed.
Thanks. Actually constrains confused me a little bit.
If max_value > sum — max_value answer is T, else answer depends on sum % 2.
I also came up with the same observation but forgot to write simple 'else' keyword in one of the conditionals while implementing, this gave WA and I thought this approach is wrong coz I didn't have a proof :(
Adding up on this, I thought div2D cannot have such an easy solution so I was convinced this is the wrong approach :'(.
Do you know how to prove it?
its more like, if the sum is odd then its T, else u look at your first condition, because the first player can always take an element from the max pile, if the sum is odd then he definately wins bcs they will either take all the stones or when a single pile is left, he will be the one to take the stone from it, making the second player unable to take from it, and if the sum is even, then if the first player doesnt always take the max element, then the second player is left with odd sum and an option to take maximums, so then the second player wins, so the first one has to take the maximums in every step, so if the maximum pile isnt bigger than the sum of the rest of the piles then the second player wins bcs, else the first player wins, this is roughly it
Thanks, this makes sense. Btw how to prove it mathematically?
well, u can prove this more thoroughly by proving the fact that the first player can always take the max, but i dont know how to bring math in here
Approach for B?
Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.
My submission 91391756
Nice problem, like this round
Please don't tell me that the constraints in D were so low only to confuse the heck out of me.
there was a solution in O(sum(a)^3)
Seeing the constraints made me think that the solution is dp. But greedy passed the pretests, can you explain the solution in O(sum(a)^3) ?
sorry, actually it`s O(sum(a)*max(a))
I feel like dumb after i fixed the bug for C that i was missing n = 1, just a minute before the contest. Really painful.
I costed 2 WA for that. Feeling the pain bro
It costed me 4 WAs and gave hell lot of panic :(
What is the logic in Div2 B
for n >= 62(max size of long long) the answer should be sum abs(a[i] — 1) else you just consider the powers of c till a[max](1 / (n — 1)) and calculate the answer
I got it, but can you please help me in finding x^(1/n). I know how to find x^n but never used x^(1/n) (without using inbuilt pow function)
I guess you can use Newton raphson's method or similar iterative approximation techniques
Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.
My submission 91391756
Div2 C was by far one of the most interesting observations used on an ad-hoc problem.
Div2 C was a pretty darn clever problem, ngl
There was a similar one in a global round! Couldn't do it then!
Upsolving helped :D
I mean... You can't say "by far" and then say "one of the..." xD
It was a super cool problem!
"By far" was for me... "one of the" for the more experienced people. Didn't want to declare something without allowing public opinion. :p
"It can be proved that the solution is always possible". Imagine if that hint wasn't there!
Let's hope the main tests pass :P
Could not solve even B this time :( Any idea on how to do it
Could not solve even B this time
You're Not Alone.
a real relief to find that an expert(not for long time xD) is with me.
Sort the numbers ascending. Now if the list is like really long, like over 50 elements, the only c you have to consider is c=1, even for c=2 the last c**i will be way to big.
For arrays under 50 elements, one can brute force all possible c numbers up to 10**5 and pick the best one. The search for c can be optimised using stricter upper bound and binary search but with generous time limit its not needed.
I implemented the same n=50 approach. Dont know what went wrong ;/
thanks ! i will try this method.i was trying to reduce the value of c by using value of n.Don't know why it gave WA on pretest 4 though
How can you use binary search?
Lets say the biggest c I have to consider is 10**6.
I will start with c = 500_000, calculate the absolute difference and then I will check c=499_999 and c=500_001, if c=499_999 is better and c=500_001 is worse then it means I am overshooting, and have to reduce the c.
Next I take c=250_000, check if I am overshooting or undershooting by checking c=249_999 and c=250_001, if I undershooting next c will be 375_000 etc.
So like a slightly modified binary search with gradient checking.
Can you prove that the function is increasing (for you to return true or false even with gradient checking)?
I'm not sure if i'm convinced.
Me too, 3rd problem was clever though!
I'm sorry guys, but Div1 C killed this round for me. The idea is straightforward, but dealing with all the details was too hard for me. Besides, I noticed that $$$r_1 \le r_2 \le r_3$$$ only 15 minutes before the end of the contest :(
Wow, didn't even notice it till the end, wrote min statements everywhere to handle cases for that ._.
$$$r_1 \leq r_2 \leq r_3$$$ — what?
Although the solution without this constraint is too complicated as well.
I just noticed after reading your comment. Thanks.
The key observation for me (which I was missing for an hour) was that there exists an optimal solution that's ever only $$$O(1)$$$ steps to the left from the rightmost position reached. Once I got that, the solution became quite manageable.
Div2 B. Im trying to brute force. 1 < i < sqrt(max(list)) But I got TLE on pretest 4
How to approach it?
I used ternary search on $$$c$$$. Passed the pretests.
EDIT: No it doesn't work that way. My solution failed in the real tests. There could be local minimas too, and I didn't think of that.
The correct way to solve it is to notice that you can not have a value for $$$c^i$$$ for any number greater than 2e9. (As you can always select $$$c=1$$$). So, if you have $$$n$$$ numbers then you can find the upper limit of the range of values for $$$c$$$. That is,
. To be more careful, I selected
1e10instead of2e9. So I gotup = pow(10,10.0/(n-1)). Now you can go from 1 toup, and keep track of the minimum abs diff.Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.
My submission 91391756
I did the same thing, Can u tell me where I did wrong? I modified binary search to find that X and used X-1, X, X+1 and took minimum. My submission: https://mirror.codeforces.com/contest/1397/submission/91386048
What was the point of Div1C? It had a really long and complex statement, but once you understood what was actually being asked, it was easy and fairly uninteresting :/
Honestly, I don't see the point of Div2 BCDE either. The difficulty gradient was quite unbalanced.
I implemented Div2 C at last moment is this code correct or still it require something else!
https://ideone.com/HJ3kDp
My idea is first we can make any possible number with two numbers whose gcd is 1. thus for each Ai I was trying to make -Ai. IN 2 operations by using n and n-1 length of segment in first 2 operations. In one remaining operation first remaining value was tackled by me separately thus a total of 3 operations!
Out of curiosity, did anyone manage to get pretests passed on Div 1 C using the +1 / +2 dp and running an exponential brute force at the end instead of handling cases?
Div2 C was nice :) took too much time to solve it
Looks like solving linear congruences a∗x≡b (mod n) was an overkill for C lol.
Can someone explain how to solve it?
Yep. Actually all you gotta realize is that multiples of consecutive numbers can form any number.
So step 1: Select 1 to n, and add -1LL*(a[i])*(n)
Step : Select 1 to n-1 and add 1LL*(a[i])*(n-1)
Now numbers 1 to n-1 must 0 by now. You can make the nth number 0 by adding (n-1)*a[n-1].
What a clever solution!!!
For C: If we can make all a_i multiple of n then we can make all of them 0 in one step using -a_i.
Now, a_i+(n-1)*a_i=n*a_i So if we select segment with length n-1 then adding (n-1)*a_i will make all element divisible by n.
Using this we can make all element divisible by n in two step and finally 0 in last step.
You should handle overflow issue and n=1 case carefully.
Devil fooled me with div2A
Someone, please explain B and C. In B I iterate over constant c until power(c,n) <= 1e18, and permutation I choose the sorted one.
For C: If we can make all a_i multiple of n then we can make all of them 0 in one step using -a_i.
Now, a_i+(n-1)*a_i=n*a_i So if we select segment with length n-1 then adding (n-1)*a_i will make all element divisible by n.
Using this we can make all element divisible by n in two step and finally 0 in last step.
You should handle overflow issue and n=1 case carefully.
Thanks, Got it! Can you tell me what's wrong in my B approach...
I will see it once i solve B successfully.
For B : Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.
My submission 91391756
What was the answer for Test case 2 ? The 10^9 one , I Mean the number they were power of ?
31622 and 31623 are the closest to 10^9 and 31623 will give us a minimum for 31622 2000017493, for 31623 1999982505
Problems B and C gave me PTSD.
Could someone please tell what is the problem for my soln to B?
https://mirror.codeforces.com/contest/1397/submission/91418834
Oh, sorry, im wrong. I forgot that n > 2
How to solve Div2 D ??
On every turn the player should pick the biggest pile, if he can't, try the next pile, if he still can't the other player wins. you can just simulate the process.
Some people complained that the pony round had long problem statements
Ha-ha.
Look at Monster Invader. That is how you write long statements
For correct solution, the timing is updated ,for incorrect it is not updated. Why the rule that the recent solved timing would be considered ?I solved Problem B nearly 30 min from the contest and then at last just to conform ,it resubmitted it with a small change so that it does not fail system test and it updated my timing. Why not make it something like If the first correct attempt fails, then the next one is considered. Also for who are new to codeforces at least the link of the rules could be included in the contest posts.
Link to the rules is there when you register.
I actually register just 5 minutes before the contest seeing whether I could give that round or not
You make changes so that it does not fail system test. So your first solution is potentially not correct. So I surely agree to the rules.
And if someone makes wrong submission then is he not doing changes.
Why not make it something like If the first correct attempt fails, then the next one is considered
Then everyone will submit multiple solutions to 'secure' AC.
You can then also charge him for his previous wrong submissions.
If you do not want you do not have to submit twice.
I will remember it from now.
"Why not make it something like If the first correct attempt fails, then the next one is considered"
Yeah. And if this one fails too, let's move on to the next one. Let's give participants infinite number of attempts to bypass system testing in case they're uncertain.
"And if someone makes wrong submission then is he not doing changes."
If someone makes wrong submission then this solution is definitely not a candidate for system testing. And I believe in most of the cases it is a mistaken submission of a completely different task
If the test cases are strong then obviously only correct solution will pass which don't pass can be skipped in system tests.
Thinking that strong pretests cover all possible cases and give you absolute guarantee is a plain bullshit and naivety
One hacked solution does not mean pretests are necessary bad. It just means that the solution is hacked. No more, no less. Similarly with system tests.
I got your point thanks
I've written a fairly straight-forward brute for B.
Could someone tell, if i'm missing something? Solution Failing on TC3
[deleted]
I have put a break condition in case the c^i overflows. also, since the biggest c is 10^5, a negative check for overflow should have done the job.
Found the mistake! The negative check is wrong! It'd overflow multiple times
Was I the only one to not attempt Div-1 C seriously initially considering its low number of submissions in the beginning?
Who else skips a heart beat when you go to the Dashboard during system tests and you see RED on your problems? (and 1 second later realize/remember it's just the bad attempts).
Although I couldn't solve C, looking at its solution, I can say it's a pretty cool ad-hoc problem.
problem C: Help Dora to find all the ways to beat the level
I misunderstood Problem B and tried solving it taking into consideration a different c for each a[i]...
Please, A quick editorial
Weak pretests = Many hacks = (Actually not super) long systest queue($$$3$$$ pretests, $$$60$$$ systest for $$$A$$$...)
Anyone interested in hacking my code, Here's the testcase : 3 1 1 1
Weak Pretests guys :(
If the number of occurrences of each letter is a multiple of $$$n$$$, the answer is
YES; otherwise the answer isNO.Try small values of c. We know that the value of c is too large when the difference between the largest element and $$$c^{n-1}$$$ exceeds the cost for $$$c=1$$$. Be very careful because if n is large, even $$$c=2$$$ can overflow
long longtype.Let's use two operations of length $$$n-1$$$, and one operation of length $$$n$$$. The first operation covers elements $$$[1, n-1]$$$, while the second operation covers elements $$$[2, n]$$$. During the first two operations, we make all elements of the array multiples of $$$n$$$. This can be done by adding $$$(n-1)(a_i\ \mathrm{mod}\ n)$$$ to each element once. Then we can make all elements zero in the third operation.
The case $$$n=1$$$ needs to be handled separately.
If the largest pile contains more stones than all the other piles combined, then the first player wins. The first player always takes from the largest pile, forcing the second player to take from the rest. The second player will run out of stones before the first player.
Otherwise, if the total number of stones is odd, the first player wins; if the total number of stones is even, the second player wins. This can be proven by showing that either player can preserve the property that no pile contains a majority of stones, thus forcing the game to end only when there are no more stones. (The other ending is when there is only one pile remaining and the other player just took from it, which makes the pile contain every single stone, and thus a majority of stones). When the other player changes the state of the game from "no majority pile" to "majority pile", the majority pile only contains one more stone than the rest combined, and one can take from that pile to return to the "no majority pile" state.
We decide, for each level, whether we will be forced to teleport out of the level (requiring us to reenter it) or not. Do a DP, where the state represents the level we are at, whether we are forced to teleport out of the current level, the number of teleportations going into the current level from the left, and the number of teleportations leaving the current level and going left (there are several constraints on these values).
I do not like the way this problem is phrased. If is too long and can be highly confusing. A much better way to phrase it would be something like:
There are $$$n$$$ levels. When you enter level $$$i$$$, you may either spend $$$a_i$$$ time completing it, or you may spend $$$b_i$$$ time partially completing it. If you choose the latter option, you must leave the level after $$$b_i$$$ time units, and return to the level at a later time, and spend an additional $$$c_i$$$ time to finish the level. One can move between adjacent levels in $$$d$$$ time. Find the minimum time needed to complete all levels.
IN div2 B I calculated (n-1)th root of largest element ad tried from 1 to that value plus 2.whats wrong with that. I also sorted the array to calculate the cost.
It is possible for the largest element at the end of the process to be much, much larger than the largest element at the beginning. See my comment above.
In addition, be careful about overflows.
For B : Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.
My submission 91391756
For D2C/D1A we can also use one operation of length n, subtracting n*a[i] from all elements for 1 <= i < n and adding 0 to the last one. Then one operation of length n-1, adding (n-1)*a[i] (initial value of a[i]) to all elements for 1 <= i < n. The last operation will be of length 1, applied to the last element, subtracting it from itself. (And the case with n=1 should be treated separately with any approach. For example subtract the only element from itself in one operation, then add 0 in the subsequent two operations.)
tourist exorcised the devil.
Am I the only one really bothered by Div1 C statement?
At first, I thought "he" referred to the boss, who would flee if not killed. This was enforced by the next sentence (the boss is forced to do something. Ziota can also choose to do it).
The wording in the sample is also unhelpful:
We? Ziota was in third person singular throughout the problem statement, why use "we" now? Ziota and the boss?
The statement is "correct", but these things get hard to read if you're not a native speaker and are reading in a hurry during the contest. Why not use the character name?
After re-reading the problem many times I submitted a suggestion the change the use of "he" for the character name, which got "No comments". I wished it could have been updated, so at least others wouldn't spend time figuring this out.
Well I only read the problem and I did not read it your way. I think it's about computer games logic, and that's why it passed through all the testers... For some reason you assumed in your head that Ziota is the feared, all powerful being, but that's usually the boss.
If you are playing a game and you reach a super strong boss that kills you with ONE SHOT, and you miss a shot (or hit but not kill), who runs away afraid? you or the boss?
Usually all you do is run and dodge while the boss attacks...
(I literally imagined teleporting between worlds making a single shot and continuing to teleport. I have a clear vision of this computer game in my head LOL)
Having a 1 HP boss run behind other small enemies isn't that unreasonable. And again, during the contest it's easy to misinterpret the statement if it's a bit ambiguous and you're not a native speaker. I don't see why they wouldn't change it
what is meant by reorder in question B??????
You can reorder a[]
That means you can swap any pair of elements and sort the whole array for convenience.
My solution to Div2 C was to just simulate every player choosing pile with max number of stones (among available ones).
I'm still not 100% convinced, but it passed pretests (soon I will see if it passes the main tests).
I used this solution as well. Looking at others' solutions, it seems that another approach is to say that player 1 wins if there is a pile with size at least all other piles combined, otherwise determine the winner by the parity of the total amount of stones. I believe it can be shown that the two approaches are equivalent.
I think the idea is that a player can claim "ownership" of a pile because if the only take from that pile, the other player can never take from it due to the rules. So, if a player takes from the non-largest pile, it could lead to a situation where the largest pile > sum of the other piles.
So if a pile > sum of the other piles (this must be the max pile), take from that pile. The other player can never take from that pile. Otherwise, never make it so that the max pile > sum of the other piles, which you can do by always taking the max pile. Then it just comes down to parity.
But how to prove that if sum of the max pile is less or equal to other piles combined "HL" will always win?
HL won't always win, it depends on the parity, you can prove it by induction.
Suppose we have $$$x$$$ stones for some even $$$x$$$ and that the max pile is not bigger than all the others combined. If $$$x = 0$$$, the proposition holds trivially. Assume, by induction, the proposition is true for all arrangements with $$$x - 2$$$ stones. Then, no matter which pile T chooses, HL can always choose another one such that the (possibly new) max pile is not bigger than all others combined. Moreover, after this we'll have $$$x - 2$$$ stones. By the induction hypothesis, HL wins.
What is the approch for div 2 B
We can simply try all possible numbers for C.
This is possible since if n is big, there are only very small numbers for c possible, and if n is small we can actually try all possible C. (max sqrt(1e9), ie 1e5)
Can you please explain the intuition behind max sqrt(1e9) ?
If n==1 and n==2 the solution is trivial, if n==3 the max possible value for c is "a little bit more" than sqrt(1e9), because 1e9 that is the max value a[2] can have. For bigger values of n the max value of c is smaller.
Find (n-1)th root of the maximum value in the array. This will be double type value so you have to add 0.5 and then take the floor of that so that value gets rounded off properly. This value is c for our array then calculate the sum of the absolute difference of a[i] and c^i for all.
I should sort the array first right bfore calculating abs difference
yes
I tried calculating the (n-1) th root of largest element and than looped c from 1 to that value+2 and tried minimum cost. But i got test case 4 wrong. Can it be becouse of some overflow. I was using long long
Start by calculating the score for c=1, it is the one that will certainly not overflow long long in any case. Then, taking larger values of c, the score may first decrease (this may be the case for small values of n), then increase forever after passing the minimum, or it can immediately increase (for large n even powers of 2 will already overflow), the score for c=1 being optimal. So iterate over c values starting from 2, continuing while getting answers smaller than the current optimum, and in the first instance when the current optimum is exceeded interrupt the search, we are past the turning point.
I think that too might cause overflow. I came up woth a formulaa to find the upper limit upto which i should consider c.
double x=pow((double)(arr[n-1]),(1.0/(double)(n-1))); ll st=floor(x+0.5); ll ans=LLONG_MAX; ll c=floor(pow(10.0,17.0/(double)(n-1))); for(ll i=1;i<=min(st+2,c);i++) { ... }this worked for me
When calculating a given next candidate score, interrupt immediately after getting a (possibly intermediate) value larger than the current optimum, no need to calculate the full score, if it is already too large. In this case it should not overflow. Code for reference
Suppose the previous_optimal is x and we are in the process of finding the current_optimal and current_optimal current value is < x. How can we be sure that the next value(candidate) added to the current_optimal will not overflow current optimal as if it will overflow current_optimal then current_optimal can be < prev_optimal after all the overflows.
I Think Div-2-B was pretty hard for newbi contestant like as me ☹️
Mastering puzzles is really necessary to be good at CP? Is it?
Anyone else solve Div 1C/2E without realizing r1<=r2<=r3?
OOPS
I think I've seen this during the contest, but my solution ended up not caring about it)
I wouldn't say this round is bad by itself, but I really expected something special prepared for #666
Found out that my A failed system tests because I wrote
for(int i = 1...when I was supposed to writefor(int i = 0.... Almost 500 points blown away for nothing :PI know, for interview preparation, there is leetcode. But sometimes I wonder, will the problems in Div 2, like A,B,C, will they really help me in interviews, as they are just some tricks. You understand the trick, you get AC, else not. More of a mind game type. Can someone answer this?
Let's just say it's not the most optimal way to prepare for interviews.
(a + x * b) % n = 0 can anyone tell me what will be value of x (here b is prime) ??
http://rachitiitr.blogspot.com/2016/12/solving-linear-congruences-ax-equiv-b.html
Problem set was really good. Div2(C) was tricky and one of the best one.
How did you solve Task B?
Sort whole input array.
Find (n-1)th root of the maximum value in the array.
This will be double type value so you have to add 0.5 and then take the floor of that so that value gets rounded off properly.
This value is c for our array then calculate the sum of the absolute difference of a[i] and c^i for all.
Formula to calculate kth root of n : pow(k, (1.0 / k) * (log(n) / log(k)))
What is the intution behind this?
Any resources for this concept?
how do you prove that that's the best C . edit : you failed main tests, F
A brute force solution works. Store the best seen cost so far. For each power from 1 to 33000, you can stop the evaluation when the cost becomes worse than the best so far: https://mirror.codeforces.com/contest/1397/submission/91374026
For B : Sort the array in ascending order and find the two value of X(ceil and floor) for which pow(X,(n-1)) is closer to the maximum value of the array. Let say you have an array [1,2,7] so the number whose (n-1)th power is closest to 7 are 2 and 3 (pow(2,2)=4 and pow(3,2)=9) now take these two values and iterate in the array and calculate what is the answer if we take 2 and if we take 3 and then print a minimum of these two.
My submission 91391756
How to avoid long queues? Answer: write a problem like B with like 5 pretests and run the contest
(yes I'm frustrated :p nice contest otherwise imo)
I felt humiliated by Div2 C
Haha same. My code worked after a minor fix when a number is 0.I could've gotten it in contest had I remembered that 0 is not a multiple of n!
0 as a multiple works. It was part of the clarifications.
You cannot add 0 I thought. I changed just that (and removed unnecessary base cases) and it worked. 91407141 91423874
It seems your error was not printing endl in every line when n == 2.
Thank you! I see now. Very sad about that problem now :(.
Anyone else who lost motivation to solve Div2 E just by seeing the size of problem statement?
Is #667 (Div. 3) going be rated?
Yes..
Were pretests really weak today? Can't believe both A and B failed system tests.
Great contest..
Was it only me or n=1 troubled many in problem C ?
same here
Great contest, problem setters! A question though.. Do you folks intentionally make weak pretests (for A in my case)? I'm asking this because, I made a substantial blunder in A, and somehow the pretests still passed for me(and then, it failed in system tests).
I have a wrong solution for Problem D. And it has got Accepted after system testing. 91418247
WA case:
1
2
1 15
For div2 B, how do you prove that simply sorting gives the best permutation?
like consider the GP as 1,c,c2,c3 and the sorted araay be a0,a1,a2,a3.....an you will make ai-->ci else if difference of a(i+1) and ci is less than that of ai and ci then you have to transform ai to a much larger no. which will not be optimum. this was what i used and am not sure whether is correct or not.
let's say you want to make your array to exist on a number line
<------c^0---c^1----c^2--------c^(n-1)--> This is required array for a particular value of chosen c. Cool.
Now lets say your array contains a1, a2......an-1. on a number line. Now the mapping we chose is to map minimum value in a to minimum value in c , and so on. lets say our array is sorted a0<=a1<=a2.....Now we will prove why we chose the sorted order as follows. Say at any point ai> ai+1. By contradiction and you matched ai to say c2 and say ai+1 to c3. lets say ai+1< c2 <c3<ai. And if we tried matching ai+1 to c3 and ai to c2. then see the segment between c2 and c3 is included twice which is not optimal.
>>>>>>>>>>>
| |
ai+1.....c2----c3----ai.
| | >>>>>>>>>>>>Hence it is always it is viable to map with nearest value.
Exchange argument should work. If our target values are $$$x$$$ and $$$y$$$, $$$x \lt y$$$, and we have two value $$$a$$$ and $$$b$$$, $$$a \lt b$$$, matching them in sorted order will cost us $$$abs(x-a) + abs(y-b)$$$. If instead we match $$$x$$$ with $$$b$$$ and $$$a$$$ with $$$y$$$, we need to prove that the cost can't get any less
Case 1: $$$b$$$ < $$$x$$$ or $$$a$$$ > $$$y$$$
Then the total cost doesn't change. One will cost less by $$$b - a$$$, and the other will cost more also by $$$b - a$$$.
Case 2: $$$a \lt x \lt y \lt b$$$ or $$$a \lt x \lt b \lt y$$$ (similar case if $$$x \lt a$$$)
You can draw the four values in a line and it should be clear that matching $$$b$$$ with $$$x$$$ is going to result in more cost.
We can prove a more general statement.
Given two sequences $$$a$$$ and $$$b$$$ with the same length $$$n$$$ and $$$b$$$ strictly increasing find a permutation $$$c$$$ of $$$a$$$ such that $$$\sum \lvert c_i - b_i \rvert$$$ is minimal.
We claim that the optimal permutation is non-decreasing.
It is easy to prove it for $$$n = 2$$$ by considering a few different general cases. For $$$n \gt 2$$$, assuming that $$$c$$$ is not sorted, we can improve the sum over any two elements that are not in order (and the total sum) by swapping them. Repeat until c is sorted.
My B , failed in main test cases :(((
the contest must have been cursed
BINOD.
bhakk bsdk
https://mirror.codeforces.com/contest/1397/submission/91390761 This is my submission of question div2 B, and it returned the wrong answer in the eighth test case. But the result I run locally is indeed 912788665, what's the problem? I changed the compiler to VS C++ 2017, and the result was ACCEPTED! Can this question be judged again? And I'm curious where is the mistake?
It could be
undefined behavior, but I have no idea where it is...Changing the language to
C++17solves the problem.Thank you very much, I am still trying to find the problem, I changed the compiler to GNU C++14 and GNU C++17, and the results are accepted.
If you change your abs() calls to std::abs() it'll pass. The abs() that is available outside of std is the c version (which means no overloads) and takes int arguments so your values get truncated. This has been changed in newer compilers to include the overloads outside of std as well but you are choosing an old compiler.
Finally I know where the problem is,It took 421 ms on test case 5, and I finally know why. thank you very much.
div2D/div1B defeated me... I still don't have an intuition for it... but I should have just tried it anyways.
My B and C both failed on system testing
vary sad contest for me....
Teach me to read pls(
Can anyone please tell me why is this wrong for Div2 A?
I think this won't even pass the example case. You used while(n--) so at last n will be zero, so mod n is always zero therefore the output would always be all YES (I think?).
Use for(int i=0; i<n; i++) instead
You are decrementing variable 'n' in while loop . Then using the same variable to check if else conditions , it's not going to work . Use a 'for — loop'.
Anyone else who solved 2C using extended Euclidean algorithms like me? :(
Suffering from success
I was about to. But then I figured out the numbers. :P
Check this out 91366270
Looking forward to seeing the proof for the solution of Div2 D...
man problem C was so fucking beautiful, Sometime i just don't get it ,why I can't catch these problems, fuck ups after fuck ups. Man cp can really hurt dumb fucks like me.
This is not CP . These are off the charts tricky ad hoc "you are lucky if you guessed it right in the first few minutes" problems.
((n*k)-k)%(n-1)==0 ,how can say it just guessing ? it was a really good problem.
Lol thats not how cp works. Observation is key in cp
Uhh more like trying one thing after some other thing after some other thing until something works.
The better one is at keeping a problem in his / her brain, the faster they can solve some problem.
What wrong with my 91425950 for problem C in div2
Checker Log wrong answer Integer -1 violates the range [1, 4]
thus for the sample, why the following is wrong answer atoiz
Output two integers as range for each operation, even it only contains one element.
Thanks!
oh my god, stupid dna049!!!
Question C in Div 2 — Multiples of length.91406408 On system Testing it got Time Limit Exceeded (on TestCase 70(last test case) ) verdict but now on running its displaying AC Verdict. What to do?Can anyone help?
atoiz[user:atoiz] Help needed with this.
Your solution passed with 998ms out of 1000, probably with internal retries. It is perfectly normal that problems have some fluctuations of the execution time. And it is certainly not a reason for rejudgement.
Your practice submission used $$$998ms$$$, which is too close to the time limit.
It's normal that the time your program used is different for each time.
Codeforces rejudges submission which got
TLfor several times, and sadly your solution failed on all of them :(3 times WA is huge demotivation. I was like, ratings can go to hell, I am not solving it :D
Please make the round unrated
Yes, the test cases weren't great but that doesn't justify making it unrated. It is the contestant's job to ensure that his/her solution is correct.
LMAO
My approach for problem E:
First we decide for each edge how many times it is passed through, then we could easily construct a matching using bottom-up.
It is easy to see, that a sequence of numbers (of times an edge is passed through) corresponds to a perfect matching if and only if : for every node $$$u$$$ (suppose its adjacent edges have numbers $$$a_1,a_2,\ldots,a_d$$$), the conditions $$$(\sum a_i)\bmod 2=1$$$ and $$$2\max\{a_i\}\le (\sum a_i)+1$$$ hold.
Starting from $$$a(u,v)=\min\{size_u,size_v\}$$$, each time we decrease the maximum value by $$$2$$$. It's obvious that the conditions above always hold (until some $$$a(u,v) \lt 0$$$). We want the sum of $$$a(u,v)$$$ equals to $$$k$$$, so we can use binary search to find the final sequence.
The overall complexity is $$$O(n\log n)$$$.
I don't know why this solution is giving Runtime error : Wrong Answer!! whereas the same code with if-else condition is accepted : Accepted
Someone please explain it!! As I am losing 50 points because of this.
You should always return 0.Returning different from 0 means the program exited due to error or anomaly.
This is strange and disgusting!! I compiled it on my system and it was showing correct output.
This is not strange at all. Program returning 0 signals the program runs properly. Other return values signals the program not working properly due to incorrect input, memory issues, etc.
Thanks!! I learned something new and will try not to repeat the same mistake again!
Hexakosioihexekontahexaphobia is the fear of the number "666" .
I declared 25 size array for 26 characters.
I deserve weak pretest.
DIV1 B and DIV2 B should have been swapped
Not sure about that, div2B seemed straight forward to me. I solved div2D/div1B without being sure about its correctness. Sometimes correctness of greedy algorithms is hard to prove.
can you explain the logic for div2 B?
Sort the array $$$a$$$ and calculate cost for $$$c = 1,2,3,4,5,......$$$
Stop iteration when the cost for current $$$c$$$ becomes greater than the current minimum cost. Because current $$$c$$$ and any greater $$$c$$$ won't give a cost less than the current minimum.
Why did my first submission 91409058 printed some random negative number? I just replaced printf with cout (91412283) and it worked correctly. atoiz
You use %lld to output an integer. You should either store n as long long or output it using %d. Also, don't use cin mixed with printf. Use printf and scanf / cin and cout.
The output was displaying correct on Codechef IDE.
Your code might work in some ide because it is undefined behaviour. Anything (e.g. crash, output the thing you want, or in this case, output the wrong answer) can happen if undefined behaviour exists in your program.
c99 Standard: 7.19.6.1: para 9:
If a conversion specification is invalid, the behavior is undefined.225) If any argument is not the correct type for the corresponding coversion specification, the behavior is undefined.
Thanks man. When you mentioned that para 9 thing, it felt like a verse mention from Holy Bible :D
The problems are tricky but they are good.
Why this submission 91375766 gives runtime error on test 3 I ran the code on my machine and it gave me the correct answer
I used INT_MAX to set limit for long long int type data.Press F for me. Got WA in div2 B
F
When will rating be updated
Can someone please explain to me the exact score decline function for problems? And how a wrong submission penalty affects it?
I can't find it anywhere and I would really love to know the gravity of every passing minute or wrong pretest submission.
Score is decreased by (maxScoreOfProblem)/250 per minute. Wrong submission reduce score by 50 and the formula can be found in the rules when you enter a contest.
Check this out : https://mirror.codeforces.com/blog/entry/4088
DIV2 B solution without using log to calculate upper bound : 91433534
Can someone prove the correctness when using greedy to solve the DIV1B? THX~
I just realized how ironic it is that today of all days I started to watch Lucifer on netflix... it's ok. I'm a little scared it's just another crime show.
Genuine question: if the problems take months of preparing, with lots of time spent writing/testing and scheduling, why aren't the editorials immediately ready after the contest? Isn't there plenty of time to write it between conception of the problem and the contest date?
Rating Update!!!
why is there no change in my rating after participating in 666 div 2?? I solved one problem but there is not even +1 or -1 , exactly same ..have the ratings not updated?
Yes indeed, the ratings aren't updated yet. Wait for it and it will update soon.
quite strange...they always got updated after the system check..anyways thank you!
No that's normal don't worry. It happened before many times. Usually I check rating changes the next day haha xD
If you really want to know a prediction of your rating changes, you can install "CF-Predictor" it's an extension for web browsers that predicts your rating changes. it's quite accurate.
Here's the link for the extension for chrome link
install it and then check the standing page you'll see an additional column that contains the rating change.
That's so cool!! Thank you so much for the suggestion, I'll surely try it ;)
You are welcome ^_^
I faced this issue of signed integer overflow, where I can easily see passing the same code for test case 17 in my machine but failing here. I am using G++17 latest on my machine. I couldn't find any solution that what is different with codeforces C++17 compiler. My submission link
When will rating be updated?
Can this comment reach 666 upvotes?
-666 maybe
Yeah :(
[problem:B — Power Sequence] [contest:Codeforces Round #666 (Div. 2)]
Mistake by CodeForces Judges!!!!!!!!!
In Problem B under test case no. 56:
p.s : I have used this headline just for attention on my doubt.. No offense on headline please. Thanku for ur replies.
Can't see TC 56
Submit your solution again
your int is overflowing which is giving a random value, if you change it with long long , it will come out to be greater than the judges' answer. Please read the c++ diagnostics on ur submission ... smh
You are incorrect. I tested it locally, if c is 2 then cost will be 4516192768. Also check twice before making such a huge statement
According to my calculation, the cost for the 2nd case is coming as 4516192768, which is greater than 4073741790. Kindly, check your calculation.
can someone give an explanation to why the Div2 D depends only in the parity if there is not a pile bigger then the sum?
I didn't participate officially in the competition yesterday (12:35am for me), but read the questions and my solution sketch for Div2D/1B is as follows:
Let S represent the sum of the piles of stones and let M be the max number of stones in one pile. Let R = S-M be the remainder — the number of stones in the other piles.
If M > R (2M > S) then the first player wins: they repeatedly take from the M pile. The second player is forced to take one of the R stones from another pile. After 2R moves, there is only one pile remaining with M-R > 0 stones; the first player takes from this pile and then wins.
Otherwise, if M <= R, we take two cases depending on the parity of S.
Let's first look at S odd; let S = 2P+1. Firstly, the first player should take from pile M. Then there are S-1 stones remaining. We can create (S-1)/2 = P pairs of stones such that each pair comes from two different piles. This can always be done by creating a pair between the two piles of greatest size. By doing this pairing, no matter what move player 2 does, player 1 can always pick the other stone in its corresponding pair. Since player 1 always has a move/response to player 2, they will win.
On the other hand, if S is even, then player 2 does this pairing strategy immediately; they have an answer to any move that player 1 does, so since player 2 can always move, they will win.
We can see why this pairing strategy doesn't work if M > R (like in the first case) — we're not able to create all the pairs because the pile with max stones has too many stones in it; if the remainder is R (R = S-M), then you can create at most R pairs.
How will we maintain the constraint M<=S/2 when we remove a pair from smallest 2 piles? Then, only S reduces and not mx.
Thank for the contest but I want to ask a problem happen with me: I submitted it 6 times in problem B. The 6th time I was accepted, but when I reviewed the results, no results for my 6th submission and no grade for it. I want to ask why is that? I submit when time have 50 minute left. Have someone know this problem?
Your code could've passed the pretests, but probably didn't pass system tests, which happens once the test is over.
hey guys. i have a problem about 1397B - Power Sequence that i dont understand, hope someone can help me :)
this submission 91447181 is wrong at test 44 , because variable "power" is int and overflow happens. when i change variable "power" from int to long long , which is this submission 91446926, its wrong at test 4 and i dont know why.
sorry for my poor English by the way.
We cannot go above the required c as it will always result in overflow For eg as in test case 4 N=100 so the appropriate c is 1 but in your code, you are also computing it for c=2 also and then comparing, for c=2 it will always have overflow(2^100 is large).By using power as int you were lucky as it resulted in greater value(at c=2 after overflow)than previous. Whereas for long long you got smaller value(again after overflow).So we cannot go to 1 higher value of c. My code for reference https://mirror.codeforces.com/contest/1397/submission/91450164
I like this contest. :)
In problem D of div2 can anyone help that for pile 2 1 3 2 how they are going....
according to me,
1st player chooses 3 in 1st turn and removes only 1 from this
2nd player chooses 2 in his 1st turn and removes only 1 from this
1st player chooses 2(new) in his 2nd turn without making empty the 1st pile he chooses of 3
2nd player chooses 1(new) in his 2nd turn without making empty the 1st pile he chooses of 2
then player 1 empty his pile from 3,2 one by one and similarly player 2 from 2,1 pile and player 1 has more number of the pile to remove so player 1 wins
Since they are playing optimally
2nd player chooses 1 in his 1st turn then u will get Player 2 wins always
Can you explain more?
I think you assumed that a pile chosen by player 1 in any of the previous turns can't be picked.
But according to the question the pile chosen in the most recent turn can't be picked all others can.
So, according to the moves mentioned. 1 2 2 3 --> 1 2 2 2(P1) --> 1 2 1(P2) 2 --> 1 1(P1) 1 2 --> 0(P2) 1 1 2 --> 0 0(P1) 1 2 --> 0 0 1 1(P2) --> 0 0 0(P1) 1 --> 0 0 0 0(P2)
So P1 has no piles left to choose.
Oh only pile chosen in the last round can not be picked
I saw many people pass 1B with a O(n) solution.I just know O(sum log sum) where sum = $$$\sum a_i$$$.Can somebody explains it?
due to a small doubt i resubmitted my solution for question A , but during system testing my first solution was skippped , though it was compeltly correct.Can i get any help regarding this.After the contest i checked my previous submission , it was also an accepted solution.Please help . Link for resubmitted solution: https://mirror.codeforces.com/contest/1397/submission/91394792 Link of skipped solution: https://mirror.codeforces.com/contest/1397/submission/91357472 Link of skipped solution which was also an accepted solution : https://mirror.codeforces.com/contest/1397/submission/91424283 please help with this, i got -106 due to this blunder.
I am still eagerly waiting for that UPD : Editorial is published !!! Anyone Else still waiting ?
oh god where is the tutorial?
submission:(http://)https://mirror.codeforces.com/contest/1397/submission/91449160
why it is showing signed integer overflow on the line 43 thank u
in your binpow, if the value of b is very large, like around 1000 and even if your a is as small as 2, the values will overflow.
then what is the solution sir
I think inside your second for loop after calculating ans just check if ans<0 then assign ans= +infinity and break the loop. Your code will work fine
div2D's easy solution
can you please give your proof? mx part was easy but I can't think of the sum&1 part
If $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}$$$ is even, then we can pair all the stones on the table into pairs so that each pair contains stones from two different stacks. (We can do it e.g. by repeatedly removing two stones from two highest stacks and pairing them together; we can prove that the conditions $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}\%2=0$$$ are satisfied throughout the process.) Then, the second player has a winning strategy -- whenever the first player picks some stone, the second player removes the other stone from the pair.
On the other hand, if $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}$$$ is odd, then the first player removes a stone from the highest stack. Then we can convince ourselves that we now have that $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}$$$ is even, but now the second player is to move. Hence, the first player wins.
It appears that this part of the solution is arbitrary:
But it is nice to remember that this condition holds if and only if $$$\mathrm{mx} \leq \frac12 \mathrm{sum}$$$ and $$$\mathrm{sum}\%2=0$$$; this is quite useful e.g. in game theory or some optimization problems.
Thanks a lot! Elegant proof.
stoned game problem is very much similar to CF round 577 div 2 B. If you submit that problem solution just changing YES->HL and NO->T, you will get AC.
We can consider each stone as a vertex, and each pair of stones from two different piles are connected by an edge. The first player chooses an arbitrary vertex, and in each turn a player chooses a vertex that wasn't chosen before and is connected with the vertex chosen in the previous turn. It's the well-known theorem that the first player loses if and only if the graph has a perfect matching.
My solution with explanation for problem E: https://mirror.codeforces.com/blog/entry/82130
Since the editorial is taking so long, would anyone who solved Div1D share how they solved it?
Brief editorial: For every x,we enumerate y from 0 to L.Suppose the left-bottom vertex of matrix is $$$(x,y)$$$ .We maintain an array $$$a_{x \dots L}$$$ ,means $$$(i,y_2)(y_2 \ge a_i)$$$ is an legal right-top vertex.We may erase some candy during enumerating y,so there will be some events like $$$(l,r,y')$$$ ,means for $$$l \le i \le r$$$ ,$$$a_i=\max(a_i,y')$$$ .We can enumerate y from L to 0 and maintain a set for every color to get the events.The total events number is $$$O(n)$$$ .Use segment tree to maintain $$$a$$$ ,time complexity is $$$O(n^2 \log n)$$$ .
Here is my code. I use map to maintain $$$a$$$ instead of segment tree to simplify the coding.
Hello everyone. I had a submission 91458515 which fails on the problem B but a similar submission 91458087 passed. The only difference between the two is — in one I assign the initial answer as 'LONG_MAX' and for the other, it is '1e15'. This should not break the solution to my knowledge. I may be missing something. If someone can point out the reason it would be very helpful to me.
Use
LLONG_MAXinstead ofLONG_MAX. Accepted Solution 91464270. Value ofLONG_MAXis2147483647and total cost can be greater than the value ofLONG_MAX.when will we get editorials
I thought I would reach Violet(1900) this time :(
You have at least better luck than me! 
)
haha. lets see who reaches 1900 first.
Challenge Accepted!! By the Way, Whyn't play a little longer, lets see who reaches 2400 first!!!
challenge extending till eternity!!
https://www.youtube.com/watch?v=kjhm0w0kcug
Hope the long wait for EDITORIAL disappears soon :'(.
Hi
My submission for Problem B Div.2 is failing in the cf compiler at test case 44. While running the same test case in my local compiler it seems to be giving the right answer.
https://mirror.codeforces.com/contest/1397/submission/91479829
Can someone help me with the same.
Thanks!
Your kthRoot() function is error prone to precision loss and/or rounding errors. You might try using long double instead of double, or make sure the rounding to lower int works correct, ie add some fraction like 0.001 before casting.
Thanks for your reply!
Even after trying the above I am experiencing the same error.
https://mirror.codeforces.com/contest/1397/submission/91482686 https://mirror.codeforces.com/contest/1397/submission/91482978
Am I still missing something?
Thanks!
On line 55 of your program, your program will overflow the integer. change
labstollabsand applying some check will work. 91485128Thanks for the reply!
Accepted
Wondering how it worked in my local compiler and not in the cf compiler.
In Div.2 B , firstly I sorted the array and then took (n-1)th root of last number , say it came to be 6.4 , then I took 6 and 7 , calculated answer in both cases and found minimum of that , still WA at pretest 4 . Is my logic wrong or I did mistake in implementation part ? My code : https://mirror.codeforces.com/contest/1397/submission/91376042
You need to implement power function for long long int, the inbuilt pow(x,y) function runs in overflow.
Can you tell me the exact pow function required as I'm getting WA by this pow func. long long int Pow(long long int x,long long int y) { if(x==0) return 0; if(y==0) return 1; long long int p=Pow(x,y/2); p*=p; if(y&1) p*=x; return p; }
You can use powl(x,y) for long long values from library.
You can check my submission here : 91391745
It's still WA , can you tell me the error ? My code : https://mirror.codeforces.com/contest/1397/submission/91514571
Point 1 : when you are incrementing cc variable make sure to get the condition greater than zero then you will pass test 3 but not test 4 and after that.
Point 2 : In your case, if you will have n greater than 64 then the powl(x,y) will overflow the long long integers and the function will return garbage value.In test 4 m + 1 = 2 and n — 1 = 99 , so powl(2,99) will be way beyond the limit of the long long int.
Actual Solution : For larger values of n (n > 50) your answer will be to make the sequence all 1s. In that case only you will get minimum cost.
Thanks me later
thanks dude for understanding my newbie code and finding mistakes :))
when editorials will be published?
Sorry for the long delay. We are really busy and trying to publish editorials as fast as possible.
Ok, we understand!
Is the editorial not released due to the long queue?
Long queue disappeared long before contest started
And took the editorial with it.
For div 2 problem C -
Can some1 explain what is the proof for k1 * n + k2 * (n — 1) = 0, in other words some multiples of coprimes can produce any number we want?
Since gcd(n, n — 1) == 1, we can use Bezout's identity to get a, b such that a * n + b * (n — 1) == 1 and then multiply both sides by the number you need, to get a * x * n + b * x * (n — 1) == x
Ok thanks, learning some new maths on Codeforces everyday o__o.
For div 2 problem D what should be the output for 1 2 1 3 According to me, it should be T but the accepted code says its HL. Explanation- first, T picks 3 one now it piles are 1,2 now HL has to pick 1 so now piles are 0,2 now T has to pick 2 so new piles are 0,1 now HL can,t pick either so T should win. UPD: I got it Sorry actually max>rest_sum so it is T
In division 2 question 2, in the following test case, why is the answer to this test case 1999982505 ? With c = 31623 we can get even smaller value 1999954247. TEST CASE: 3 1000000000 1000000000 1000000000
for 31623 , we get
1999982505. check again .Since I joined Codeforces Community, this is the slowest editorial among all of the contest!
Hurry up with the tutorial, Please!!
In stoned Game problem , according to me there can be multiple answer, as it depands on "T" and "HL" which pile they choose. can anyone help ,
This is a misunderstanding of the concept. It is stated that both play "optimally".
Which means that the one losing the game would have made at least one other move that he did, if that would have helped to not be the loser. But he didn't, which means that no such move is possible.
Here are my solution to Div2 probE.91547269
In each level of the game, we have two plans to kill all monsters:
The difference between two plans is that boss will not be killed immediately if using plan 2, so we have to move to adjacent levels twice and spend $$$ 2d $$$ time (assume that we stay in current level after kill all monsters).
Let $$$ \text{once}[i] $$$ be the time we kill all monsters in level $$$ i $$$ by plan 1 , and $$$ \text{twice}[i] $$$ be the time we kill all monsters in level $$$ i $$$ by plan 2. At the beginning, we start the game at level $$$1$$$, and at a certain time, we are at level $$$i$$$, where all monsters in level less than $$$i$$$ were killed and all others are alive. This just same as we start the game at level $$$i$$$. So we using dynamic programming and let $$$dp[i]$$$ be the minimum time to finish the game if we start the game at level $$$i$$$.
Normally, we kill all monsters in current level, then move to next level. So we have $$$dp[i]=\min(dp[i],min(\text{once}[i],\text{twice}[i])+d+dp[i+1])$$$. And let's consider if we use plan 2 in level $$$i$$$, after deals 1 hp damage to boss we are forced to move to next level. If we use plan 2 again in level $$$i+1$$$, then we will move back to level $$$i$$$, we now kill the level $$$i$$$ boss, back to level $$$i+1$$$, and kill the boss too. Now we are at level $$$i+1$$$, where all monsters in level $$$i$$$ and $$$i+1$$$ were killed. We have moved to adjacenct level three times, if we move to level $$$i+2$$$ next, then the total time we spend on this two level is $$$\text{twice}[i]+\text{twice}[i+1]$$$. So we also have $$$dp[i]=\min(dp[i],\text{twice}[i]+\text{twice}[i+1])+dp[i+2])$$$.
And there is also a corner case. Let's consider $$$dp[n-1]$$$, if we use plan 2 in level $$$n-1$$$, then we will finish the game at level $$$n-1$$$. So we have $$$dp[n-1]=\min(dp[n-1],min(\text{twice}[n-1]+\text{once}[n],\text{twice}[n-1]+\text{twice}[n]-d))$$$.
Any idea till when will the Tutorial be uploaded? I am stuck on the last question, Div 2.
Where is the tutorial?
How to summon the editorial
How to summon the editorial
Auto comment: topic has been updated by DatVu (previous revision, new revision, compare).
For the problem 1396A - Multiples of Length, Do I have to select different segments in each step?
No