### atoiz's blog

By atoiz, history, 22 months ago,

(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 Aug/30/2020 17:35 (Moscow time) and lasts 2 hours. In both divisions, there will be 5 problems for you to solve.

The problems were authored and prepared by Maripium, DatVu, MofK, and me.

We are very grateful and would like to sincerely thank the following people for their assistance in preparing the round:

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

• +1146

 » 22 months ago, # |   +33 Auto comment: topic has been updated by Maripium (previous revision, new revision, compare).
•  » » 22 months ago, # ^ |   +47 how do you edit others post?
•  » » » 22 months ago, # ^ |   +69 I'm coauthor
•  » » » » 22 months ago, # ^ |   +57 I was not aware of this feature, but indeed you can now add co-authors of the blog post. Thanks
•  » » » » » 22 months ago, # ^ |   -29 ++
•  » » » » 22 months ago, # ^ |   +6 The question levels jumped a lot from 1st to 2nd. 2 Div.Hoping gradual increase next time.
•  » » » » » 22 months ago, # ^ |   -10 Yeah :/
•  » » » » 22 months ago, # ^ |   +16 Do co-authors receive upvote contribution?
•  » » » » » 22 months ago, # ^ |   +27 Good question! But the answer is no. I also hope cf will have this feature.
•  » » » » » » 22 months ago, # ^ |   +13 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.
•  » » » » » » » 22 months ago, # ^ | ← Rev. 3 →   -15 maybe we can set a limit to how much co-authors can get
•  » » » » » » » 22 months ago, # ^ |   +15 The total contribution should be divided among the author and co-authors in some ratio, that will solve the problem :3
•  » » 22 months ago, # ^ | ← Rev. 2 →   +13 https://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.
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +19 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
•  » » » » 22 months ago, # ^ |   0 Finally I know where the problem is,It took 421 ms on test case 5, and I finally know why. thank you very much.
•  » » » » 22 months ago, # ^ |   +3 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.
•  » » » » » 22 months ago, # ^ |   +3 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.
•  » » » 22 months ago, # ^ |   0 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.
•  » » » » 22 months ago, # ^ |   +3 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).
 » 22 months ago, # |   +145 As a Maripium fan, I want to start an orz chain.Maripium orz.
•  » » 22 months ago, # ^ |   +52 Maripium orz
•  » » » 22 months ago, # ^ |   +39 Maripium orz
•  » » » » 22 months ago, # ^ |   +41 Maripium orz
•  » » » » » 22 months ago, # ^ |   -255 Maripium antiorz
•  » » » » » 22 months ago, # ^ |   +35 Maripium orz
•  » » » » » » 22 months ago, # ^ |   +32 Maripium orz
•  » » » » » » » 22 months ago, # ^ |   +1 Maripium orz
•  » » » » » » » » 22 months ago, # ^ |   0 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   +21 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   -45 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   -118 Mongorz
•  » » » » » » » » » 22 months ago, # ^ |   -73 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   +39 redditforces
•  » » » » » » » » » 22 months ago, # ^ |   -89 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   -83 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   -101 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   -91 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   -79 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   +74 Number of votes are so random
•  » » » » » » » » » 22 months ago, # ^ | ← Rev. 2 →   -30 .
•  » » » » » » » » » 22 months ago, # ^ |   -41 Maripium orz
•  » » » » » » » » » 22 months ago, # ^ |   0 whoever invented the 'downvote number generator', I'm probably gonna hate him :(rip contribution
•  » » » » » » » » » 15 months ago, # ^ |   -10 Maripium orz
•  » » » 22 months ago, # ^ | ← Rev. 2 →   -54 Hope for strong pretests.
•  » » 22 months ago, # ^ |   -57 Maripium orz
•  » » 22 months ago, # ^ |   -48 Kuroni orz
 » 22 months ago, # |   +88 Will this contest be Lucifer themed?
•  » » 22 months ago, # ^ | ← Rev. 2 →   +49 Unfortunately, this contest won't have any theme.
•  » » » 22 months ago, # ^ |   +266 Shame on you, ruined such a chance
•  » » » 22 months ago, # ^ |   +117 The greatest trick devil ever pulled was convincing the world that the devil's theme doesn't exist :XD
•  » » » 22 months ago, # ^ |   0 Another missed opportunity...
•  » » » 22 months ago, # ^ |   +205 *Fortunately
 » 22 months ago, # |   +107 I tested this round when I was blue!!! xD
•  » » 22 months ago, # ^ |   +200 After this round I will be blue!!! xD
•  » » » 22 months ago, # ^ |   +58 666 is the devils number, you will become orange :XD
•  » » » » 22 months ago, # ^ |   +69 How many devils do you know that are orange instead of red?
•  » » » » » 22 months ago, # ^ |   +303
•  » » » » » » 22 months ago, # ^ |   -70 I guess this is saffron!
•  » » » 22 months ago, # ^ |   0 How good it'll be if you and me will have the same colour after this round.
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 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 !
•  » » » » » 22 months ago, # ^ |   +9 positive or negative change :XD
•  » » » » » » 22 months ago, # ^ |   +23 Devil knows!
•  » » » 22 months ago, # ^ |   -16 Really?
•  » » » 22 months ago, # ^ |   0 devil was right
•  » » 22 months ago, # ^ | ← Rev. 2 →   +24 I tested this round when I was blue (well I still am).
•  » » 22 months ago, # ^ | ← Rev. 2 →   +2 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!
•  » » » 22 months ago, # ^ |   +18 Well, there are specific Discord servers set up for co-ordination.
•  » » » 22 months ago, # ^ |   +5 its because we people have a wonderful sleep schedule :)
•  » » 22 months ago, # ^ |   -8 Nice
 » 22 months ago, # |   -22 You know the guy gives no F's when his handle name is something like user202729_ Damn bro , You have the most interesting uninteresting handle name I've ever seen
 » 22 months ago, # | ← Rev. 2 →   +136 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...
•  » » 22 months ago, # ^ |   +23 Plot Twist: This was a plan to get more friends using reverse psychology
 » 22 months ago, # | ← Rev. 2 →   -9 OMG!!!! 666 round, so scared!! OMG
 » 22 months ago, # | ← Rev. 2 →   +28 ♫ 666 the Number of the Beast Sacrifice is going on tonight ♫
 » 22 months ago, # |   +1 WOW! palindrome round.
 » 22 months ago, # |   +16 What’s devil’s number?
•  » » 22 months ago, # ^ |   +10 666 is the devil's number or also referred to as 'number of the beast'
 » 22 months ago, # |   +57 300iq seems like having an Asia tour on Internet and now he is arriving at Vietnam.
 » 22 months ago, # | ← Rev. 2 →   +25 Others: " I know coding "LGMs: " Coding knows me "
 » 22 months ago, # |   +30
 » 22 months ago, # |   +76 $666 = \sum\limits_{i=1} ^ {36} i$ $666\times 69$ is a palindrome. Look at my profile picture. I also recorded a video of it happening.
•  » » 22 months ago, # ^ |   +61 Also, 666 is the sum of squares of first seven primes
•  » » 22 months ago, # ^ | ← Rev. 2 →   +92 One more, 666 is the sum of the first 144 decimals of π.
•  » » 22 months ago, # ^ | ← Rev. 4 →   +26 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
•  » » 22 months ago, # ^ |   -37 left-handed? cringe
•  » » » 22 months ago, # ^ |   +8 Right-handed gang aaaoooohhh! aaaooooh!
•  » » 22 months ago, # ^ |   +25 You use the mouse with your left hand, on the right side of the keyboard???
•  » » » 22 months ago, # ^ |   0 Wakanda Style!
•  » » » 22 months ago, # ^ |   0 I think his right hand was holding the camera.
•  » » 22 months ago, # ^ |   +4 Hexakosioihexekontahexaphobia is the fear of the number "666."
•  » » » 22 months ago, # ^ |   +8 Hippopotomonstrosesquippedaliophobia is the fear of long words
 » 22 months ago, # | ← Rev. 2 →   +9 5 problems and div.1 & div.2 looks like round is going to be tough.
 » 22 months ago, # |   -35 hope pretests passed => main tests passed
•  » » 22 months ago, # ^ | ← Rev. 2 →   +43 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/7357B: 10/6890C: 81/5225D: 35/2046E: 0/352(pretests=tests)F: 3/263G: 1/97H: 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.
•  » » » 22 months ago, # ^ |   0 Does all hack-Cases are included in main tests or it depends on setter committee to decide which tests to include for system tests?
•  » » » » 22 months ago, # ^ |   +17 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.
•  » » » » » 22 months ago, # ^ |   +5 Thanks for the reply!
 » 22 months ago, # |   -30
 » 22 months ago, # |   +7 rip Devil
 » 22 months ago, # |   +6 six six six
 » 22 months ago, # |   +11 six six six, nice round, :) from VietNam with love <3
•  » » 22 months ago, # ^ |   0 nice round :) from LeToan Fan Club <3
 » 22 months ago, # |   -17 Maripium org
 » 22 months ago, # |   0 How many languages does 300iq plan to master?
 » 22 months ago, # |   +7 atoiz orz
 » 22 months ago, # |   -11 Wow Rated contest after a long gap,Contest is seems to be very Interesting...
 » 22 months ago, # |   -15 Hope for strong pretests.
 » 22 months ago, # |   +42 This is the last contest I can play before school starts. (T_T)Then I will become Candidate Master!
•  » » 22 months ago, # ^ |   0 yo man! i'm still newbie here T.T how can i be like you? :<
•  » » » 22 months ago, # ^ |   +94 YO man! i'm STill mAStER heRe T.t hOw caN i BE Like you? :<
•  » » 22 months ago, # ^ |   -15 You will see, once you go to school you will learn many new things!
•  » » » 22 months ago, # ^ |   +124 Many new useless things
 » 22 months ago, # |   0 me when i see the image: chrome translate can translate image ???? :D ???? what is going on ????
 » 22 months ago, # |   -6 Is div. 3 being discontinued or something? No div3 being held nowadays.
•  » » 22 months ago, # ^ |   0 There is a Div 3 this coming Friday.
•  » » » 22 months ago, # ^ |   0 Oh yes. Thanks. The contest wasn't declared when I wrote that comment.
•  » » » » 22 months ago, # ^ |   0 No worries, I hope you're able to attend this one. Have fun!
 » 22 months ago, # |   -18 Ya, From VietNam with Love. Good luck to the contest and for all
 » 22 months ago, # | ← Rev. 12 →   -42 excited for vietnamese contest
•  » » 22 months ago, # ^ |   -17 vietnamese nha bro :))
•  » » » 22 months ago, # ^ |   -17 ok fine :)
•  » » » 22 months ago, # ^ |   +3 u'll get many downvotes because of speaking vietnamese here bro :v
•  » » » » 22 months ago, # ^ |   +5 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 :))
 » 22 months ago, # |   -15 húuuuuuuuu!!!!!!!!
 » 22 months ago, # |   -7 this week's only contest ...
 » 22 months ago, # |   -6 This'll be a devil of a round
 » 22 months ago, # |   0 If this round isn't DOOM themed I will lose all hope in humanity.
 » 22 months ago, # |   +27 What is codeforces Round X? is it a new type of round?
•  » » 22 months ago, # ^ |   +15 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.
•  » » » 22 months ago, # ^ |   +8 It is 2.5 hr long, so it is most probably a different type of round.
 » 22 months ago, # |   -24 I hope to get the 666th place :)
 » 22 months ago, # |   +85 Here it is! +666
 » 22 months ago, # |   0 Why score distributions are announced later? I don't know the reason. Can anyone tell me?
 » 22 months ago, # | ← Rev. 2 →   +11 Again,the long queue issue ..Waiting my solution to be executed...[user:MkeMirzayanov] Please look into it
 » 22 months ago, # |   0 Cant wait
 » 22 months ago, # |   -7 WOW, Viet Nam :v
 » 22 months ago, # |   +20 Is the codeforces queue long just to make it feel like a bad omen?
 » 22 months ago, # |   +8 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.
 » 22 months ago, # |   0 Looks like problems from hell.
 » 22 months ago, # |   0 Auto comment: topic has been updated by atoiz (previous revision, new revision, compare).
 » 22 months ago, # |   0 The queue disappeared!
 » 22 months ago, # |   -36 Me trying to get some rating in this round: Meanwhile the devil:
•  » » 22 months ago, # ^ |   -33 me too :)
•  » » 22 months ago, # ^ |   -12 You think you are funny?! So face it, you are not
 » 22 months ago, # |   -35 Score distribution looks very scary.B and C have difference of 250 points onlyThis indicates two types of round1. Speed-forces2. The hard one or unbalancedFingers crossed....
 » 22 months ago, # |   +17 round-666 will be my 66 contest :D
•  » » 22 months ago, # ^ |   +6 Aren't you and Rudro25 same person?
•  » » 22 months ago, # ^ | ← Rev. 2 →   -13 Cant tell if thats a good or bad omen
 » 22 months ago, # |   0 Queue disappeared :) All the best everyone for the round.
 » 22 months ago, # |   +2 To do well in this contest you have to listen to Iron Maiden not TWICE :P
 » 22 months ago, # |   -20 666 is a natural number :)
 » 22 months ago, # |   +6 Hakuna Matata!!
 » 22 months ago, # |   -31 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
•  » » 22 months ago, # ^ |   0 you'd be judged based on your last submission time for any problem. it's part of the rules
•  » » » 22 months ago, # ^ |   0 Why this rule? It just screwed my contest.
•  » » » » 22 months ago, # ^ |   +24 Why did you resubmit?
•  » » » » 22 months ago, # ^ |   +21 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.
•  » » 22 months ago, # ^ |   0 Read the "Judging Solutions" part in the rules, point number 5 after the table.
•  » » 22 months ago, # ^ |   +2 Meanwhile I cant even solve B
 » 22 months ago, # |   +1 Is there a way to find the number of pretests in a problem?
•  » » 22 months ago, # ^ |   +23 You can see it in http://m2.codeforces.com/.
 » 22 months ago, # |   +21 Reading E is so fun. haha
 » 22 months ago, # |   -7 This really is a cursed round
 » 22 months ago, # |   0 After this round, I hate 666.
 » 22 months ago, # |   +14 finally some interesting problems i love it!!
 » 22 months ago, # |   -26 We have spent many months to brainstorm ideas, so we hope you will enjoy our round! Duh
•  » » 22 months ago, # ^ |   0 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)
•  » » » 22 months ago, # ^ |   0 Are you sure 10^9-31625^2 is positive?
•  » » » » 22 months ago, # ^ |   0 But we can either increase or decrease the number so 10^9 can be raised to 31625^2 by adding 140625
•  » » » » » 22 months ago, # ^ |   0 But the cost is 31625^2 — 10^9Not 10^9 — 31625^2
•  » » » » » » 22 months ago, # ^ |   0 I got it. I was doing silly mistake Thankyou for helping me.
 » 22 months ago, # |   0 Pretests for B :(
•  » » 22 months ago, # ^ |   0 Me too
•  » » 22 months ago, # ^ |   0 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.
•  » » » 22 months ago, # ^ |   0 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.
•  » » » » 22 months ago, # ^ |   0 I used 1e6, still WA
•  » » » 22 months ago, # ^ |   0 witcher98 I had the same mistake with binary search at first, I changed the search such that if(min==max){return min} and if(min+1==max){return max}, and it worked.
•  » » » 22 months ago, # ^ |   0 Did the same bro, WA on pretest 4, my output comes smaller :D
 » 22 months ago, # |   +53 Div1 C was really painful
•  » » 22 months ago, # ^ |   -19 Agreed, statement was very long.
•  » » 22 months ago, # ^ |   0 The statement looked so painful that after solving all the other tasks in div2 I decided to quit without approaching it
•  » » 22 months ago, # ^ |   +53 Disagree. The first impression was indeed painful, but the seemingly annoying parts disappeared quickly. Code is short and contains no strange special cases.
•  » » » 22 months ago, # ^ |   0 Hmm, my code doesn't look that short. Maybe I'we just done things in a too complex way
•  » » » 22 months ago, # ^ |   +8 contains no strange special casesI'm very curious as to how you solved this problem, because my solution is case whack after case whack.
•  » » » » 22 months ago, # ^ |   0 Are the cases only on paper or in the code too? Now I'm kind of worried that I'll fail system tests. My code#include using namespace std; typedef long long ll; const int MAX_N = 1e6 + 5; const ll INF = 1e18 + 300; ll monsters [MAX_N]; ll A [MAX_N]; ll B [MAX_N]; ll sfx [MAX_N]; ll dp [MAX_N]; int main () { ios::sync_with_stdio(false); int n; cin >> n; ll R1, R2, R3, D; cin >> R1 >> R2 >> R3 >> D; for (int i = 1; i <= n; i++) { cin >> monsters[i]; } for (int i = 1; i <= n; i++) { A[i] = min((monsters[i] + 2) * R1, R2 + R1); B[i] = min(monsters[i] * R1 + R3, A[i] + 2 * D); A[i] += D; } sfx[n] = B[n]; for (int i = n - 1; i >= 1; i--) { sfx[i] = sfx[i + 1] + A[i]; } for (int i = 0; i <= n; i++) { dp[i] = INF; } ll ans = INF; dp[0] = 0; for (int i = 0; i < n; i++) { dp[i + 1] = min(dp[i + 1], dp[i] + B[i + 1]); dp[i + 2] = min(dp[i + 2], dp[i] + A[i + 1] + A[i + 2]); ans = min(ans, dp[i] + sfx[i + 1]); } ans = min(ans, dp[n]); cout << ans + (n - 1) * D << endl; } 
•  » » » » » 22 months ago, # ^ |   0 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. My code (apologies, I don't appear to know what line breaks are)#include #include #include using namespace std; int n; long long r1, r2, r3, d, a[1000000], x[1000000], y[1000000], z[1000000], dptable[1000000][4]; long long dp(int i, int flag) { if (i == 0) { if (flag == 0) return z[0]; if (flag == 1) return 1000000000000000000LL; else return min(x[0] + y[0], z[0]); } if (dptable[i][flag] != 0) return dptable[i][flag]; if (flag == 0) return dptable[i][flag] = z[i] + min(dp(i - 1, 0), dp(i - 1, 1)) + d; if (flag == 1) return dptable[i][flag] = min(x[i] + y[i], z[i]) + dp(i - 1, 3) + 3 * d; if (flag == 2) return dptable[i][flag] = min(x[i] + y[i], z[i]) + min(min(dp(i - 1, 0), dp(i - 1, 1)) + d, dp(i - 1, 2) + 2 * d); return dptable[i][flag] = min(x[i] + y[i], z[i]) + min(min(dp(i - 1, 0), dp(i - 1, 1)) + d, dp(i - 1, 3) + 3 * d); } int main() { scanf("%d %lld %lld %lld %lld", &n, &r1, &r2, &r3, &d); for (int i = 0; i < n; ++i) scanf("%lld", &a[i]); for (int i = 0; i < n; ++i) { x[i] = min(min(r1 * (a[i] + 1), r3 * a[i] + r1), r2); y[i] = min(min(r1, r3), r2); z[i] = min(r1 * a[i] + r3, r3 * (a[i] + 1)); } int i = n - 1; printf("%lld", min(min(dp(n - 1, 0), dp(n - 1, 1)), dp(n - 1, 2) + min(max(0LL, z[i] - x[i] - y[i]), 2 * d))); return 0; } 
•  » » 22 months ago, # ^ |   +51 I dare to disagree with you. I think Div1 C was a beautiful dp problem.
•  » » » 22 months ago, # ^ |   0 could u pls explain
 » 22 months ago, # |   0 what is the pretest 4 of B.. Any guess ???
•  » » 22 months ago, # ^ |   +2 a really cursed pretest lol
 » 22 months ago, # |   0 How to solve B?? Should we brute force all possible values of c and then find minimum cost??
•  » » 22 months ago, # ^ |   +3 Yes
•  » » » 22 months ago, # ^ |   +1 Yeah but how do you set the limit on maximum value of c.My logic gave WA on pretest 4.
•  » » 22 months ago, # ^ |   +1 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
 » 22 months ago, # |   +3 How to solve D?
•  » » 22 months ago, # ^ |   +7 Greedily. Actually I think it was easier than C
•  » » 22 months ago, # ^ | ← Rev. 3 →   +7 Passed pretest by always choosing the pile with the biggest value. Let's see if it passes the system test.UPD: It passed.
•  » » » 22 months ago, # ^ |   +3 Thanks. Actually constrains confused me a little bit.
•  » » » 22 months ago, # ^ |   0 hi, can you tell me what's wrong with this? https://codeforces.com/contest/1397/submission/91393551
•  » » 22 months ago, # ^ |   +12 If max_value > sum — max_value answer is T, else answer depends on sum % 2.
•  » » » 22 months ago, # ^ | ← Rev. 3 →   0 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?
•  » » » » 22 months ago, # ^ |   +3 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
•  » » » » » 22 months ago, # ^ |   0 Thanks, this makes sense. Btw how to prove it mathematically?
•  » » » » » » 22 months ago, # ^ |   0 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
 » 22 months ago, # |   0 Approach for B?
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 Why is this[submission:91390097] giving WA.
•  » » » 22 months ago, # ^ |   0 I did the same but failed the system cases.
•  » » » 22 months ago, # ^ |   0 Can you elaborate more?
 » 22 months ago, # |   0 whys is this Giving WA?
 » 22 months ago, # |   0 Nice problem, like this round
 » 22 months ago, # |   +15 Please don't tell me that the constraints in D were so low only to confuse the heck out of me.
•  » » 22 months ago, # ^ |   0 there was a solution in O(sum(a)^3)
•  » » » 22 months ago, # ^ |   0 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) ?
•  » » » » 22 months ago, # ^ |   0 sorry, actually its O(sum(a)*max(a))
 » 22 months ago, # |   +21 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.
•  » » 22 months ago, # ^ |   +10 I costed 2 WA for that. Feeling the pain bro
•  » » » 22 months ago, # ^ |   +3 It costed me 4 WAs and gave hell lot of panic :(
 » 22 months ago, # |   +1 What is the logic in Div2 B
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 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)
•  » » » » 22 months ago, # ^ |   0 I guess you can use Newton raphson's method or similar iterative approximation techniques
•  » » 22 months ago, # ^ |   0 Use ternary search for appropriate c
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 Why is this submission 91390097 giving WA
 » 22 months ago, # |   +27 Div2 C was by far one of the most interesting observations used on an ad-hoc problem.
