### Stepavly's blog

By Stepavly, 5 months ago, translation,

Hello, Codeforces!

<almost-copy-pasted-part>

Hello! Codeforces Round #713 (Div. 3) will start at Apr/10/2021 17:35 (Moscow time). You will be offered 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. However, all of you who wish to take part and have a rating 1600 or higher, can register for the round unofficially. The round will be hosted by rules of educational rounds (extended ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round, it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

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

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

The problems for this round were invented by MikeMirzayanov, Supermagzzz, Stepavly and sodafago.

Thanks Gassa, darkkcyan, bfs.07, Tzak, songsinger, Mukundan314, iankury, drunya, sodafago, ChOmPs, Programmer, Khairy, IITianUG, Rox for helping with testing the round!

Thanks to MikeMirzayanov for platforms and coordination of our work. Good luck!

</almost-copy-pasted-part>

Editorial: https://codeforces.com/blog/entry/89535

• +124

 » 5 months ago, # | ← Rev. 3 →   -32 UPD : sorry
•  » » 5 months ago, # ^ |   +13 And why exactly you gave this guy so many negative reviews?
•  » » » 5 months ago, # ^ |   +36 This is the third time I've seen the same meme in announcement blogs
•  » » » » 5 months ago, # ^ |   +25 Yeah I have seen it before too
•  » » » 5 months ago, # ^ |   0 This guy has been getting upvotes on copy-pasted memes even before this lmao
•  » » 5 months ago, # ^ | ← Rev. 2 →   -54 All the best!
 » 5 months ago, # | ← Rev. 2 →   +54 is it only me who see only this announcement in russian and rest are in english?UPD : Now it is fine for everyone :)
•  » » 5 months ago, # ^ |   +2 No announcement is in russian
 » 5 months ago, # |   -52 from today all indian coders have a big problem wheather to give codeforces round or to watch IPL
•  » » 5 months ago, # ^ |   +20 Ofc codeforces's contests!!
•  » » 5 months ago, # ^ |   +1 Any sane person would prefer the former one.
•  » » » 5 months ago, # ^ |   +4 i know that is just a joke
•  » » 5 months ago, # ^ |   +9 no
 » 5 months ago, # |   -19 Is it rated?
 » 5 months ago, # | ← Rev. 2 →   0
•  » » 5 months ago, # ^ |   0 UwU
 » 5 months ago, # |   0 OK thank You
 » 5 months ago, # |   -13 Finally a Div 3 contest on weekend! Thanks for making it a reality :-)
 » 5 months ago, # |   -28 Plz change time since there is an IPL match.
 » 5 months ago, # |   +7 I think Everyone Love to see it :)
 » 5 months ago, # | ← Rev. 2 →   0 Yep, my mistake, Sorry!
•  » » 5 months ago, # ^ |   -16 CodeJam is runnig.will be finish in 10 min. then how The timing of Google Codejam clashes with this content?????
 » 5 months ago, # |   +1 I wish i would solve atleast 3 to 4 problems in this contest
•  » » 5 months ago, # ^ |   0 me too !!
•  » » 5 months ago, # ^ |   0 me too
 » 5 months ago, # |   0 Good luck to all
 » 5 months ago, # |   0 may the force be with you
 » 5 months ago, # | ← Rev. 2 →   -28 Old but still best......
•  » » 5 months ago, # ^ |   +7 should be rating and not rank (rank may increase/decrease).
•  » » » 5 months ago, # ^ |   0 same for rating, it should be !(entropy)
 » 5 months ago, # |   +4 After a long time,I've got my focus back & feeling the same excitement I was used to feel.Hoping the contest will end smoothly.Good luck to me, Codeforces and all. :-) (Thinking,what will happen if Codeforces have an emoji that express excitement levels? :3)
 » 5 months ago, # | ← Rev. 2 →   +8 It's sad that I can't participate in this Div. 3 because of my courses...Maybe I'll participate in the Div. 2 tomorrow, but I'm not quite sure yet. Maybe I will be absent in CF contest for a long time...btw, wish me good luck for my senior high school entrance examination QAQ
•  » » 5 months ago, # ^ |   0 Best of Luck!!!
•  » » » 5 months ago, # ^ |   -10 .
•  » » » 5 months ago, # ^ |   0 Thanks very much :)
 » 5 months ago, # |   +4 aboba
 » 5 months ago, # |   0 first time doing contest.... it's hard for me....(cry....:<)
