### BucketPotato's blog

By BucketPotato, 2 months ago,

Hi Codeforces,

We're excited to invite you to Codeforces Round #809 (Div. 2), which will take place at Jul/18/2022 17:35 (Moscow time). All problems were created and prepared by lunchbox, lce4113, and me. It will be rated for all participants with ratings lower than 2100.

Thanks to the people that made this round possible:

You will be given 2 hours to solve 5 problems, one of which will be divided into 2 subtasks. The scoring distribution will be announced later.

UPD: The scoring distribution will be $500 - 1000 - 1250 - (1000 + 1250) - 2250$.

UPD2: The editorial has been posted at https://codeforces.com/blog/entry/105008.

UPD3: Winners

#### Everyone

• +472

 » 2 months ago, # |   +119
•  » » 2 months ago, # ^ |   -21 As a contestant ...
•  » » » 2 months ago, # ^ |   -22 As a man...
•  » » » » 2 months ago, # ^ |   -30 As a person...
•  » » » » » 2 months ago, # ^ |   -32 As a coder
•  » » » » » » 2 months ago, # ^ |   -19 As a developer
•  » » » » » » » 2 months ago, # ^ |   -26 As a shit
•  » » » » » » » » 2 months ago, # ^ |   -30 As a human...
•  » » » » » » » » » 2 months ago, # ^ |   -17 As a as
•  » » » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   -16 As
•  » » » » » » » » » 2 months ago, # ^ |   -18 a
•  » » » » » » » » » 2 months ago, # ^ |   +23
•  » » 2 months ago, # ^ |   +27 As a loser
 » 2 months ago, # |   +70 As a massive fan of hugs, cosy blobs, and the problem-setting team, I am looking forward to the contest!
 » 2 months ago, # |   +254 As a tester, tester is just a premutation of setter
•  » » 2 months ago, # ^ |   +16 Damn
•  » » 2 months ago, # ^ |   -12 As a contestant, contest is just a prefix of contestant
•  » » 2 months ago, # ^ |   0 Omg, op logic
 » 2 months ago, # |   +122 As a useless problemsetter, I hope you enjoy this round!
•  » » 2 months ago, # ^ |   -34 Excellent thank you! I also hope that you come up with a great and good problem. Looking forward to the competition.
•  » » 2 months ago, # ^ |   -34 Thanks to the people that made this round possible. I think they will not disappoint us, they came up with great problems, tests and so on. :)
•  » » 2 months ago, # ^ |   -27 By the way, I really like codeforces!
•  » » 2 months ago, # ^ |   +22 As a contestant, waiting for the score distribution...
 » 2 months ago, # |   +73 As an author, BucketPotato orz.
•  » » 2 months ago, # ^ | ← Rev. 4 →   -35 BucketPotato orz.
 » 2 months ago, # |   +57 BucketPotato round orz
 » 2 months ago, # |   +83 BucketPotato orz. As a tester, I can confirm that the problems are very interesting and would recommend everyone to participate in the contest. AlsoCan I have your upvotes please?
•  » » 2 months ago, # ^ |   +19 So you want to say I won't loose cm first round after I reached it? :thinking:
•  » » » 2 months ago, # ^ |   +16 Congratulations for CM! Yeah, hopefully you will not lose CM just after you reached it.
•  » » » » 2 months ago, # ^ |   +17 Thanks, then I'm like 2 times calmer to participate xdd
 » 2 months ago, # |   +53 BucketPotato hard carry orz
 » 2 months ago, # |   +59 As a tester this round is extraordinaryTake it or BucketPotato will come to your house and enact his revenge
 » 2 months ago, # |   +7 As a CFer, BucketPotato orz
 » 2 months ago, # |   0 Seeing sus as a tester makes me feel really excited about this round!!
 » 2 months ago, # |   +3 Through the last two competitions, I have reached “pupil”. I hope my rating can reach 1300 in this competition!
 » 2 months ago, # |   0 thankyou to all the testers and problem setters and good luck for everyone
 » 2 months ago, # |   0 Can anyone tell me how to become a tester for cf contest? What are the criteria for it ?
