By awoo, history, 2 months ago, translation,

Hello Codeforces!

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Roman Roms Glazov, Adilbek adedalic Dalabaev, Vladimir vovuh Petrov, Ivan BledDest Androsov, Maksim Neon Mescheryakov and me. Also huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 neal 7 223
2 jiangly 7 224
3 tute7627 6 190
4 nocriz 6 195
5 noimi 6 213

Congratulations to the best hackers:

Rank Competitor Hack Count
1 MarcosK 41:-6
2 dapingguo8 34:-2
3 jerdno 12:-4
4 ARTpositive 10:-1
5 halyavin 9:-1
357 successful hacks and 769 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A edickLPM 0:00
B SSRS_ 0:03
C corol 0:03
D pajenegod 0:08
E neal 0:29
F jiangly 0:55
G jiangly 1:17

UPD: Editorial is out

• +146

 » 2 months ago, # |   -31 Hope this round will be good
 » 2 months ago, # |   -23 Another Educational Round. Hopefully I will do better like previous Educational Round. I think, The problem will be more interesting. Ops! I'm waiting for that.):
•  » » 2 months ago, # ^ |   -8 I don't know why people giving me down vote! I just expressed my feelings! I really shocked about people's attitude. But I have done well today that is my satisfaction.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +22 People downvote your comment probably because they think this types of comments just fill the comment section and then one need more time to find useful content. No one wants to read 100 comment of people expressing their feelings!
•  » » » » 2 months ago, # ^ |   +22 Thank you for knowing me. I didn't guess it before. Next time i wll keep it in my mind.
 » 2 months ago, # | ← Rev. 3 →   -39 [Deleted]
•  » » 2 months ago, # ^ | ← Rev. 4 →   -26 [Deleted]
 » 2 months ago, # |   0 Super Excited !!
 » 2 months ago, # |   0 In awe of the mentions UwU
 » 2 months ago, # |   +4 This is my chance to go up to master!!!
•  » » 2 months ago, # ^ |   +14 Good luck
•  » » 2 months ago, # ^ |   +12 my chance for expert !
•  » » 2 months ago, # ^ |   +91 my chance to lose expert
•  » » » 2 months ago, # ^ |   0 may be next time
•  » » » » 2 months ago, # ^ |   0 I entered the contest with my smurf. Delta = -134. I went back to blue
•  » » » » » 2 months ago, # ^ |   0 nvm round #688 awaits, btw smurf means alt account right ?
•  » » » » » » 2 months ago, # ^ |   0 yes
•  » » 2 months ago, # ^ |   +2 My chance for pupil!
•  » » 2 months ago, # ^ |   +1 Hoping I get my blue back in this contest
•  » » » 2 months ago, # ^ |   +5 a bad contest for you :(.. dont worry next one may make you blue.....i am sure of it.keep up hopes
•  » » » » 2 months ago, # ^ |   +1 Thank you.. After losing 250 rating in 2 days I seriously needed this :)
•  » » 2 months ago, # ^ |   0 I hope I become an expert after this :)
 » 2 months ago, # |   +27 People reading this comment, hope you have a good contest. All the best!!
 » 2 months ago, # |   +2 May i become specialist this time !!
•  » » 2 months ago, # ^ |   0 all the best !!
•  » » 2 months ago, # ^ |   0 Wish me luck too
 » 2 months ago, # |   +2 This may be my last contest before my college final exam. After that I will open my brand new advanced mathematics book and my linear algebra book. Oh my god, brand new(╥﹏╥). I hope i can get good results all of them.
•  » » 2 months ago, # ^ |   0 Maybe my last contest too before my college final exam. After that I will open the PDF notes send by the topper and hope I can get good results.
 » 2 months ago, # | ← Rev. 2 →   +16 Maybe the last round before senior high school...It's time to say goodbye to you now guys. Hope we'll all do our best in this round. :)
•  » » 2 months ago, # ^ |   0 Don't go :(
•  » » » 2 months ago, # ^ |   0 I don't want to do that either but I have to :(After all, high school entrance examination is always more inportant than OI :(
 » 2 months ago, # |   +116
 » 2 months ago, # |   +12 the comment section is shit
•  » » 2 months ago, # ^ |   +36 And you're not Errichto
 » 2 months ago, # |   -31 Score distribution awoo ?
•  » » 2 months ago, # ^ |   +70 There is no score in Educational Codeforces Round
•  » » » 2 months ago, # ^ |   +1 Why? Also what is differnece between educational div. 2 and other div. 2.
•  » » » » 2 months ago, # ^ |   0 In edu each problem scores 1 point, other div2 have different points per problem.
 » 2 months ago, # |   +14 In the hope that I don't mess this round by silly and not required lengthy implementations.
 » 2 months ago, # |   -16 I have end semester exam tomorrow. Should I compete this round?
•  » » 2 months ago, # ^ |   0 What? So early in India? In China usually in January or February...Anyway, you'd better take a good rest as the end semester exam is more important than a CF round :)
•  » » » 2 months ago, # ^ |   0 no its happening in december as usual
 » 2 months ago, # |   -9 I just pray and hope that it wouldn't be another Mathforces round.
•  » » 2 months ago, # ^ |   +5 pikMike loves Math problems, so who knows!!!
 » 2 months ago, # |   -38 aaaja mahi aaja mahi aa soniya ve aake aaj mere gale lag jaaa tu hoye
 » 2 months ago, # |   0 I don't understand why I perform bad in educational rounds, despite the fact that standard problems are asked unlike Div 2 contests. Anyone else with same problems?P.S: This is an alt account.
•  » » 2 months ago, # ^ |   -30 yes but if u sing arijit singh songs while solving questions then u will get AIR 1
 » 2 months ago, # |   +5 When will be shown the difficulties of tasks from Codeforces Round #685 ? It's been more than a week ago!
 » 2 months ago, # | ← Rev. 2 →   0 7 min left be ready i hope u solve many problems good luck :D
 » 2 months ago, # |   0 My opportunity for Expert