•  » » 5 months ago, # ^ |   +14 This was the lowest division and in my opinion, the problems were easier than other Div3 contests. I'm not saying this to discourage you but to give you advice. Maybe codeforces is a little too hard to start with. You can learn the basics from this website (https://www.pbinfo.ro/). It's a website from my country which takes you from zero to hero (or at least doing the first 2-3 problems in Div2 in less than 1 year, haha) You only have to translate the page to English when you enter the site. Good luck with your coding journey! I hope I gave some positive thoughts!
•  » » 5 months ago, # ^ |   0 dont listen to alexadru7, just solve 800s instead, and if those are still too hard, do leetcode (but they shouldn't be that hard)
•  » » » 5 months ago, # ^ |   0 Thx...I'll try it!
 » 5 months ago, # |   0 Thanks for the great round!
 » 5 months ago, # |   +1 Please someone give idea for Problem E. Thanks in advance!!
•  » » 5 months ago, # ^ |   0 First take the at least number if l to r difference is 3 then take the number 1 2 3 if its greater than s then answer must be -1. other wise try to replace every number with large unused number as if sum of those number not exceed s. if sum==s you find the result. implementation
•  » » 5 months ago, # ^ |   0 you_ create new array have size = r-l+1. make array from 1 to r-l+1. add 1 to arr[pos]._ _You start with pos = size — 1. if arr[pos] == pos then pos--
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 Here $sum(x)$ denote sum of $1, 2, 3, ..., x$. Let $len=(r-l+1)$. A solution exists if and only if $s>=sum(len)$ && $s<=sum(n)-sum(n-len)$. Now to simulate the process, take numbers from $1$ to $len$ in an array (arr). And take numbers from $len+1$ to $n$ in a set (st). Let's denote $left$ as the sum remaining i.e. $left = s - sum(len)$. Now, you can start from last element of array do this while $left>0$. for i from len to 1: if(left==0) break y=arr[i]+left if(st.contain(y)): arr[i]=y break else: remove greatest element from st say g insert arr[i] in st left=left - (g-arr[i]) replace arr[i] with g Once you have got arr with sum s, you can add remaining elements at other positions. see my submission
 » 5 months ago, # |   +1 I can't tell if I've gotten better, or if this round was just easier :/
•  » » 5 months ago, # ^ |   0 really easier than other div 3.
 » 5 months ago, # |   -24 Video Tutorial A and B:https://www.youtube.com/watch?v=9ZMkngzyJtY
 » 5 months ago, # |   +2 Can someone help me in solving problem E?? I tried by using no from 1 to x-2(where x = r-l+1) whose sum will be equal to sum = (1+2+3+...+x-2), and found two no whose sum was equal to s — sum. I don't know the proof of this method. Someone kindly help.
•  » » 5 months ago, # ^ | ← Rev. 4 →   0 Here's an example for n = 10, l = 3, r = 7, and s = 21.We want to find the numbers that will be in the sum. First we try:1 2 3 4 5 / 2 3 4 5 6 / ... 6 7 8 9 10Then find the two sums that s is in between.Over here, it is 2 3 4 5 6 and 3 4 5 6 7.Now, since 3 4 5 6 7 is too large, we need to decrement some of the numbers one by one.Since 25 — 21 = 4, we decrement 4 of the numbers, and to ensure no collisions occur we decrement 3, 4, 5, 6.So the numbers included in the sum are 2 3 4 5 7.Now, just put these numbers so that they occupy positions 3 ... 7.
•  » » » 5 months ago, # ^ |   0 That's what i wrote. But I got the second example wrong. I want to know why.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 LOL, ignore.
 » 5 months ago, # |   0 codell c; cin>>c; //for(int i=0;i<=c;i++) {cout< mp; ll n=i; while(n!=1){ if(seive[n]==1) {mp[n]++;break;} mp[seive[n]]++; n/=seive[n]; } ll sum=1; for(auto x:mp){ sum*=(((ll)pow(x.first,x.second+1)-1)/(x.first-1)); } //deb(i,sum); if(sum==c) ret(i); } ret(-1) why my code is giving TLE for problem G?
 » 5 months ago, # | ← Rev. 3 →   +27 I'm curious what the intended $O(n ^ 3)$ solution to E was, there is actually a pretty nice solution to that can be made to run in $O(n)$.For the subarray $[l, r]$, if a solution exists, then there always exists a solution of the form:$1, 2, \ldots, i, j, k, k + 1, \ldots n$, where $i \lt j \lt k$.(We can always shift terms equivalently left / right to reach this for some $i$ and $k$ from any valid solution)Since size is fixed, $k$ also depends only on $i$. So we can just iterate over $i$, calculate the sums of $1 \ldots i$ and $k \ldots n$ and then check if the $i \lt s - sum \lt k$.I implemented it in $O(n ^ 2)$ during contest by trivially iterating to calculate sums in $O(n)$ time for each iteration, but it can be done in $O(1)$ time per iteration using prefix sums or summation identities.