•  » » 2 months ago, # ^ |   +9 How to become a CodeForces tester 101: Step 1. Become friends with some setters Step 2. Profit
•  » » » 2 months ago, # ^ |   0 How to become friend with some setters?
•  » » » » 2 months ago, # ^ |   +42 Seduction works
•  » » » » » 2 months ago, # ^ |   +21 Unspoken rizz
•  » » » » » 2 months ago, # ^ | ← Rev. 2 →   +10 I don't know how to seduce :( probably just gonna make myself an e-girl
 » 2 months ago, # |   0 I wish you all good luck! :)
 » 2 months ago, # |   0 I'm waiting impatiently and wish everyone good luck to score more points
•  » » 2 months ago, # ^ |   0 I wish you all the best too! :)
 » 2 months ago, # |   0 As a contestant I hope I can become Specialist
•  » » 2 months ago, # ^ |   0 as a contestant I hope I can become expert :D
•  » » » 2 months ago, # ^ |   0 Nice we are far 31 exactly. Good luck today!
•  » » » » 2 months ago, # ^ |   0 good luck <3
 » 2 months ago, # |   0 Get it!
 » 2 months ago, # |   +39 BucketPotato orz
 » 2 months ago, # |   +1 I hope this Div2 gets easier!
 » 2 months ago, # |   +4 Good luck everyone. I hope this round is easier than the last round.
 » 2 months ago, # |   +110
•  » » 2 months ago, # ^ |   -10 good joke! hahahahahaha!
•  » » 2 months ago, # ^ |   0 Ahahahahhahahahha. U made my day, get like XD
•  » » » 2 months ago, # ^ |   0 Ahahahahahahahha
•  » » 2 months ago, # ^ |   0 hhhhhh
 » 2 months ago, # |   -11 Best of luck everyone! Lets's give our best in this contest.
•  » » 2 months ago, # ^ |   0 Of course, I also wish everyone good luck and I really hope that the tasks will be easier than the previous ones! :)
•  » » 2 months ago, # ^ |   +2 Ok but please stop cheating
 » 2 months ago, # |   0 the name potato head would be better!
 » 2 months ago, # |   +26 :pkinghi: BucketPotato Orz. Master of hugs.
 » 2 months ago, # |   0 You will be given 2 hours to solve 5 problems, one of which will be divided into 2 subtasks Can someone explain what divided into 2 subtasks means.
•  » » 2 months ago, # ^ |   +9 I think we could have same two problems with different constraints as b1 b2 for example
•  » » 2 months ago, # ^ |   +2 It doesn't always mean different constraints. That means we will have 6 problems, but two of them will be very similar.
 » 2 months ago, # |   0 as a participant I am participating
 » 2 months ago, # |   -6 Hope everyone enjoy the round.
 » 2 months ago, # |   0 I hope all participants will write this round good! I also wish good luck everyone!
 » 2 months ago, # |   -14 I hope this is a Codeforces round and not a Mathforces one.
 » 2 months ago, # |   0 Nothing is impossible.
 » 2 months ago, # |   0 div 4 is not to hard, div 3 is hard, div 2 is very hard, div 1 is hardest of them all.
 » 2 months ago, # |   0 Hi, Can I have a peer group link??? It will help me to discuss different approaches to solve a problem...
 » 2 months ago, # |   +5 As a Rating-rapid-decline-er, I hope I can enjoy this round.
•  » » 2 months ago, # ^ |   0 As a Master, I hope today is not still a Candy Date.
•  » » » 2 months ago, # ^ |   +5 Candydate Master orz
 » 2 months ago, # |   0 Hope there will be more contests in the near future <3
 » 2 months ago, # |   +4 I think codeforces have best userInterface amongs all comptetive coding platform.
 » 2 months ago, # |   +17 Scoring distribution when
 » 2 months ago, # |   0 It's time for Pupil :)