•  » » 2 months ago, # ^ |   0 same i have opportunity for 1000 points
 » 2 months ago, # |   0 I'm gonna participate so more chance to gain lost rating on sunday
•  » » 2 months ago, # ^ |   0 i hope that :D
 » 2 months ago, # |   +64 Congratulations to the 100000000th submission!
•  » » 2 months ago, # ^ |   +19 Congrats ub33 :p
 » 2 months ago, # |   -20 Man, is this educational round a joke?
 » 2 months ago, # |   +13 Most uninteresting problem set ever
•  » » 2 months ago, # ^ | ← Rev. 2 →   -13 nvm
•  » » » 2 months ago, # ^ |   +4 Also, example- Education round 99 problem C
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Yes, i will also agree that 'C' is uninteresting, but this guy is shitposting before solving them which is not fair. The only problem i found interesting was 'B'.
•  » » » » » 2 months ago, # ^ |   0 can you share your solution please
•  » » » » » » 2 months ago, # ^ |   0 keep moving greedily and once you cross you destination you will come to know what step you should not have taken greedily that will be K=(finalDest-x)th step.
•  » » » » » » » 2 months ago, # ^ |   0 can you explain the case for 7
•  » » » » » » » » 2 months ago, # ^ |   0 sorry k is actually (finalDest-x-1)th step, for 7 finalDest will be 10, so difference=3 so inspite of taking second step greedily, take a step back and again proceed greedily
•  » » » » » » » » 2 months ago, # ^ |   +1 Keep jumping greedily till you reach a point >= x. If your current_pos-x is 0, then obviously answer is number of jumps. Now if its not, then there are two cases 1. current_pos-x == 1 In this case, you always need to jump back a step. So, answer is jumps + 1. The second case current_pos-x > 1 Since it is greater than 1, there is always a jump in range [1, jump], that you can decide to not perform and jump back. Example x = 7 1 3 6 10 lets stop jumping since 10>=7 cur_pos = 10, jumps = 4 here, difference is 3 (10-7), so there is always a previous step,in which you decide to not jump forward and jump back. In this case, if you dont do the second jump (+2) and jump back (-1), you will end up at 7 in 4 jumps.
•  » » » » » » » » » 2 months ago, # ^ |   0 this is hard for a Div2 B
•  » » » » » » » » » 2 months ago, # ^ |   0 How would you prove the last section of your comment? Why in case we overjumped our x by 1, then we make a jump back, but when we overjumped by n greater than 1, there is ALWAYS a jump in range [1, jump] that i wanna not perform and jump back? Why if I overjumped by n greater than 1, i can't just jump back n times?
•  » » » » » » » » » 2 months ago, # ^ |   0 This is because the kth jump goes over k positions, and n-x is garanteed to be smaller than the last jump.
•  » » » » » » » » » 2 months ago, # ^ |   0 Ok, I understand that the distance of overjump is less than kth jump, but i don't understand why i shall do a jump back(and what's the count of them) somewhere in my jump path, instead of inserting my backjumps in the end of jump sequance?
•  » » » » » » » » » 2 months ago, # ^ |   0 See it that way: If you do a step back in ith step instead of jumping, then the contribution of this step back is i+1 positions to the left. (Because you did not jumped i and steped one back).So if you are in the end y position to much on the right, then you kind of revert one jump. And because it should cause y positions, you choose the y-1 -th one. This works as long as y>1. If y==1 then there is no jump you could revert.
•  » » » » » » » » » 2 months ago, # ^ |   +1 Because you want to minimize the number of steps. Changing one of the already taken jumps to -1 will cost nothing. But jumping back in the end will cost 1 move for jump.
•  » » » » » » » » » 2 months ago, # ^ |   0 Wow, great! As soon as I read your comment i firstly started to think that i misunderstood the task, then i read again the task, returned to this post and started to write that you're wrong, and in this moment i finally understood why it works. Thanx!
•  » » » » » » » » » 2 months ago, # ^ |   0 Consider 4 jumps [1, 2, 3, 4]. Here, the sum is 10. Now try replacing any of these by -1 and check what the sum will be. You will get all sums except 9. So you always a need an extra jump if difference is 1.
•  » » » » » » » » » 2 months ago, # ^ |   0 So well explained!
•  » » » 2 months ago, # ^ |   +4 Kid looks like its your first time solving D. Doesn't mean its an interesting problemset (atleast for me). Besides I left the contest long ago, and I dont judge someone's opinion based on their rating or whether they have solved B or not in a contest I like problems which are ds oriented not based on Math
•  » » » » 2 months ago, # ^ |   -7 Looks like you got a burn?
•  » » » » » 2 months ago, # ^ |   +8 Yes burnt just like your rating graph
•  » » » » » » 2 months ago, # ^ |   0 Haha your Humour is great! Btw nice talking to you
•  » » » » » » 2 months ago, # ^ |   +12 You just literally said you dont judge anyone based on their rating and then went on to judge him on his rating graph. Hypocrite much
•  » » » » » » » 2 months ago, # ^ |   +3 lol what I said I don't judge someone's opinion/likeness towards a problemset on basis of his rating or whether he solved B or not lolHe was mocking me for my comments I mocked him for his graph.These are unrelated. You need some humour man.
 » 2 months ago, # |   +100 Congratulations to ub33 for the 1e8-th submission!
•  » » 2 months ago, # ^ |   0 yayy!! congrats ub33
•  » » 2 months ago, # ^ |   +99 meow
•  » » 2 months ago, # ^ |   0 CONGRATULATIONS !!!!!!
 » 2 months ago, # |   -21 Is C's statement an english test? I can't understand it.
•  » » 2 months ago, # ^ |   0 C's statement is definitely hard to understand at first, need to google "ping-pong" after reading the statement
•  » » » 2 months ago, # ^ |   0 hm. later i solved it by guessing output from samples.
 » 2 months ago, # |   +40 Either I will live or geometry in this world !!
 » 2 months ago, # |   -36 It was a good round!! Really enjoyed the problemset which I could do :)
 » 2 months ago, # |   -37 How to solve E ???
 » 2 months ago, # |   0 ez game pls dont hack me pitch
 » 2 months ago, # |   +17 Use me as dislike button if you also didn't like this contest.
 » 2 months ago, # |   +6 Solved C in 1 minute after the announcement ;)
 » 2 months ago, # |   +2 It's the second time in a row that in a Educational Round problem C is easier then problem B what is this :(.