•  » » 5 months ago, # ^ |   0 I did not understand from the statement k also depends on i.Can you please elaborate as to what you have taken as i and c and k
•  » » » 5 months ago, # ^ |   0 Sorry I meant $s$, not $c$, got confused between the characters representing the needed values in different questions.So we want to select $r - l + 1$ values, right?So if I know that I'm taking $i$ values at the start $(1, 2, \ldots, i)$, and I'm going to select a single number later as $j$, then I want to select $(r - l + 1) - (i + 1)$ values for the part $(k, k + 1, \ldots, n)$. So we can write $k$ completely in terms of $i$ as $n - ((r - l + 1) - (i + 1))$
•  » » 5 months ago, # ^ |   +7 E was apparently available on stackoverflow https://stackoverflow.com/questions/46296588/distinct-n-numbers-so-that-sum-equals-to-n
•  » » 5 months ago, # ^ |   +10 I didn't read sum of $n$ over all testcase is $500$ and took a lot of time to solve in $O(nlogn)$. About your intended solution $O(n^3)$ I think we can solved it like $0-1$ Knapsack. Since sum $s<=n(n+1)/2$
 » 5 months ago, # | ← Rev. 3 →   0 I think Blog should be update Cz it div3 : do not have a point of 1900 or higher in the rating.it should be: do not have a point of 1600 or higher in the rating.UPD: It's my mistake :)
•  » » 5 months ago, # ^ |   0 no
•  » » 5 months ago, # ^ |   0 Thats for trusted vs untrusted standings, not the rated part. Basically what it means is that if someone has peak rating $\geq 1900$, even if their current rating is $\lt 1600$, they won't appear in the official standings. Basically its meant to stop people from smurfing to specialist to appear at the top of the official standings of a Div3.
 » 5 months ago, # |   0 Was the intended solution for problem F is DP ?
•  » » 5 months ago, # ^ |   0 I also think so. but it's not dp. you_ create new array have size = r-l+1. make array from 1 to r-l+1. add 1 to arr[pos]. _You start with pos = size — 1. if arr[pos] == pos then pos--.
•  » » » 5 months ago, # ^ |   0 problem F dude. I think you are talking abt problem E.
•  » » » » 5 months ago, # ^ |   0 oh. so sorry
•  » » 5 months ago, # ^ | ← Rev. 2 →   +9 you can prove that in the optimal solution,you will spend minimal days reaching a position then stop and only earn tugriks on that position until you pass c,so iterate over which position you stop at
•  » » » 5 months ago, # ^ |   0 hey, can you please share your solution? I thought almost the same but guess I missed some corner case.
•  » » » » 5 months ago, # ^ |   0 my sol is the same as editorial
•  » » » » » 5 months ago, # ^ |   0 Funny thing, i thought that but couldnt get it to work
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I don't think so. It can be solved by using Greedy. Assume Polycarp last at position i, then for position before i, upgrade to next position as soon as possible will be the best way.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +3 My approach was array day[i] carries the number of days to reach position i and the rem[i] the number of money i start with at position ithen i get the minimum of days[i] + ceil(( c — rem[i]) /arr[i])i really don't know if it consider dp or not
•  » » 5 months ago, # ^ |   0 yup. You can calculate the number of days required to reach every position and tugriks left after reaching every position. Then calculate the number of days required for each position and take the minimum. You can also do it in the single loop. I made a very silly mistake in this :(
 » 5 months ago, # |   0 Thank you for the effort you put into the contest.
 » 5 months ago, # |   0 contest ended at 10:05 ist, code submitted and ac in one go at 10:07 ist. Life.
 » 5 months ago, # |   0 Contest was easy but a lot of code was there to write .
 » 5 months ago, # |   0 can problem E solved by knapsack?