•  » » 2 months ago, # ^ |   0 Good luck
 » 2 months ago, # |   +3 How do I become a tester?
 » 2 months ago, # |   0 for proposing problems that didn't make it to the final version of the round. XD XD.
 » 2 months ago, # |   0 Good luck everyone :)
 » 2 months ago, # |   0 No score distribution yet!
 » 2 months ago, # |   0 hope its not like previous D2 round
 » 2 months ago, # |   0 I'm looking forward to this contest, because it will decide my ranking tomorrow I'll try to go green
 » 2 months ago, # |   0 Hoping for good question and to perform better
 » 2 months ago, # | ← Rev. 2 →   -9 I want to go to green
 » 2 months ago, # |   0 First contest has a subtasks problem!
 » 2 months ago, # |   +2 hoping not to become pupil again
 » 2 months ago, # |   0 good luck to me , I'm participating after so long
 » 2 months ago, # |   +1 Looking forward to this round! After this round, I should become green.
 » 2 months ago, # |   -9 too complicated for div 2
 » 2 months ago, # |   0 I like B.
 » 2 months ago, # |   0 one of the easy div 2's imo
 » 2 months ago, # |   0 Advanced div.2 ! I can't solve anything.
 » 2 months ago, # |   +9 What's the backstory of naming D1 as Chopping Carrots?
•  » » 2 months ago, # ^ |   +65 Originally, the statement looked something like this (this is a very condensed version of it): You are preparing carrots to cook. The carrot can be modeled as a non-decreasing array, and your chopping skills are represented by an integer k. The roughness of an array p is max(a / p) — min(a / p), find the minimum roughness of the carrot you can achieve. The flavor text was ultimately taken out since testers found it made the statement more confusing.
 » 2 months ago, # |   0 WA on test case 2 it's all i can see
 » 2 months ago, # | ← Rev. 3 →   +1 B is way harder than C to me.
•  » » 2 months ago, # ^ |   0 B is greedy
•  » » » 2 months ago, # ^ |   +3 How? I see only dp solution.
•  » » » » 2 months ago, # ^ |   0 How can you please explain your approach?
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +7 difference between index of 2 same colors should be odd so that we can put them in same tower
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   0 We need to have odd distances between indexes of each frequency to build
•  » » » » » 2 months ago, # ^ |   0 Yes, wiered named friend, but how is this greedy?The dp is more or less simple:  vvi dp(2, vi(n+2)); vi ans(n); for(int i=n-1; i>=0; i--) { dp[i%2][c[i]]=dp[1-i%2][c[i]]+1; ans[c[i]]=max(ans[c[i]], dp[i%2][c[i]]); } 
•  » » » » » » 2 months ago, # ^ |   +5 It's dp because you solved it using dp and its greedy because I solved it using greedy.
 » 2 months ago, # |   0
 » 2 months ago, # |   0 How to solve D1?
 » 2 months ago, # |   0 How to do problem B?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 My solution goes something like this: The observation on the grid shows that we can stack two blocks of the same color on top of each other if the the number of blocks in between them is even. Using this observation, we can maintain a count of such consecutive blocks and update our counter each time we find such blocks. Finally, for each type of block just print their counters. Also if some numbers have 0 counter, but they do appear at least once, then their final value should be 1. Soln: My submission Complexity: O(n)
 » 2 months ago, # |   0 How to solve D1?(Just some hint)
•  » » 2 months ago, # ^ |   +1 Fix the maximum (or minimum) element.
•  » » » 2 months ago, # ^ |   0 https://codeforces.com/contest/1706/submission/164793681 I did that! But WA on pretest 3 :(((
•  » » » » 2 months ago, # ^ |   0 The minimum element is not necessarily of the form $\frac{a[0]}{j}$...
•  » » » » » 2 months ago, # ^ |   0 Can you please clarify why every value of 0 to a[0] is possible as min value ??
•  » » » » 2 months ago, # ^ |   +5 Take a look at Ticket 15890 from CF Stress for a counter example.
•  » » » 2 months ago, # ^ |   0 I got TLE by doing that but may be inefficiently. I stored all possible values for a number in a 2-D array and iterated 1 to 3000 fixing it as maximum and got maximum possible number of each element less than fixed maximum using binary search!How did you do that?
 » 2 months ago, # |   0 Is the main idea for $E$ to maintain a DSU and for each 'root' node mantain the set of intervals covered and then merge them appropriately?