•  » » 2 months ago, # ^ |   +52 ObservationForces
•  » » 2 months ago, # ^ |   0 I think C easier then A. Because during contest I solved A help with pretests but C was really apparent but for understand what it says on C i need to read multiple times maybe this becomes C harder than A.
•  » » » 2 months ago, # ^ |   0 why didnt I look at C? I tried A, B and D
•  » » 2 months ago, # ^ |   0 So it's a good reason to start solving C firstly the next time. I think cfpredictor is a suitable work for you :)
 » 2 months ago, # |   +22 How to solve E?!
 » 2 months ago, # |   +5 Sounds stupid.. But someone help me with B
•  » » 2 months ago, # ^ |   -22 ll n; cin>>n; ll i; for(i=1;i<=n;i++){ if((i*(i+1))/2>=n) break; } ll ans=(i*(i+1))/2; if(n==1) cout<<1<=2) cout<
•  » » 2 months ago, # ^ |   0 After you draw the steps (don't come back initially) you will realize that you can come back by not making some pth move in front, but by just making it backwards. suppose you are at point y such that y>x, you need to check if there exists some p, such that (p+1) = (y-x). this accounts for not making the pth move in front, i dont have proof, but since p can take all natural numbers, it's always possible. and yeas if(y-x)=1 then add one.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I kind of have a proof so basically, y — x will always be less than or equal x, so let y-x be p so p can be written as 1 and p-1 which are steps which we have already taken 1 + 2 + 3 .... to remove the extra p we can remove 1 and p — 1 because they both sum up to p too, we can replace the p-1 step by taking -1 jump in p-1th step, and this way we can always remove any extra step taken. Also when we have y-x == 1 we cannot write it as 1 + some number, to remove it we need -1 so therefore an extra step is taken.
•  » » 2 months ago, # ^ |   0 U can go about like this--- u can see that x is less then 1e6 right and sum of first n natural numbers is n*(n+1)/2 which is approx the square of x so first u can create an array where u put the sun of first n natural numbers value of index i(1 based) will be sum of first i natural number now u can do a lower bound to check the value of index i. Now we are not done yet,let the array name be res now u need res[index] — x backward right so as u have already moved K steps what u can do is reduce j+1 for all j belongs to [1,index] i.e j dont not add j in the jth step but instead subtract 1 and thats how u can greedly approch at an optimal solutionSolution for B : https://ideone.com/HZvp8JNow i having trouble with problem C can someone help me understand it. For problem D can somewhere tell where i made a mistake would be grateful. D wrong solution dp approach link : https://ideone.com/i3lWQr
 » 2 months ago, # |   +3 Solved Div.2 D for the first time.
•  » » 2 months ago, # ^ |   -6 what was the fucking test 2 in C
•  » » » 2 months ago, # ^ |   0 Don't know.
 » 2 months ago, # |   0 A being as expected,B being a bit unexpected then comes the one liner C......XD crazy contest
 » 2 months ago, # |   0 How to solve c (please tell along with proof) ?
•  » » 2 months ago, # ^ |   0 print(x-1,y)
•  » » 2 months ago, # ^ |   0 Ans is always (x-1,y), since the 2nd player wants to maximize he always gets y points by loosing the first x-1 games and now player 1 has only 1 stamina and uses it to serve and player 2 reflects it to get his first point and wins the rest y-1 points after that.
•  » » » 2 months ago, # ^ |   0 how you can say that ? he also has to minimizes the apponent chance of winning can u please tell the proof why u r doing this little more ??
•  » » » » 2 months ago, # ^ |   0 but first priority is to maximize his own points
•  » » » » » 2 months ago, # ^ |   0 got it man , thanks can u tell how to solve B what was the intend/intuition behind the problem Thanks in advance ?
•  » » » » 2 months ago, # ^ |   0 The order is that in first place they want to win as much as possible. Only if they cannot win any more they will care for the other ones points.
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 How the above strategy ensures that bob cannot play in such a way that Alice wins less than x-1 times and he wins y times ?
•  » » » » » » 2 months ago, # ^ |   0 If you are not serving, its always optimal to lose the play and not lose stamina. This way you make the opponent lose stamina on the next try, since they compulsarily have to serve.
•  » » » » » 2 months ago, # ^ |   0 what if alice doesn't return in the 1st move?
•  » » » » » » 2 months ago, # ^ |   0 She has to. This is mentioned in the problem statement : "On the contrary, when the server commences a play, they have to hit the ball, if they have some stamina left."
 » 2 months ago, # | ← Rev. 2 →   +8 wasted 35 min on b then did c in 1 min then went to b for another 35 min to actually solve it. C must have been in place of A. C<=A
•  » » 2 months ago, # ^ |   +10 C easier than A. Seriously?
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 ok ,say C=A in difficulty,because, Ans is always (x-1,y), since the 2nd player wants to maximize he always gets y points by loosing the first x-1 games and now player 1 has only 1 stamina and uses it to serve and player 2 reflects it to get his first point and wins the rest y-1 points after that.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 I get C is easy but what did you find tough in A that you placed it after C? In A you don't even have to think anything.
•  » » » » 2 months ago, # ^ |   0 in A ans is always n.size(), where n is the string in input. So A easier than C.
•  » » » » » 2 months ago, # ^ |   0 similarly in c, answer is always (x-1,y) . :D
•  » » » 2 months ago, # ^ |   +8 Yes.
 » 2 months ago, # |   +80 I miss those times when Educational used to be great!
•  » » 2 months ago, # ^ |   0 lower end question may be interesting so try them !!!
 » 2 months ago, # |   +18 Thank you for the new mathforces round !
 » 2 months ago, # |   +5 Is it just me or the game thoery problems are a bit tough to understand?
 » 2 months ago, # | ← Rev. 2 →   +57 Strong dislike for C, it is completly based on observation and hence has no educational worth at all. That might be a nice problem, but simply misplaced in educational contest. It is basically no programming problem.