•  » » 5 months ago, # ^ |   0 cant store an array of 500 as a dpstate ? or you meant problem F ?
•  » » 5 months ago, # ^ |   0 I think so, but the problem is that you should consider amount of taken items, it is fixed
•  » » 5 months ago, # ^ |   +1 I get AC with greedy
•  » » 5 months ago, # ^ |   +8 Maybe, but if so its tougher than other solutions in my opinion. I thought about this at first, but the best state I could come up with was $dp[\text{current number(1 to n)}][\text{count of taken}][\text{sum of taken}] = 1 \text{ if it is possible}$, which is $O(n ^ 4)$. I can't see any trivial way to reduce the state.
•  » » » 5 months ago, # ^ |   0 what do you mean by count of taken?
•  » » » » 5 months ago, # ^ |   0 He meant amount of numbers used, cuz it should be always fixed
•  » » » 5 months ago, # ^ | ← Rev. 2 →   +5 If it's a boolean knapsack it can be optimized using bitsets I guess, so solution might become N^4 / 64
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   +8 Oh yeah, $dp[\text{current}][\text{count}][\text{sum}]$ will update $dp[\text{current}][\text{count + 1}][\text{sum + current}]$, so it can be performed in blocks of 64 elements using an $OR$ on the bitset. If you consider the extra constant factor of $\frac{1}{2}$ from sum, this will take $\frac{N^4}{128}$ or around $5 \times 10^8$ operations, which is sketchy but possible for 2 seconds I guess. However its obviously not the intended, and based on the editorial I think it was just set to $n = 500$ to allow less optimized solutions to pass.
•  » » » » » 5 months ago, # ^ |   0 Yeah :p
 » 5 months ago, # |   -10 A great Contest！ Although I spent lots of time on problem D&G so that I couldn't finish this. :(
•  » » 5 months ago, # ^ |   +1 I refuse to believe that this is your first account. Also wtf is this ??
 » 5 months ago, # |   0 Did anyone used bruteforce approach with right angle property in problem 2?
 » 5 months ago, # |   0 Who else ignored the fact that the coordinates for B were for rectangles instead of squares
•  » » 5 months ago, # ^ |   0 Every square is a rectangle!
•  » » » 5 months ago, # ^ |   0 Every rectangle is not a square!
•  » » » » 5 months ago, # ^ |   0 So if your solutions is for squares instead of rectangles , it should still work ryt?
•  » » » » » 5 months ago, # ^ |   0 No. It only works for all squares, not all rectangles are squares
•  » » » » » » 5 months ago, # ^ |   0 Maybe I didnot get what you were trying to say! just ignore my messages in that case :D
•  » » » » » 5 months ago, # ^ |   0 not all the cases allow him to make square
 » 5 months ago, # |   +5 Despair is when you fail to fit a solution in time-limit, only to realize post-contest that the bottleneck is '64-bit int'.Only if the time-limit were 3 seconds :(
•  » » 5 months ago, # ^ |   0 Yeah TL was super tight, my first submission with 64 bit integers ran in 1980ms, after replacing it with 32 bit ints it ran in around 1s.
 » 5 months ago, # |   -10 MikeMirzayanov Can you please provide the whole second testcase for problem B , can't seem to find my mistake
•  » » 5 months ago, # ^ |   0 Line 91 should be poin1 = make_pair(first_x,0); instead of poin1 = make_pair(0,first_x);Currently can't submit this, but you can check after the hacking phase gets over.Let me know if the error persists!
 » 5 months ago, # |   +29 The ranklist is cyclically shifting started from Geothermal and it will end to him LOL.
•  » » 5 months ago, # ^ |   0 Mission successful !! :)
 » 5 months ago, # |   +3 Why is everyone's A failing on the top of the standings?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +3 Invalid inputs are passing as hacks. I think the validator doesn't have a check for 1 different element.I submitted 1 3 1 1 1 and got successful hack.
•  » » » 5 months ago, # ^ |   +4 Oh crap , Supermagzzz ... Can you look into this
•  » » » 5 months ago, # ^ |   +1 1 3 1 1 1 Is good, but it can be better! :v 1 4 1 1 2 2
 » 5 months ago, # | ← Rev. 2 →   +14 EDIT: VALIDATOR DOESN'T CHECK THE 1 DIFFERENT ELEMENT PROPERTYWhats the hack case on A?Also how is this idea incorrect:The different element is either the smallest or the largest element of the array, so we can just check one of them.
 » 5 months ago, # |   +5 HackForces
 » 5 months ago, # |   +45 Div3-A, there's probably an error in the input checker. It is known that in this array, all the numbers except one are the same (for example, in the array [4,11,4,4] all numbers except one are equal to 4). But I have successfully hacked my own submissions(#112521962) in the following case.131 2 3
•  » » 5 months ago, # ^ |   +24 Yup, hacked someone with this case as well. Seems like validator doesn't actually check that property. Should be fixed fairly soon. 1 3 1 1 1 
 » 5 months ago, # |   +3 wtf. Why everyone is getting hacked?
 » 5 months ago, # | ← Rev. 2 →   +5 I think setters should again write a correct validator in problem A, invalid test cases are showing hacked in A.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 [deleted]
 » 5 months ago, # |   0 MikeMirzayanov Please fix all hacks for A, Thanks!
 » 5 months ago, # |   0 Uh, are you guys going to fix the invalid test case for A. It's allowing many people to be hacked and lose easy rating.