•  » » 2 months ago, # ^ |   +57 This wasn't my approach. I used DSU with small-to-large merging to find the earliest time at which vertex v is connected to vertex v+1, for all v. Then, queries can be answered by storing these times on a segtree and storing the maximum values within the range [L, R-1].
•  » » » 2 months ago, # ^ |   0 This is exactly what I did, only difference is I used when v is connected to v-1.
•  » » 2 months ago, # ^ |   +3 That was what I thought of during contest (164782058), but realized only after that a much simpler solution exists.
 » 2 months ago, # | ← Rev. 2 →   0 good luck everyone!
 » 2 months ago, # |   0 Hi, I have a hard time debugging my code. For example, today's Div2D1, I felt I had made it but then I had WA on pretest 3 and I couldn't debug fast. Here is my submission. https://codeforces.com/contest/1706/submission/164793681 Any tips on fast debugging? Thanks!
•  » » 2 months ago, # ^ |   +5 Take a look at Ticket 15890 from CF Stress for a counter example.
 » 2 months ago, # |   0 In problem C when n=6 there will be 3 possibilities right (2,4) or (2,5) or (3,5)?
•  » » 2 months ago, # ^ |   0 if n = odd, it becomes trivial. If n = even: For every tower we want to make cool we can pick it up from 2 array: 1) 2,4,6,8,... 2) 3,5,7,9,...Suppose you pick i from 1) then you need rest (n/2-1-i) from 2). Just iterate over i and take the min.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 I saw many guys use dp to solve problem C, i don't know why. The problem description says "maximize the number of cool buildings."I think we have 1 option for n % 2 == 1, and 2 options for n % 2 == 0.n == 6 is a special case and has 3 options.So what I missed?
•  » » » » 2 months ago, # ^ |   0 You can "skip" a building in case of n % 2 == 0Consider the case of10 9 7 7 7 7 9 10"odd" and "even" options use 2 + 1 + 3 = 6 floors10 (9->11) 7 (7->8) 7 (7->10) 9 1010 9 (7->10) 7 (7->8) 7 (9->11) 10while optimal solution10 (9->11) 7 (7->8) 7 7 (9->11) 10uses only 2 + 1 + 2 = 5 floors.
•  » » » » » 2 months ago, # ^ | ← Rev. 3 →   0 If n is even: For some building x, choose all odd indexed in the left to x, and all even indexed buildings to the right of x. So there is a gap of two non-cool buildings near x.
•  » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 10 9 7 7 7 7 9 100 1 0 1 0 1 0 00 0 1 0 1 0 1 0there are only two options, right? I need an example which has more than 2 options except n == 6, cause (6 — 2)/2 = 6-4
•  » » » » » » » 2 months ago, # ^ | ← Rev. 2 →   0 3 options:01010100 (6 floors)00101010 (6 floors)01010010 (5 floors)
•  » » » » » » » 2 months ago, # ^ |   0 Consider n = 10. Suppose you want to make buildings h_i cool. Max cool towers are 4.2,4,6,8 or 3,5,7,9 or 2,4,7,9 or 2,5,7,9 etc. You get it right?
 » 2 months ago, # |   +35 Easier Div2? I like B, it's good D2B I saw some tasks similar to C somewhere Why so tight ML for D2? I have a painful work making the memory of my solution < 64MB