•  » » 22 months ago, # ^ |   +1 Div2 C was a pretty darn clever problem, ngl
•  » » » 22 months ago, # ^ |   0 There was a similar one in a global round! Couldn't do it then!Upsolving helped :D
•  » » » » 22 months ago, # ^ |   0 Can you give the link of the problem in global round?
•  » » 22 months ago, # ^ |   +11 I mean... You can't say "by far" and then say "one of the..." xDIt was a super cool problem!
•  » » » 22 months ago, # ^ |   0 "By far" was for me... "one of the" for the more experienced people. Didn't want to declare something without allowing public opinion. :p
•  » » 22 months ago, # ^ |   +9 "It can be proved that the solution is always possible". Imagine if that hint wasn't there!
 » 22 months ago, # |   +3 Let's hope the main tests pass :P
 » 22 months ago, # |   +7 Could not solve even B this time :( Any idea on how to do it
•  » » 22 months ago, # ^ |   +1 Could not solve even B this timeYou're Not Alone.
•  » » » 22 months ago, # ^ |   +5 a real relief to find that an expert(not for long time xD) is with me.
•  » » 22 months ago, # ^ |   +5 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.
•  » » » 22 months ago, # ^ |   0 I implemented the same n=50 approach. Dont know what went wrong ;/
•  » » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 How can you use binary search?
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » 22 months ago, # ^ | ← Rev. 5 →   0 Are you assuming that as $c$ grows the result is continuously improving until it reaches the optimal value, and after that it is getting increasingly worse?
•  » » » » » 22 months ago, # ^ |   0 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.
•  » » 22 months ago, # ^ |   0 Me too, 3rd problem was clever though!
 » 22 months ago, # |   +269 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 :(