•  » » 2 months ago, # ^ |   0 Exactly. A,B,C were more about observation than implementation! -_-
•  » » » 2 months ago, # ^ |   +1 And D was just a blunt implementation of the statement.
•  » » » » 2 months ago, # ^ |   0 How to solve D using DP?
•  » » » » » 2 months ago, # ^ |   0
•  » » » » 2 months ago, # ^ |   0 This was more disappointing than ABC combined. ;_;
•  » » » » » 2 months ago, # ^ |   0 Was it intentional to give an implementation problem with low constraints to confuse low-confidence participants like me?
•  » » » » » » 2 months ago, # ^ |   0 I messed up because of the same reason. I think the intention was to let n^3 solutions pass too. if constraints were high there would've been less confusion.
•  » » 2 months ago, # ^ |   +8 The problem wasn't even interesting. Just trying to come up with possible ways of playing and hoping one of them is optimal.
•  » » 2 months ago, # ^ |   +7 Today's A,B,C were more like Atcoder's ABC contest A,B,C
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +10 Well, I did work like an hour on C and needed 7 submissions ;)
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +6 A,B were not as simple as A,B of atcoder's ABC .
•  » » » 2 months ago, # ^ |   +14 Atcoder's A is not a problem, but a solution!
•  » » » » 2 months ago, # ^ |   0 Epic XD
•  » » 2 months ago, # ^ |   0 Yes, C was very ambiguous for me
•  » » 2 months ago, # ^ |   0 I wouldn't say that it was a complete observation-based problem. I think the most obvious thought process was a greedy one : Prioritize wins which you can do by not interfering with the opponent's moves. The next part of minimizing the opponent's wins was trivial after getting the main idea. I would have liked it if this problem was B instead of C though.
•  » » 2 months ago, # ^ |   0 I won't say C was bad even though i was not able to solve it during contest . I didn't expected that observation will be so simple and was always thinking in complicated way .
•  » » 2 months ago, # ^ |   0 if the intended solution was minimax dp, It can be an educational problem.
 » 2 months ago, # |   +2 The best boring ping pong in C.
 » 2 months ago, # |   +69 I don't like this round. Learned nothing from ABC.
 » 2 months ago, # |   0 D was pretty easy,such a shame that I and made a terrible mistake kept failing to solve it.
 » 2 months ago, # |   0 How to deal with D?
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   +2 How to solve B ?
•  » » 2 months ago, # ^ |   +4 It was observation that you calculate $s = 1+2+3\, ...\, + k\ge n$. Now see that if $s = n+1$ then answer is $k+1$, otherwise it is $k$. This is because if you overstep by some amount $o > 1$ and also we have $o < k$ so we can do the $-1$ step on $(o-1)^{th}$ move and $+j$ step on other $j^{th}$ moves and so effectively we have reduced the sum to $n$, so answer is $k$. But if $o$ is $1$ then you must step back on $(k+1)^{th}$ move, so giving total $k+1$.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you explain me that how I reach to 7 in problem B
•  » » » » 2 months ago, # ^ |   0 You can follow the sequence $0, 1, 0, 3, 7$ (step back on the second step).
•  » » » » » 2 months ago, # ^ |   +3 Oh!I understand this.Thank you so much.
 » 2 months ago, # | ← Rev. 2 →   -8 .
 » 2 months ago, # |   0 How to solve B?
 » 2 months ago, # |   +57 I might get a lot of downvotes here, but I felt that $C$ was a pathetic problem, with no learning at all.
•  » » 2 months ago, # ^ |   0 You aren't wrong
•  » » 2 months ago, # ^ |   0 A should be a better example.
 » 2 months ago, # | ← Rev. 2 →   +6 What was the intended solution for problem D?? Was it DP or greedy??
•  » » 2 months ago, # ^ |   +7 greedy
•  » » » 2 months ago, # ^ |   0 I did dp, I guess there are more solutions.
•  » » » » 2 months ago, # ^ |   0 can you explain the dp solution plzzz
•  » » » » » 2 months ago, # ^ |   +3 dp[index][valueofx][0/1] So you can see that you have n+1 elements in total, let's rename them 1 -> k (where k is the number of distinct elements) The solution will have n elements from your n + 1 elements. For example, if your normalized values are 1, 2, 3, 4, 4 and x = 5 (in total 6 elements), you can see that the solutions can be something like 1, 2, 3, 4, 4 or 1, 2, 4, 4, 5 etc. (you pick 5 elements). index — means the element you are at valueofx — the current value of x after you do the operations on the first "index" elements 0 / 1 — you haven't skipped / have skipped an element (which means if you are still taking the smaller n elements, or have already skipped 1, so your solution will end with the n+1th) dp holds the answer obv. Try solving yourself from here on, since it is not hard.
•  » » » » » » 2 months ago, # ^ |   0 i got it thanks
•  » » » » » 2 months ago, # ^ |   0 The states are (current position i, Max element from [0,i), current x). Transitions are simple, you either make the current element x or you don't. My submission
•  » » » » » » 2 months ago, # ^ |   0 This is a way easier solution, but performs worse. But for this problem, n^3 is fine as well
•  » » » » » » » 2 months ago, # ^ |   0 Yup, I noticed the memory limit was 512 MB which was unusual from a general 256MB. So I decided to go with this since its pretty easy to implement
•  » » » » » » » » 2 months ago, # ^ |   0 If it would have been 256MB, you could have only kept the last 2 lines of dp, because you only need them. And had like dp[2][500][500]
•  » » » » » » » » » 2 months ago, # ^ |   0 that would work in iterative solution right? because in recursive dp, we can't remove the state $pos$ as far as i can think.
•  » » » » » » » » » 2 months ago, # ^ |   0 Isn't the current state unique for (i,x)? Submission
•  » » 2 months ago, # ^ | ← Rev. 2 →   +12 I used a greedy approach: First check whether the original array is already sorted or not. If it is sorted, print 0. Otherwise traverse the original array. Swap the value at current index with 'x' if it's greater than x and increment your answer by 1. At every step of the traversal check whether the Array has become sorted or not. The low constraints allows this. If it has become sorted print your answer. At the end of the traversal if the array is not sorted print -1.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +10 It was a greedy solution. I solved it this way: Notice that $x$ is monotonically strictly increasing. If at any point, for any $i$ starting from $1$ to $n$, $a_{i \dots n}$ is sorted, break out. If for any $i$, $a_i > x$, do the operation. As an operation can only lower down the value of an element, so it is optimal to lower down the values when possible starting from the left. Finally, at the end check if $a$ is sorted, if it is, then print the moves you took, else print $-1$. Update: Cleaner and faster code.C++ Code: 100058194Time Complexity: $O(n)$Auxiliary Space: $O(1)$
 » 2 months ago, # |   +7 Problem C was really ambiguous. Strongly dislike it.What was the point of it?
 » 2 months ago, # |   0 Maybe my complexity analysis was wrong. But I think I probably submitted an O(n^3) solution to the problem D where the sum of n over all test cases was <=500. Am I missing something in my complexity analysis? I would be glad if someone helped out.My submission: 100048016
 » 2 months ago, # |   +10 Got VERY stuck on B ;(.
 » 2 months ago, # |   +2 Interesting problem С, liked it. But, in my opinion, problem B is more difficult than problem C :(
 » 2 months ago, # |   +10 neal's stream is running now, feel free to join :)https://codeforces.com/stream/71
 » 2 months ago, # |   +6 I can't believe D is just mostly implementing what they given, I overthought that so hard D:
•  » » 2 months ago, # ^ |   0 Ikr. i don't see why it was a D. Q.Q
•  » » 2 months ago, # ^ |   +1 Hey, I iterated on the input array and every time check whether input array is equal to sorted input array if that's the case print answer and return else if the current element is greater than X then swap it. Here is the implementation of the same.
•  » » » 2 months ago, # ^ |   0 Thanks!!
•  » » » 2 months ago, # ^ |   0 Can you explain why this solution will work?
 » 2 months ago, # |   0 what is hacking here? How can we hack? Can we hack anyone? please enlighten me..:)
 » 2 months ago, # |   -12 how to solve b
•  » » 2 months ago, # ^ | ← Rev. 2 →   +1 Find the cnt where cnt*(cnt+1)/2 is just greater than x Then find by how much it is greater than x,let it be y=(cnt*(cnt+1)/2)-x; Now just we have to remove the step y which can be done without any extra step. if y>1 so ans = cnt and if y==1 ans=cnt+1Let's say x=7.So cnt=4; And the guy moved 1+2+3+4 steps. Then his final position is at step 10; y=(1+2+3+4)-7=3 Only if he could move 3 steps behind then the problem will be sorted. So we just need to remove the step size 3. So lets do Step 1: +1 position =1 Step 2: -1 position =0 Step 3: +3 position =3 step 4: +4 position =7So we get the minimum number of steps as cnt=4
•  » » » 2 months ago, # ^ |   0 if y>1 so ans = cnt, why is this always happening?
•  » » 2 months ago, # ^ | ← Rev. 2 →   +3 For B, let's use only +i as long as sum < X. +1 +2 +3 +4 ... + K = S (>=X) If we switch a "+i" to "-1", then S updates to S-i-1 That is great, because for i = 1, 2, 3.. it is -2, -3, -4 ... -K on S with no more jumps (result = K), and we could reach any S, S-2, S-3, ... except S-1, in which case we need an additional "-1" jump (result = K + 1).
 » 2 months ago, # |   0 How the answer of B for n=12 is 5 ?
•  » » 2 months ago, # ^ |   0 1 + -1 + 3 + 4 + 5
•  » » 2 months ago, # ^ |   0 1 -1 3 4 5
 » 2 months ago, # |   0 How to solve B？It took me an hour and a half to solve problem B,but I did not succeed in solving。
•  » » 2 months ago, # ^ |   +8 Find the cnt where cnt*(cnt+1)/2 is just greater than x Then find by how much it is greater than x,let it be y=(cnt*(cnt+1)/2)-x; Now just we have to remove the step y which can be done without any extra step. if y>1 so ans = cnt and if y==1 ans=cnt+1Let's say x=7.So cnt=4; And the guy moved 1+2+3+4 steps. Then his final position is at step 10; y=(1+2+3+4)-7=3 Only if he could move 3 steps behind then the problem will be sorted. So we just need to remove the step size 3. So lets do Step 1: +1 position =1 Step 2: -1 position =0 Step 3: +3 position =3 step 4: +4 position =7So we get the minimum number of steps as cnt=4
•  » » » 2 months ago, # ^ |   0 Really,really thanks a lot man!
•  » » » » 2 months ago, # ^ |   0 Welcome !!
•  » » » 2 months ago, # ^ |   0 And for x=11?
•  » » » » 2 months ago, # ^ |   0 1 2 -1 4 5
 » 2 months ago, # |   +7 MarcosK Make a nice hacks for E
•  » » 2 months ago, # ^ |   0 Doesn't it mean that someone did bad tests?
•  » » » 2 months ago, # ^ |   0 They don't need to have perfect test btw you can resubmit if you think your solution bad while accepted this means no one says pretest are perfect
•  » » » » 2 months ago, # ^ |   +5 What? What is your point? Do you wanna say that it's normal that in all tests $t \leqslant 10^3$ while $t \leqslant 10^4$ is in statement?
 » 2 months ago, # |   +1 This was my first contest ....can someone please send me solution for strange functions A question ? Pls it will be of great help ...thanks