•  » » 2 months ago, # ^ |   +10 Linear memory is intended I think. My submission with $3n$ integers on a BST (instead of heap) only used 6MB, so if anything I think it could have been 32MB
•  » » 2 months ago, # ^ | ← Rev. 2 →   +8 Agreed re: D2. The process of solving D2 was very unpleasant for me--I came up with/recognized the main observation in <2m, then took the vast majority of my time dealing with the memory optimization. In particular, because $\sum a_n$ was unbounded, my approach to optimizing the memory was dependent on the fact that the number of tests was small, as it leads to a time complexity of $O(n \sqrt{n}) + a_n)$ per test case. The problem is solvable in linear memory, but the process of optimizing to linear memory is not at all interesting, and the linear memory solution doesn't feel any more clever than the $n \sqrt{n}$ memory solution.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +49 Sorry for the trouble, there is a $n \sqrt n$ two-pointers memory solution in D2 that we wanted to cut off. We decided it would be fine since all of the correct $O(n)$ memory solutions (from testers, authors, and the coordinator, including in Python and Java) use less than 1/6 of that memory without any optimizations.As for the difficulty, there was originally a problem F, but testing suggested that up to E was hard enough.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   +14 My O(n) memory solution requires me to change std::vector to std::list, or free the memory of std::vector correctly (.clear() doesn't free the memory).It's a bit annoying. :(
•  » » » » 2 months ago, # ^ |   0 I also MLEed once due to clear().
•  » » » » 2 months ago, # ^ |   +18 Sorry to hear :(Our correct intended solutions take some more thinking, but have clean and easy implementations (no optimizations needed).So I guess the difficulty of this task was in, do you want to optimize your code or think of a cleaner solution?
•  » » » » » 2 months ago, # ^ | ← Rev. 4 →   +8 I believe the core idea of mine (the one changed to std::list 164802621) and the posted solution doesn't differ a lot. (to me, it's just some computation order)Are there any more clever solutions?I know knowing the programming language I used is also a part of CP, but just don't like it to be kinda the only point of a problem.btw, what do u mean by optimizing my solution?Anyway, other problems are not bad.Thanks for the contest!
•  » » » » » » 2 months ago, # ^ |   +13 The main idea is the same, but the way you go about it is different:Your solution uses a vector> to help determine cmx (using variable names from your code), and has to update the lists as you sweep through.The intended solution also finds all values of cmx, but uses the additional idea of prefix maxes on increasing functions to simplify the memory usage to a single int pf[100000 + 1].
•  » » » » 2 months ago, # ^ |   0 I had MLE with vectors too, but during contest I forgot about std::list and wrote custom (164757358)Changing vector to list in upsolving gives AC but sadly it is ~9x times slower than custom (164886835)
•  » » 2 months ago, # ^ |   +37 I was using a linear memory solution, but it was using vector> and the memory still blew up and used > 64 MB.Then I learned that .clear() does not necessarily reallocate to make the capacity back to 0. To "force clear" a vector, one can use vector().swap(x)
•  » » 2 months ago, # ^ |   0 I also agree about seeing C somewhere. I did try spending a little bit of time looking for it, but ended up not finding anything. I don't know how similar the problem I remember was, but it involved this idea of a[i] > a[i — 1] and a[i] > a[i + 1]
•  » » » 2 months ago, # ^ |   +1 https://codeforces.com/contest/1698/problem/B from round 803 is based on the same basic idea but asks a different question about it.
 » 2 months ago, # | ← Rev. 2 →   +5 wow, memory limits in D1 are divine. I submitted with O(n*3000) time, using 2d arrays, but it got ml. I changed algorithm for 2d arrays to 1d, and it passed. 5 incorrect attemps, rest in peace. But i had to gain only 4 points to reach CM164778279
»
2 months ago, # |
-28

# Is it Div.3?