•  » » 5 months ago, # ^ |   0 I mean you just hack 113 solutions with it!
•  » » 5 months ago, # ^ |   +3 we are not going to lose rating lmao. I don't know if you are delusioned or you are joking it's most probably the latter.
 » 5 months ago, # |   +5 It seems that a wrong validator was written for Problem A.
 » 5 months ago, # |   +25 Indeed
 » 5 months ago, # | ← Rev. 2 →   +2 People are using invalid hacks on problem A by using 1 3 1 2 3 as input, can anyone please check it
 » 5 months ago, # | ← Rev. 2 →   -8 Please tell me why my B is wrong! 112540024  Thanks lazy_and_slow Thanks a lot for taking the trouble. Appreciated!
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 you have made a mistake in your first_y and second_y points in the code. I corrected it (commented on the line with mistake). 112571015
 » 5 months ago, # |   -16 wrong answer Not a rectangle (1) (test case 35) Could someone please provide that
 » 5 months ago, # |   0 Everyone's Problem A XDDDD
 » 5 months ago, # |   +3 This is most probably an unecessary comment but please do make sure to not allow incorrect (most probably TLEd out solutions for A to get accepted) upon re-judging
 » 5 months ago, # |   0 Could you help me with problem C please? I uploaded a solution but it failed. In one of the tests it should print 100001101100001 or something like this, but prints -1 instead.
•  » » 5 months ago, # ^ |   0 your solution fails on this test 1 4 4 ??00???? after the first iteration, your string will be0?00???0, which is incorrect, since these new zeros must be next to the already existing zeros. to fix this, you can first process the pairs about which it is already obvious which character should be set (pairs 1?, ?1, 0?, ?0), and then the remaining ones (which consist only of ?) 112623883
•  » » » 5 months ago, # ^ |   0 Thanks!
 » 5 months ago, # |   +20 The input validator of Problem G is also wrongI use this testcase and successful hack 1 10000001 
 » 5 months ago, # |   +10 This is ridiculous, not only problem A, but problem G is also broken... why does it allow inputs bigger than 10^7?
 » 5 months ago, # |   +1 Can anyone also check G validator? I got hacked with RE and it seems kinda strange for me...
 » 5 months ago, # | ← Rev. 3 →   0 Can anyone help me why my code is failing at Test 2 (Case-60) for problem D. Link-SolutionUpd: Found the mistake and got AC.
 » 5 months ago, # |   +1 I got hacked in G for a solution which I believe can't be hacked , hey CF correct your test case validators
 » 5 months ago, # | ← Rev. 2 →   +10 Hackerforces :(
•  » » 5 months ago, # ^ |   +2 Today people like me (Newbie) tried to hack GEOTHERMAL(I.G.M) solutons :):)
 » 5 months ago, # |   +9 Everyone Problem A XD
 » 5 months ago, # | ← Rev. 2 →   +3 Could anyone tell me why my submission for D 112517759 was incorrect (hacked)? I'd appreciate it, thanks! UPD: Thanks to you_dont_know_me for clarifying! Really appreciate it.
•  » » 5 months ago, # ^ |   +1 overflow b_i <= 10^9 & n <= 10 ^ 5 worst case : Sum <= 10^14
 » 5 months ago, # |   +29
 » 5 months ago, # | ← Rev. 2 →   0 Lol got to about rank 298 before A and G hacks were fixed. GG.
 » 5 months ago, # |   0 Can the validator for G please be checked? Thanks
 » 5 months ago, # | ← Rev. 2 →   +39 Sorry to say but the level of Div3 is getting down day by day. We all saw what happened today. Moreover, problem G is just copied. Original G problem . If you just copied, give some credit to the owner at least. We really enjoyed Div3's that were organized by vovuh. I don't have any problem with the recent authors and I appreciate their hard work, but please maintain the level of Div3, as many of us enjoy giving Div3 more than much other contest.
 » 5 months ago, # |   -8 I have been debugging my G since it got hacked.
•  » » 5 months ago, # ^ |   +25
•  » » » 5 months ago, # ^ |   +2 Keep posting good memes like this :)
•  » » » » 5 months ago, # ^ |   +4 bro, I hope you don't mind :)
•  » » » » » 5 months ago, # ^ |   +10 I didn't. That was really a good one. Keep posting good memes (it's hard to find them).
 » 5 months ago, # | ← Rev. 3 →   +6 Meanwhile Problem A after today's Div3 Edit — Those who don't know, most of the solutions were hacked by invalid Test Cases. It's fixed now. Thanks Mike ;)
 » 5 months ago, # |   0 Could anyone tell me why my submission for D 112574846 is showing incorrect output for test case 1 only??
 » 5 months ago, # |   -20 So much hack unhack , that much high numbers of submissions on problems , Bug in the Problem A & Codeforces | #WeWantUnrated