•  » » 2 months ago, # ^ |   0 You simply have to print the length of the input for this question
•  » » 2 months ago, # ^ |   0 You just have to print the length of the input. while(t--) { string n; cin>>n; cout<
•  » » 2 months ago, # ^ |   0 Its just the number of digits in the number.Reason: Any number without starting or ending 0s will give g(x)=1. We get a different value for g(x) only when a number contains 0s at the end(i.e. multiples of 10).EG: for if n=124, take 100. We get g(x)=100 as it is (100/1). We get g(x)=10 from x=40. So the answer is 3(1,10,100)The various values of g(x) possible are 1,10,100,1000,etc.
 » 2 months ago, # |   +40 The constraint of $E$ is $1\le t \le 10^4$,but the maximal $t$ for the tests are $1000$ only...That's why there can be a lot of hacks in $E$...
•  » » 2 months ago, # ^ |   +8 Out of curiosity, was the limit for $t$ originally $10^3$ and not $10^4$ awoo? I had a solution without ternary/binary search in mind, but I saw my solution passed in only 483 ms, so I assumed that it most likely wouldn't be hacked :P
 » 2 months ago, # |   +15 Is it codeforces or ObservationForces?
 » 2 months ago, # |   +92 This was a really nice round, but I have to complain about problem E. I hacked more than 40 submissions (including mine), just because the complexity is $O(log(10^9) * 4!)$, and all of them exceeded time limit because of having 10^4 subtests. I don't get the decision of the setter about it.Besides that, thank you for the round, i loved the problems!
•  » » 2 months ago, # ^ |   +81 Theoretical computer scientist: That is O(1) XD
•  » » 2 months ago, # ^ |   +30 My solution is $O(4!)$ if we allow such notation. Initially, I didn't intend to make limits so tight and wanted to allow sub-optimal solutions but, I'm sorry, I messed up with tests.P.S.: it's a little strange that something that looks like $t \cdot \log^2$ doesn't pass with $t \le 10^4$.
•  » » 2 months ago, # ^ |   0 Wait, that sounds weird. 2 sec TL, log(10^9) is ~30, 4! is 24, then for all tests we have 7200000 (7M) total. How that could be TL?
•  » » » 2 months ago, # ^ |   0 In most of the codes, the constant factor is not small. For example, some codes perform more than one binary search. My hacking method was:Open submission. Look for a binary/ternary search. If there is one, send a hacking attempt with $t=10^4$. Successful hacking attempt.Of course it didn't work in 100% of the submissions, but I did more than 40 hacks in that way :P
•  » » » » 2 months ago, # ^ |   0 That’s all pretty cool, but math is math: constant factor should be very big to jump from 7M to TL. Hack is hack, good for you, just very weird.
 » 2 months ago, # |   +5 problem C was much much easier than b.
 » 2 months ago, # |   -8 any tutorial for b please
•  » » 2 months ago, # ^ |   0 This comment
 » 2 months ago, # |   +10 A~D: No programming, just observation and math...
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 well , I solved D with DP , is there another solution?
•  » » » 2 months ago, # ^ | ← Rev. 4 →   0 We will iterate over the given array a from beginning. If a[i] <= x, we can't change the value. If a[i] > x and a[i] should be changed to sort the whole array, we should swap a[i] and x — if we don't, it cannot be corrected later. After each swap, I checked the array is sorted. If then I escaped the loop and printed # of swaps.If the array is not sorted after all swap, print -1. We can solve the problem by this greedy approach.
•  » » » » 2 months ago, # ^ |   +1 That's problem B, not problem D.
•  » » » » » 2 months ago, # ^ |   0 Oh, it's my mistake. I will edit the comment.
 » 2 months ago, # |   +32 No offense to the writers but I don't really think this contest is educational.
 » 2 months ago, # |   +30 Adhoc-Forces crossed 100 million+ submissions. wow!
 » 2 months ago, # |   +8 How to solve Problem E?
•  » » 2 months ago, # ^ | ← Rev. 3 →   +25 Essentially you are compressing the x and y co-ordinates each to two distinct values, and the problem has many similarities to making all elements of an array equal. In the array problem, you compress all elements to be equal to the middle value, or in the case of an even-length array, one of the middle values.In this problem, we want to compress the co-ordinates such that x and y deltas are minimal. If we sort our starting X co-ordinates (X1,X2,X3,X4) and starting Y co-ordinates (Y1,Y2,Y3,Y4), ideally we will compress them such that all x co-ordinates are between X2 and X3 inclusive, and all Y co-ordinates will be between Y2 and Y3 inclusive. The optimal length of the square, L, will be the max(Y3-Y2,X3-X2), since we don't want to compress the square more than necessary.Suppose we cannot fit the whole square inside the bounding box X2 to X3 and Y2 to Y3. Then we want as much of the square as possible to be inside that bounding box, and as much of the rest of the square to be inside the bigger bounding box X1 to X4, Y1 to Y4. It can be seen quite easily by drawing an example that any shift outside of these bounding boxes is sub-optimal.So we can say the bottom left corner of our square is at (min(X2,X4-L),min(Y2,Y4-L)). [Note the we equivalently could have positioned the top right corner at (max(X3,X1+L),max(Y3,Y1+L))].Therefore we have the four co-ordinates of the optimal square. From there we can try all 24 permutations of starting points to corners, and find the optimal one. There may be a neater way to do this final step, but I brute forced it as 24 is not many.
•  » » » 2 months ago, # ^ |   0 I dont get it how here the connection between x and y is done. Since it is a square x and y size of resulting rect must be same. But the logic separates the x from the y coordinates :/
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 The logic combines the x and y results, though. Length (both horizontally and vertically) = max(Y3-Y2,X3-X2), so the length is determined by the x and y co-ordinates Bottom left corner of square is at (min(X2,X4-L),min(Y2,Y4-L)), so the position of the square is also determined by the x and y co-ordinates
•  » » » 2 months ago, # ^ |   +5 This is my approach for E after taking some ideas from jimm89 : int x[4], y[4], old_x[4], old_y[4]; for(int i = 0; i<4; i++){ cin>>x[i]>>y[i]; old_x[i] = x[i]; old_y[i] = y[i]; } sort(x, x + 4); sort(y, y + 4); int b_a_u = x[3] - x[0]; // The upper limit for difference of x2 and x1 where x1 and x2 are defined below int b_a_l = x[2] - x[1]; int d_c_u = y[3] - y[0]; int d_c_l = y[2] - y[1]; int side = min(b_a_u, d_c_u); int x1 = max(x[0], x[2] - side); int x2 = x1 + side; int y1 = max(y[0], y[2] - side); int y2 = y1 + side; cout<
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 Looks like a nice variant on the same ideas. Nicely done.My in-contest submission was a little messy as I was very short on time, and a little panicked. Afterwards I tidied it up.
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 Here is a case-work based solution (no binary search) to problem E: https://codeforces.com/contest/1455/submission/100073456.Edit: I'm not sure if this solution is always correct.
 » 2 months ago, # |   0 A
 » 2 months ago, # |   -13 Guys look at the topic(contest) rating, going to zero XD
 » 2 months ago, # |   +6 How to solve E?