•  » » 2 months ago, # ^ |   +14 No.
•  » » 2 months ago, # ^ | ← Rev. 2 →   +7 Did you know participating with alt account is forbidden in codeforces?!
 » 2 months ago, # | ← Rev. 2 →   0 I think my solution to D2 only uses O(N) memory, but still can't pass TC11.upd: std::vector is so hard (.shrink_to_fit() is stupid)
 » 2 months ago, # |   0 In the end, I solved three problems, which made me very happy. But how to solve D1?
•  » » 2 months ago, # ^ |   0 I think you fix either the max or minimum value and use brute force, but I didn't solve it, so I'm not too sure.
•  » » » 2 months ago, # ^ |   0 Yes, but instead of brute force use two pointers.
 » 2 months ago, # |   +1 Video Solution for Problem C.
•  » » 2 months ago, # ^ |   0 I did pretty much the same thing.Here is my submission:164775959Can anyone give me a fail-case.
•  » » » 2 months ago, # ^ |   0 long long ans
•  » » » 2 months ago, # ^ |   0 Testcase1 10 5 5 6 6 1 8 1 4 5 1 Your output5 Correct Output3
•  » » » » 2 months ago, # ^ |   0 I am such a retard. It 1 character mistake
•  » » » » 2 months ago, # ^ |   0 why it's 3 ?[0, 2, 1, 1, 8, 0, 8, 2, 0, 0, 0]we choose i which i % 2 == 1, then sum of them are 5
•  » » » » » 2 months ago, # ^ |   0 Using 1-indexing on the list [5, 5, 6, 6, 1, 8, 1, 4, 5, 1]The max number of good buildings you could have is 4$a_6$ and $a_9$ are already goodIf you add 2 floors to $a_2$ and 1 floor to $a_4$ those become good, so you only need 3 floors rather than 5
 » 2 months ago, # | ← Rev. 2 →   -10 I think the input constraints in problem D2 are really confusing. Why those $O(n\sqrt n\log n)$ solutions can get pretests passed but a $O(A\log n\log A)$ solution (my idea) can't get PP (only $\sum n$ is $10^5$ but $\sum A$ isn't) so I wasted a lot of time on this problem and I didn't solve problem E (or even carefully read the statement) which I found a solution just 5 minutes after the contest.Anyway, good contest & problems, hope the next round will be better.
•  » » 2 months ago, # ^ |   0 If $n=100000$,$\sqrt{n}\approx320$,$nlog^2n \approx 256$,but the constant of segment tree is so big that it is greater than $320$ after multipliying $256$.
 » 2 months ago, # | ← Rev. 3 →   0 The key observation is there should be single gap of length 2 in even numbers case and gap of length 2 can be chosen anywhere between gap of length 1's. I messed up with implementation and this question look familiar to leetcode ?
 » 2 months ago, # |   0 I used DSU to get when each point is first added to the connected graph, and then use segment tree to query the maximum values within the range [L+1, R].Why I couldn't get a accepted?my submisson
•  » » 2 months ago, # ^ |   0 that's not correct. Added to connected graph does not mean connected to previous node.
•  » » » 2 months ago, # ^ |   0 Thanks!
 » 2 months ago, # |   0 I used Overall dichotomous( $O(n \log^2 n)$ ) ，but TLE on 4. Am I wrong ? mysubmission
 » 2 months ago, # |   0 B problem was tough
 » 2 months ago, # |   -31 I think the most difficult problem in this contest is at most *2200 :(so it like div.3.
•  » » 2 months ago, # ^ |   +60 we heard you the first time now shut up jesus christ
•  » » 2 months ago, # ^ |   +1 Maybe most difficult one idk about that, but A, B and C's are not far from expected div2 difficulty
 » 2 months ago, # |   -9 Problem B was quite standard ! It took lots of time to understand the problem first rather than solving it.
 » 2 months ago, # |   0 D seems to be an easy one but when I started I found it a bit complicated :)..
 » 2 months ago, # |   0 Why problem B Complexity: O(n) can not pass?164782973
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I had same issue (but with Golang, not Java). I had to change standard output (fmt.Println) to bufio Writer. [Solution_1 TLE, Solution_2 AC]. It might have something to do with bufferization.
•  » » » 2 months ago, # ^ |   0 yes, this is ok 164798975
 » 2 months ago, # |   -52 Well, problem E is better to be put in an edu round. And D2 is a totally trash problem I think.