•  » » 5 months ago, # ^ |   +2 Why? Because you couldn't perform well enough?
 » 5 months ago, # |   +22 Hello! Because of mistakes in some validators I reverted all hacks and rejudged solutions. Sorry for the issue. Fortunately, this did not affect the round itself in any way. Not a single participant was hurt!
•  » » 5 months ago, # ^ |   +15 Will these real successful hacks which is ignored now be run again?
•  » » 5 months ago, # ^ |   +43 After the rejudge of problem G, my solution got TLE on test 5. On submitting the same code in practice, it got AC, and test 5 ran in 1325 ms. Is there any reason for this inconsistency, because it may have affected other participants too.
•  » » » 5 months ago, # ^ |   -6 :")
•  » » » 5 months ago, # ^ |   +1 Same happens to me.
•  » » » 5 months ago, # ^ |   +5 Same for me my solution passed in 1650 ms in the contest but after rejudge it TLE on the 1st test. On submitting the same code it got accepted now.TLE : 112502445, Accepted : 112582502
•  » » » » 5 months ago, # ^ |   0 The same happened with my code. It's giving tle on 3rd test case. when I submitted it again it got ac.
•  » » 5 months ago, # ^ |   +9 My effort of two hours is gone. T_T
•  » » » 5 months ago, # ^ |   0 Sorry for it. It would be not easy to rejudge hacks properly. But you can uphack all solutions which weren't hacked yet )
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   -13 Sorry for bothering you Mike sir.But my query regarding a plagiarism check (which I had posted about an hour ago) is still unanswered even though the ratings are out.It would be great if the team is considering checking the claim and my message once again.Thanks
 » 5 months ago, # |   -8 Is this contest unrated? I haven't received any rating yet
•  » » 5 months ago, # ^ |   0 Opening hacking is not over yet.
 » 5 months ago, # |   0 my solution got hacked , now will it effect my ratings?
•  » » 5 months ago, # ^ |   0 how to know it got hacked ?
•  » » » 5 months ago, # ^ |   0 you can check your submissions
 » 5 months ago, # |   +4 Though F is easier than G, for the first 1 1/2 hours during the contest there are more accepted submissions for G than F. Why is that?
•  » » 5 months ago, # ^ |   +4 The relative length of problem Statement of F vs G probably. Plus I think G wasn't that hard compared to F. The time limit was rather tooooo tight for G.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +2 G is fairly standard if you know the property about sum of divisors (or can obtain it from the property about number of divisors), whereas F actually takes a few minutes to think about the specifics. Also 5-6 top participants solved G early in the round, meaning it had more solves than C or D. So several other participants (including me) just switched to trying G after solving B thinking it was significantly easier based on the solve count, which led to a positive feedback loop.
 » 5 months ago, # | ← Rev. 4 →   +7 My solution for problem g is giving tle .however when i submitted it again it is getting accepted. How could it be possible?
 » 5 months ago, # |   +16 Many of problem G accepted solutions got TLE in pretest after rejudge. G needs to rejudge again with proper balance. Thanks.
 » 5 months ago, # |   0 During the contest, my solution for D was Accepted. Now it is a TLE. I am tired of changing my Java solutions to use fast I/O. Are these I/O problems or algorithm problems?Yes, in this case, seeing 1860 ms (with 2 sec limit), I probably should have changed it, especially because I had time to do it. For instance, my G passed only after I changed the way I printed the output. Nothing else. And then I saw D's time and thought "Screw that, I am not changing it".Well, it sounds like it is a part of the competition. And yes, I go through this every other contest. For instance, it is a common knowledge that you want to use Long[] instead of Integer[] in Java when they need to be sorted. Why?I think that having an efficient I/O should never be a goal for these contests. If it is, please remove "slow" languages, so we (the users of said languages) can either skip the contest or try to compete on equal grounds by coding in languages we are not familiar with.
•  » » 5 months ago, # ^ |   +3 Each participant has the right to choose the language that he likes. Together with all its pros and cons. Yes, Java runs a little slower on average, but it has better static analysis in the IDE. It is quite typical for IT tasks that the tool is chosen for the task. And yes, I'm sure it's not a bad thing that sometimes you encounter purely programming difficulties. Understanding that not all ways to read or write data are the same is helpful. In particular, it is important to understand the basics of buffering. Specifically, in your case, knowing the standard library of the language in which you write is also useful. You are using Arrays.sort, but not reading the documentation. Read it finally. This algorithm offers O(n log(n)) performance on many data sets that cause other quicksorts to degrade to quadratic performance
•  » » » 5 months ago, # ^ |   0 Thanks for the response. All valid points, sorry for venting out.
 » 5 months ago, # |   0 New here, how long does it take for the ratings to be updated ?