•  » » 2 months ago, # ^ |   0 Some explenation on E would be of educational worth.
•  » » 2 months ago, # ^ |   +4 I just posted my method above — I hope it makes some sense.
•  » » 2 months ago, # ^ | ← Rev. 4 →   0 Here is a case-work based solution (no binary search) to problem E: https://codeforces.com/contest/1455/submission/100073456.Edit: I'm not sure if this solution is always correct.
 » 2 months ago, # |   +66 Me after reading the solution of problem C
 » 2 months ago, # |   0 Coded an n^3 solution for D using DP, is it hackable? 100060462
•  » » 2 months ago, # ^ |   +5 Problem statement guarantees: The sum of values of n over all test cases in the input does not exceed 500. So (sum of n) * 500^2 operations should be fine.
•  » » 2 months ago, # ^ |   0 no problem with the given constraints n^3 solution passes
 » 2 months ago, # |   +1 Is the round difficulty below average ?
 » 2 months ago, # |   +12 G was nice, thanks authors! Sadly, I needed 20 more minutes to solve it :)
 » 2 months ago, # |   0 is their hack points in this contest??
 » 2 months ago, # |   0 Solving A-D feels like guess some conclusion and just try it...Even don't need to think seriously. Am I too impulsive?
•  » » 2 months ago, # ^ |   +63 I own none of these problems' ideas but I personally find the observation problems the hardest of them all. They tend to make me think a lot more than the standard-ish ones and usually way more than it takes people of my rating :( The fact that you don't need to think seriously just shows that you have better intuition I guess. So you can enjoy your "free" rating and the guys like me can enjoy practicing more in this kind of problems :P
•  » » » 2 months ago, # ^ |   +3 I also got immediate ideas for A, C, and D but didn't believe them in the first place so spent a lot of time proving them :(
 » 2 months ago, # |   +66
 » 2 months ago, # | ← Rev. 2 →   -45 Hello nerds,I think contests of codeforces also drowning into the scam of plagiarism and it can be seen that moss checker isn't giving justice to the genuine programmers who really work hard to get better in every other contest and they don't get their deserving ranks because of some people take this place as fun and plagiarise easily get the good ranks this gives a lots of demotivation to genuine guys.So i request codeforces community(BledDest ,awoo,MikeMirzayanov,Roms,adedalic,vovuh,Neon) to check these submission neutrally and if found guilty required action should be taken. https://codeforces.com/contest/1455/submission/100047211 https://codeforces.com/contest/1455/submission/100051933Thank YOU
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I agree they have same code. Please take action BledDest
 » 2 months ago, # |   +33 I can't understand why so many people downvote a contest. Just for the problems? ok but also the writers and the testers make some effort to gives us these contests. And about the problem : Easy A like always , a easy math problem for B , C an observation one and D greedy (I Didn't understand that N <= 500 but that is not an issue). If A-D were easy why just 300 make at least 5 problems? You can say , was a huge gap between D and E and I agree , but that s not a reason to downvote a contest. I enjoy every contest (and I would like to see more DP and graph problems in div2 and Educational contests)
•  » » 2 months ago, # ^ |   0 problem D I solved it DP lol. I didn't even think. I just wrote the code and AC that is why $N<=500$ so dumb people like me could write a standard DP solution :/
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +9 N=500 you can get accepted with O(N^3) if I am not mistaken. I think N=5000 was better but that's the most irrelevant thing in this contest
•  » » » » 2 months ago, # ^ |   0 i guess it was intended that authors wanted N^3 dp solution to pass, that's why n=500, just doubling N would have cut dp solution.
•  » » » » » 2 months ago, # ^ |   0
•  » » » » » » 2 months ago, # ^ |   0 i am wondering that why it doesn't depend on $prev$ state in dp. can you please elaborate on this?
•  » » » » » » » 2 months ago, # ^ |   0 I'm very bad at proof and explanation but here's a try. I thought of it this way, dp(i,x) is the min number of steps needed to sort [0,i]. Obviously, the configuration we are considering might be invalid so i return inf in that case. I did not consider prev, because I'm swapping x and a[i] in every move. so if x=a[y] for any y at idx i, I can be sure that I've sorted from [0,y] and infact used moves from [0,y]. From [y+1,i] I have not used the moves. This is enough to uniquely define the state of the array. I might be wrong, if so please correct me.
•  » » » » » » » » 2 months ago, # ^ |   0 Nice explanation @nagraj41. More formally, I think that is what he means.https://codeforces.com/blog/entry/85116?#comment-728332
•  » » » » 2 months ago, # ^ |   0 I coded DP solution with O(N*X). Even if N=5000 then also it will pass. So I chose DP over greedy as I will learn something.
•  » » » 2 months ago, # ^ |   +7 Wish I was dumb like you!
•  » » 2 months ago, # ^ |   0 People didn't like problems so they downvote, what's wrong with that? — Errichtosource
 » 2 months ago, # |   0 Good contest. Finally I can be expert
 » 2 months ago, # | ← Rev. 2 →   0 hi all, in problem B,if we consider only the first operation jumping to y+k, then we can do the following jumps,on 1st jump 0 to 1on 2nd jump 1 to 3on 3rd jump 3 to 6on 4th jump 6 to 10so we get the following series of 1 3 6 10 15....now what i did is stored this series upto the given constraint of x which is 10^6 in a vector a. Then if x is just greater than or equal to any a[i] I calculate ans=i+1+a[i]-x where i+1 is the jumps to reach a[i] and a[i]-x is to move back to x by using the second operation y-1;now after this I noticed this that for x=4 following is the optimal operation1st jump 0 to -12nd jump -1 to 13rd jump 1 to 4then i noticed if we do this kind of operation for any x(except 1 2 3) the total number of jumps will be x-1;so at last i took min(ans,n-1).is my approach wrong?pls help here is my code