•  » » 2 months ago, # ^ |   +35 Sorry to hear. What did you dislike about D?
•  » » » 2 months ago, # ^ |   -15 Too difficult to implementation.
•  » » » » 2 months ago, # ^ |   0 just about 10 lines except for careful memory management. Where is difficult?
•  » » » » 2 months ago, # ^ | ← Rev. 3 →   +26 Hi, the intended solution codes for D2 have now been posted (here and here). IMO, the implementation in both is very clean and easy, no optimizations needed.As I said in a different comment, the difficulty in this problem seems to lie on whether you want to painfully optimize a simple idea or think a little more to find a nicer solution.
•  » » » » » 2 months ago, # ^ |   0 It says "you are not allowed to view the requested page" when I click on 2nd link(/here).
•  » » » » » » 2 months ago, # ^ |   0 Sorry, the link has been fixed
•  » » » » » » » 2 months ago, # ^ |   +19 Thanks for the contest!Awesome problems especially B,D2 and E!
 » 2 months ago, # |   +48 First time to AK a div 2 contest!
 » 2 months ago, # |   0 Thanks For This Nice Round . As a newbie : A : was straightforward. B : was hard to understand btw easy to observe the solution. C : didn't get it through the round but I think it was likely to a Div2B.
 » 2 months ago, # |   0 I am only waiting to se the ranting change
 » 2 months ago, # | ← Rev. 5 →   0 Is the below statement true? for integers a and p, where 1<= p <= sqrt(a) . floor(a/p) is unique. Proof if any?
 » 2 months ago, # |   0 My submission I am new to competitive programming. In today's contest, I solved the A problem and submitted the above solution. The above code worked for test cases but when I submitted the code, it showed runtime error on test case 2. I tried to search about runtime error but couldn't find anything. If anyone could help me with it then I would be grateful to them. Thank you.
•  » » 2 months ago, # ^ |   0 if m is smaller than n it will give runtime error.
•  » » » 2 months ago, # ^ |   0 Thank you very much for your time.
 » 2 months ago, # |   +5 How to get unique elements of a/p for an integer a and p <= k, efficiently for problem D2?
•  » » 2 months ago, # ^ |   +5 Iterate over segments:start with [1, 1]then next for [l, r] will be [r+1, a / ( a / l )]in each segment a // i is constant (l <= i <= r).
•  » » » 2 months ago, # ^ |   0 Thank you very much. And are the number of unique a/ps around sqrt(a)?, if we consider k as infinity. I wanted to calculate time complexity.
•  » » » » 2 months ago, # ^ | ← Rev. 2 →   +5 There will be no more than 2 * sqrt(a) such segmentsFirst part where r <= sqrt have l = rIn second part a / p = sqrt ... 1
 » 2 months ago, # |   +30 Ratings updated preliminary. As I said here: https://codeforces.com/blog/entry/104766?#comment-932270 cheaters will be removed later.
 » 2 months ago, # |   0 what am i doing wrong ? i rarely can solve div2c in contest time despite solving alot of high rated problems from c2 ladder and from problem set can anyone tell me what can i do? or what am i doing wrong?
 » 2 months ago, # |   0 Turned green today.:)
 » 2 months ago, # |   +3 thx for specialist-1... im totally fine after today's contest
 » 2 months ago, # |   +5 div2.5
 » 2 months ago, # |   0 I'm sorry I missed the fight
 » 2 months ago, # |   0 How to become stronger quickly
 » 2 months ago, # |   0 Can anyone share solution for second question?
•  » » 2 months ago, # ^ |   0
 » 2 months ago, # |   -13 Problems were somewhat hard in this contest.