•  » » 5 months ago, # ^ |   0 for div3 and educational rounds around 12-14 hours
•  » » » 5 months ago, # ^ |   +1 But, I think it should be updated before the new contest Div 2 today.
 » 5 months ago, # |   +5 question g needs to be rejudged. Many of the solutions which are getting tle getting accepted on resubmitting. Even on 1300 ms.
•  » » 5 months ago, # ^ |   +1 Yes , the code I submitted yesterday got AC . Today it showed TLE on testcase 5. A Few moments later TLE on testcase 3. Submitted the same code just now in Practice — AC. Admins, please look into this.
 » 5 months ago, # |   +7 My submission for Problem D passed all the pretests yesterday even though I had used int instead of long long. Can finally say that the pretests should have been stronger ;) int long long
•  » » 5 months ago, # ^ | ← Rev. 2 →   -9 It was obvious in the question that you had to use long long, if n==2e5 and you have permutation of that length, then the sum would more than 2e10 which can't be scored in int, which is basically what you had in the B array
•  » » » 5 months ago, # ^ |   +8 That's not the point. The pretest should obviously have some counter cases for int-solutions.
•  » » » 5 months ago, # ^ |   +2 I agree that it was an avoidable mistake on my part; but the thing is that if I had got an overflow error while the contest was still running, I would have been able to fix it in a moment and wouldn't have got the WA verdict that I got around 12 hours later. Had the pretests been a little stronger, I wouldn't have missed out on a point because of something as silly as the mistake that I made...
 » 5 months ago, # |   0 If we could not solve a problem and got 4 wrong submissions than penalty of 40 minutes extra will be added?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 NO, You will get penalty only after you get AC
 » 5 months ago, # | ← Rev. 2 →   0 I am a newbie . When will the rating be updated ?. This is my first contest. Anyone pls reply
•  » » 5 months ago, # ^ |   +1 it should be updated very soon. you can see your rating changes by cf predictor extension
•  » » » 5 months ago, # ^ |   0 Thanks
•  » » » 5 months ago, # ^ |   0 but it does not work it just show Good luck & high rating!
 » 5 months ago, # |   +1 I refreshed the official standings table (after the open hacking phase finished), and the rankings are still changing. What is the reason behind this?
•  » » 5 months ago, # ^ | ← Rev. 3 →   +1 Sorry MikeMirzayanov But I don't have any super complex template/snippet in my codes. I prefer writting simple and clean code; which is why there is always a chance that my code may match similar to anyone else's code.I didn't wanted to ping you 2 times but please kindly look into other factors while checking for plagiarism. Like if the 2 people had the same code for others questions or not. Suppose my code for A and C are not at all similar to that of the user mentioned above. So how did I solve them if I had to ask for solution for B?
•  » » » 5 months ago, # ^ |   0 Doesn't seems like my query will be looked into :(
•  » » » » 5 months ago, # ^ |   0 MikeMirzayanov and Stepavly It has been 4 days since I posted the comment and still no response or update whether the team has considered reviewing the claim or not.I again insist that I have no direct connection with the above mentioned user. My solutions are very simple and easy to understand which might be a reason that my solution might have coincided with someone else's code.
 » 5 months ago, # |   0 I participate for the first time in contest. So can anyone help me in whether my "Unrated" status changes with a rating .
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 After giving the contest your ratings will be updated 1 day after the contest gets over. NOTE : May take more or less time depending on factors like : no. of participants, hacks, buggy hacks(like that happened in this one) ...etc.
 » 5 months ago, # |   0 hey guys, java code for problem D is giving tle in test case 17 although it's linear time complexity, can anybody explain why??
•  » » 5 months ago, # ^ |   0 Arrays.sort() internally uses quick sort as a sorting alogrithm thus in worst cases if pivots are not choosen optimally complexity will be O(n^2), so try to use Collections.sort() instead, which uses merge sort.
•  » » » 5 months ago, # ^ |   0 thanks bro!!
•  » » 5 months ago, # ^ |   0 Same thing happened with me too. I think Arrays.sort uses dual-pivot quicksort algorithm for primitive arrays which is not stable. Sometimes its time complexity degrades to O(n^2) for particular data sets.
 » 5 months ago, # |   0 Top round!!!