•  » » 2 months ago, # ^ |   0 You seem to have made a few false assumptions, just trying to get your formula to match the example solution.The main problems are that the min with n - 1 doesn't really play a role for larger n, as the answer starts to increase much slower than $n$. The other one is that the answer will be the same for multiple consecutive $n$, where a[i] stays the same, but your formula does not account for that.Thus, as the second test shows, for example with input $7$, a[i] is $10$, i is $3$, and it is possible to reach $7$ with the sequence $0, 1, 0, 3, 7$ ($4$ jumps), but your formula gives $3 + 1 + 10 - 7 = 7$, and with the minimum $min(7 - 1, 7) = 6$.
 » 2 months ago, # |   0 Problem G is really nice.Thanks!
•  » » 2 months ago, # ^ |   0 What should be the problem rating for E,F,G in the contest according to you?
•  » » » 2 months ago, # ^ |   0 Sorry ,I haven't read E&F.For me G is about 2600.
 » 2 months ago, # | ← Rev. 2 →   +7 I can't understand why people are writing wrong code and then hacking theirselves like this guy — You_Will_Be_Hacked
•  » » 2 months ago, # ^ |   0 They are most likely coping someone else's code and testing their hacks on the dummy account.
 » 2 months ago, # |   0 Observed Cth problem solution printf(x-1,y) just in 1 minute but thought how can it's solution be so dumb! And then wasted 30 min and submitted wrong and most dumbest solution ever. RIP my rating.
•  » » 2 months ago, # ^ |   0 f
 » 2 months ago, # |   +6 I personally believe that if problem C was given as Problem A I would have come up with a solution much faster, I just thought since it was a C problem, it can't be so simple!
•  » » 2 months ago, # ^ |   0 Me too :(
 » 2 months ago, # |   +3 Can we apply BFS in B problem??
•  » » 2 months ago, # ^ |   0 I know u r gr8 at graphs but why for this problem
 » 2 months ago, # | ← Rev. 2 →   +1 Solved D with DP and used only two states — [index][x]. I thought that x and prev are inter-related. I also tried [index][prev] but it was wrong. Is it wrong and just a coincidence with test cases? https://codeforces.com/contest/1455/submission/100080134
•  » » 2 months ago, # ^ | ← Rev. 3 →   0 (i,x,prev) (i,x) They are inter-related according to me. How is it wrong?
•  » » » 2 months ago, # ^ |   0 Can you please explain why both these states are inter related? What redundant information are we providing in 3D DP?
•  » » » » 2 months ago, # ^ |   0 Does this help? In other words, if prev!=v[i-1] then it's obvious that it has been swapped till i-1. you will see that the prev does not matter when you have fixed x because it's v[i-1] if not swapped, and previous x if swapped.
•  » » » » » 2 months ago, # ^ |   0 Thanks for your explanation. I think I got the gist.For any state to be uniquely defined. You need 3 information here: - current index - x on the current index - Maximum value till now on [0, curr_index-1]Since you only proceed further when you are convinced that [0,curr_index-1] is sorted, you can derive the 3rd information from the first 2.That is, it will always be arr[curr_index-1] (considering you have made swaps in the array wherever needed).Thus the 3rd condition is redundant and can be removed only because of the virtue of having a sorted array.I hope I got it right?
•  » » » » » » 2 months ago, # ^ |   0 Yeah that's pretty much what I meant.
•  » » 2 months ago, # ^ |   +3 Oh, that's a nice idea to remove the index from the state as it is not providing us any useful information, just telling on which step we are. So, it makes sense to just focus just on values at step and step — 1
 » 2 months ago, # |   0 anything on when ratings will be displayed?
 » 2 months ago, # |   0 It has been 12 hours since the contest ended. My rating didnt change. Wasn't this contest rated?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Div 3 and Educational round gives 12 hours for open hacking. After that, system testing starts and rejudge all the solutions. Then rating gets updated. System testing isn’t started yet.
 » 2 months ago, # |   0 I'm curious why Educational Round doesn't system test instantly after finishing the hacking phase.
•  » » 2 months ago, # ^ |   0 Me too :)
•  » » 2 months ago, # ^ |   0 I think some successful hacks are added to the system tests.
 » 2 months ago, # |   -8 Ratings will be displayed as soon as system testing complete.
 » 2 months ago, # |   0 Next time add/change notes or info in the main problem page too. In problem C, changes didn't show up after refreshing the page.
•  » » 2 months ago, # ^ |   0 There was no change in problem statement. Announcement for the explanation and that was writing on problem statement.
•  » » » 2 months ago, # ^ |   0 Well, it was an explanation and it should have been included in the lower section.
 » 2 months ago, # |   +6 where is the editorial?
 » 2 months ago, # |   +3 Where are the tutorials?
 » 2 months ago, # |   0 Can we solve 2nd using dp?
 » 2 months ago, # |   0 Can anyone tell me why am i wrong ? :'< https://codeforces.com/contest/1455/submission/100029658
 » 2 months ago, # |   0 Is it rating???
 » 2 months ago, # |   -50 Below average problem set.Cf standard going downward day by day
•  » » 2 months ago, # ^ |   0 Why, then, could not solve problem E, since the standard is easy?
•  » » » 2 months ago, # ^ |   +22 The answer is in your comment XD The guy who cannot solve E,solved ABCD within 50 minutes! and no ds recquired till D! Neither a hard implementation problem nor any requirement of hard observation or ad-hoc logic till D -_- so you want to treat problem D as B in previous difficulty standard, Nice. Clap clap
 »