•  » » 2 months ago, # ^ |   0 Life is not easy as you are thinking.
 » 2 months ago, # | ← Rev. 4 →   -16 The solution I wrote for problem B during the contest gave TLE but the same solution got accepted after the contest. How is it possible? This is not the right way, because of this my rank and rating got affected. Please look into this matter. EnDeRBeaT, 0mniking, AlperenT, FairyWinx, ak2006, TheScrasse, sus, SirPh, litesam, asrinivasan007, Igorbunov, Runtime-Terr0r, timreizin, Aaeria, MikeMirzayanov
•  » » 2 months ago, # ^ |   0 I tested the TLE solution and it passed, i hope your submission will be re-evaluated. I suggest you write a custom buffered I/O so this doesn't happen again.
 » 2 months ago, # |   0 Could anyone have a look at this code? https://codeforces.com/contest/1706/submission/164815320The solution got TLE before I added an early exit trick, then it got AC, I have no idea why. It seems that the early exit trick is wrong. So is the data too weak or the early exit is actually correct?
•  » » 2 months ago, # ^ |   0 why are you glorifying this shenanigan by calling it a "trick"
•  » » » 2 months ago, # ^ |   0 Is the word trick kinda glorifying? I don't think so. And, if actually it can be proved at most a certain amount of updates lead to the minimized answer, then it's not a shenanigan. This is also why I am asking here. I'm not able to construct a case failing the solution.Besides, early exit is sometimes useful in OI competitions.
 » 2 months ago, # |   0 In problem C, I wrote a recursive approach at 34 minutes and it works. But I think there will be a stack overflow and FST so I spent 15 minutes modifying my solution. Stupid me:(
 » 2 months ago, # |   0 For problem B: I used std::vector and got TLE — https://codeforces.com/contest/1706/submission/164907546 I changed to normal arrays for the same solution and got AC — https://codeforces.com/contest/1706/submission/164916818 I understand vectors are slower than arrays but can someone help me understand why I got TLE. Thanks.
•  » » 2 months ago, # ^ |   0 You are making vectors of size 100005 irrespective of n. Instead make vectors of size n, it will get accepted :)
•  » » » 2 months ago, # ^ |   0 alright, thanks
 » 2 months ago, # | ← Rev. 2 →   0 Hi MikeMirzayanov. My solution for problem A was detected as coincide with another solution. However, this is not a violation because I have not leaked or copied the code. This is only because the logic for problem A is quite simple so the 2 solutions may have looked quite the same. I also encountered this last time. I do not have concrete evidence to show that this is a false cheating detection. But I just want to inform you so that you may reduce the detection for easy problems. This may help other coders too and more importantly, I do not want to see my account blocked because of this incorrect detection.
 » 2 months ago, # |   0 Hi MikeMirzayanov. My solution 164789888 for problem 1706A significantly coincides with solutions with others. Sorry, but it was a coincidence. I write my code on ideone.com that's why the problem occurred. I think I have used ideone in public mode by mistake because I don't have an idea that someone can see my solution there that's why my solution has been copied by somebody. I will take care next time. Please give my ratings back.
 » 2 months ago, # | ← Rev. 2 →   0 Why are my ratings rolled back without any message like cheating warnings?
•  » » 2 months ago, # ^ |   0 They have been temporarily rolled back for everyone. It will be back after removing cheaters
 » 2 months ago, # | ← Rev. 2 →   0 Hi MikeMirzayanov. my solution 164765949 for the problem 1706B significantly coincides with solutions with others. But I have solved it myself you have take a look at submissions of my previous contest solutions, in which I have used same methodology to solve the problems. I haven't indulge in any malpractice in during the contest.
•  » » 2 months ago, # ^ |   +1 Even in the apology comment, you are copying from others' apology comments LMAO.
 » 2 months ago, # |   -13 As a tester, please give me contribution.The only goal for joining the test is to get more marks and get more ratings.
•  » » 4 weeks ago, # ^ |   0 We wish ourselves best wishes and that's it
 » 5 weeks ago, # |   0 best of luck