•  » » 5 months ago, # ^ |   +1 +1After receiving the message, I actually went to see, if my code was similar to floki's code Or not. I agree to the fact that the codes are really very very similar. But, what else would I code? That is such a straight forward approach, and a straight forward implementation. Plus, as far as using ideone Or something similar is concerned,I didn't use it. I would request MikeMirzayanov and Stepavly to please look into thisThanks
 » 5 months ago, # |   0 For Codeforces round 713 div 3, I got a message saying that my submission for problem B coincides with another person. The reason behind this is that I solved all my problems on CodeChef IDE but for problem B it was throwing some problems. don't know the reason why. So I tried running my code on Ideone in the default setting and someone copied my code and I was not aware of that. You can check my code for Problem A it is unique. The approach is unique the variables are unique. So it was only for Problem B that this mistake happened.sorry for my mistake. I'll make sure it never happens again.
 » 5 months ago, # | ← Rev. 2 →   0 Is there anyone who got in Problem F's second test WA because 8891st number differs and then could manage to find the issue and get AC ?
•  » » 5 months ago, # ^ |   +3 yes you can see my code actually u might be missing the case where you dont have to earn at a particular day and the balance you have is sufficient to move to next position
•  » » » 5 months ago, # ^ |   0 thanks a lot, I didnt think about that
 » 5 months ago, # | ← Rev. 2 →   0 [Deleted]
 » 5 months ago, # | ← Rev. 2 →   0 For problem G: My submission using long long: https://codeforces.com/contest/1512/submission/112652041My submission using int: https://codeforces.com/contest/1512/submission/112651472Using int is taking noticeably less time than using long long.Can anyone explain, Why long long is slower than int?
 » 5 months ago, # |   0 I don't know why I got TLE for nlog(n) submission in D.
 » 5 months ago, # | ← Rev. 5 →   +1 Please consider to rejudge my solution of problem GLast 713 div3 Same solution one is ac and one is tleTLE Solution : https://codeforces.com/contest/1512/submission/112528244Accepted Solution : https://codeforces.com/contest/1512/submission/112621917When contest is running my problem got ac verdict all the 9 test case And i have a screen shot alsoAnd when contest and rejudge theAll solution g that time my solution got tle In 7th test case, . But contest timeShow all the 9 test case acAnd same solution i submit nowIt's show ac verdictPlease rejudge my solution MikeMirzayanov
•  » » 5 months ago, # ^ |   0 Almost the same thing happened to me also.TLE Solution — https://codeforces.com/contest/1512/submission/112541255 (Which was ac in the running contest)After contest AC solution — https://codeforces.com/contest/1512/submission/112611320Both codes are exactly the same.
 » 5 months ago, # |   +1 This Div.3 is too easy...Hope a harder contest!
»
3 months ago, # |
0

# include<bits/stdc++.h>

using namespace std; // #define int long long

const int mod=1000000007; const int MAX=100005;

int mul(int a, int b){ return (a*b)%mod; }

// int mp1[MAX*4];

void solve(){ int a, b; cin>>a>>b;

string str;
cin>>str;
int cnt0=0;
int cnt1=0;
int cntq=0;
int n=str.size();
if(a%2!=0 && b%2!=0) {cout<<-1<<endl; return;}
// if(a==0 || b==0) {cout<<str<<endl; return;}
for(int i=0;i<str.size();i++){
if(str[i]=='0')cnt0++;
else if(str[i]=='1') cnt1++;
else cntq++;
}
if(a<cnt0  || b<cnt1) {cout<<-1<<endl; return;}
// cout<<"here";
for(int i=0;i<str.size();i++){
if(     str[i]!=str[n-i-1]   && (str[i]!='?' && str[n-i-1]!='?')   ) {cout<<-1<<endl; return;}
else if(     str[i]!=str[n-i-1]   && (str[i]=='?' || str[n-i-1]=='?')   ) {

if(str[i]!='?') {str[n-i-1]=str[i];
if(str[i]=='0') cnt0++;
else cnt1++;}
else if(str[n-i-1]!='?') {str[i]=str[n-i-1];
if(str[n-i-1]=='0') cnt0++;
else cnt1++;}

}
if((str[i]=='?' && str[n-i-1]=='?') ){
//  cout<<"here";
if(min(a-cnt0,b-cnt1)==b-cnt1  && cnt0<a)  {str[i]='0'; str[n-i-1]='0'; if(i==(n-i-1)) cnt0++; else cnt0+=2;}
else if(min(a-cnt0,b-cnt1)==a-cnt0  && cnt1<b)  {str[i]='1'; str[n-i-1]='1';  if(i==(n-i-1)) cnt1++; else cnt1+=2;}

}
}
if(cnt0!=a || cnt1!=b){cout<<-1<<endl; return;}

for(int i=0;i<str.size();i++){ if(str[i]!=str[n-i-1])  {cout<<-1<<endl; return;}}
cout<<str<<endl; return;

}

int main(){

int t; cin>>t;
while(t--){
solve();

}

return 0;

}

can you help me which point am i missing.for problem c