•  » » 22 months ago, # ^ | ← Rev. 2 →   +31 Wow, didn't even notice it till the end, wrote min statements everywhere to handle cases for that ._.
•  » » 22 months ago, # ^ |   +11 $r_1 \leq r_2 \leq r_3$ — what?Although the solution without this constraint is too complicated as well.
•  » » 22 months ago, # ^ |   -16 I just noticed after reading your comment. Thanks.
•  » » 22 months ago, # ^ |   +26 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.
 » 22 months ago, # |   -15 a video solution for problem c(seems good problem).
 » 22 months ago, # |   0 Div2 B. Im trying to brute force. 1 < i < sqrt(max(list)) But I got TLE on pretest 4 How to approach it?
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 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, $up^{(n-1)}<=2e9$. To be more careful, I selected 1e10 instead of 2e9. So I got up = pow(10,10.0/(n-1)). Now you can go from 1 to up`, and keep track of the minimum abs diff.
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 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://codeforces.com/contest/1397/submission/91386048
•  » » » 22 months ago, # ^ |   0 Thank you for your help!! I astonished very cleary solution to me.
 » 22 months ago, # |   +171 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 :/
•  » » 22 months ago, # ^ |   +11 Honestly, I don't see the point of Div2 BCDE either. The difficulty gradient was quite unbalanced.
 » 22 months ago, # |   0 I implemented Div2 C at last moment is this code correct or still it require something else!https://ideone.com/HJ3kDp
•  » » 22 months ago, # ^ |   0 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!
 » 22 months ago, # | ← Rev. 2 →   +3 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?
 » 22 months ago, # |   +5 Div2 C was nice :) took too much time to solve it
 » 22 months ago, # |   +14 Looks like solving linear congruences a∗x≡b (mod n) was an overkill for C lol.
•  » » 22 months ago, # ^ |   +1 Can someone explain how to solve it?
•  » » » 22 months ago, # ^ |   +3 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].
•  » » » » 22 months ago, # ^ |   +6 What a clever solution!!!
•  » » » 22 months ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » » 22 months ago, # ^ |   0 I can't believe I missed this observation :(
 » 22 months ago, # |   +2 Devil fooled me with div2A
 » 22 months ago, # |   0 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.
•  » » 22 months ago, # ^ | ← Rev. 2 →   +5 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.
•  » » » 22 months ago, # ^ |   0 Thanks, Got it! Can you tell me what's wrong in my B approach...
•  » » » » 22 months ago, # ^ |   +3 I will see it once i solve B successfully.
•  » » 22 months ago, # ^ | ← Rev. 3 →   0 For B I tried all values of c until c^k < 10000000000, because A[i]<10^9 and and abs(A[i]- 10000000000) would be too big. my submission
•  » » 22 months ago, # ^ |   0 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
•  » » » 22 months ago, # ^ |   0 What was the answer for Test case 2 ? The 10^9 one , I Mean the number they were power of ?
•  » » » » 22 months ago, # ^ |   0 31622 and 31623 are the closest to 10^9 and 31623 will give us a minimum for 31622 2000017493, for 31623 1999982505
•  » » » » » 22 months ago, # ^ |   0 Thanks.
 » 22 months ago, # |   +18 Problems B and C gave me PTSD.
 » 22 months ago, # |   0 It took me over an hour to realize that I was overflowing long long on problem 2. RIP.
 » 22 months ago, # |   0 Could someone please tell what is the problem for my soln to B?https://codeforces.com/contest/1397/submission/91418834
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 Oh, sorry, im wrong. I forgot that n > 2
 » 22 months ago, # |   0 How to solve Div2 D ??
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 I also wonder how to do it. Could someone tell me what the meaning of this sentence : "if the current turn is the first turn then the player can choose any non-empty pile" . Could HL pick the first pile if T pick the first pile at first?
•  » » 22 months ago, # ^ |   +4 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.
•  » » 22 months ago, # ^ |   0 it's a parity problem but with a twistscenario 1: Both players can pick from any stack regardless — Then T wins if the total number of stones is odd and HL wins if total number of stones is evenscenario 2: Each player can not pick from the stack the other player just picked — same as scenario 1 but on the condition if (size of biggest stack) > (size of rest of stacks added together) then T wins automatically since he picks first.
 » 22 months ago, # | ← Rev. 2 →   0 Some people complained that the pony round had long problem statementsHa-ha.Look at Monster Invader. That is how you write long statements
 » 22 months ago, # | ← Rev. 2 →   -42 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.
•  » » 22 months ago, # ^ |   0 plz tell approach for B...?
•  » » 22 months ago, # ^ |   +20 Link to the rules is there when you register.
•  » » » 22 months ago, # ^ |   -47 I actually register just 5 minutes before the contest seeing whether I could give that round or not
•  » » 22 months ago, # ^ |   +3 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.
•  » » » 22 months ago, # ^ |   -22 And if someone makes wrong submission then is he not doing changes.
•  » » 22 months ago, # ^ |   +8 Why not make it something like If the first correct attempt fails, then the next one is consideredThen everyone will submit multiple solutions to 'secure' AC.
•  » » » 22 months ago, # ^ |   0 You can then also charge him for his previous wrong submissions.
•  » » 22 months ago, # ^ |   0 If you do not want you do not have to submit twice.
•  » » » 22 months ago, # ^ |   0 I will remember it from now.
•  » » 22 months ago, # ^ | ← Rev. 3 →   +4 "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
•  » » » 22 months ago, # ^ |   0 If the test cases are strong then obviously only correct solution will pass which don't pass can be skipped in system tests.
•  » » » » 22 months ago, # ^ | ← Rev. 2 →   +1 Thinking that strong pretests cover all possible cases and give you absolute guarantee is a plain bullshit and naivetyOne 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.
•  » » » » » 22 months ago, # ^ |   0 I got your point thanks
 » 22 months ago, # | ← Rev. 2 →   +6 I've written a fairly straight-forward brute for B.Could someone tell, if i'm missing something? Solution Failing on TC3
•  » » 22 months ago, # ^ | ← Rev. 2 →   -7 [deleted]
•  » » » 22 months ago, # ^ |   +3 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.
•  » » » 22 months ago, # ^ |   +3