### okwedook's blog

By okwedook, 4 months ago,

Hi, Codeforces!

I finally get to return something to this great community, so I am glad to invite you to take part in Codeforces Round #703 (Div. 2), which will take place on Feb/18/2021 17:35 (Moscow time). The round will be rated for the participants with rating lower than 2100. Participants from the first division are also welcomed to take part out of competition.

You will be given 2 hours 15 minutes to solve 6 problems. All the problems were created and prepared by me. One of the problems is interactive, please read the guide of interactive problems before the contest.

I would also like to thank:

Scoring: $500-1000-(750+750)-1750-2250-3000$.

Don't forget to read ALL the problems. I wish you good luck and high ratings!

I tried my best to create some good problems and clear statements, so I hope you'll enjoy the round:)

Story

UPD: Editorial

UPD: Winners and First to solve

Div1 + Div2

Place Participant
1 renascencepjw0510
2 dlalswp25
3 Bohun
4 kmjp
5 theodor.moroianu

Div2

Place Participant
1 renascencepjw0510
2 Quirrel
3 YuuKoito
4 _Nyusha_
5 JackF

First to solve

A king_of_tt
B IgorI
C1 dlalswp25
C2 dlalswp25
D Omer223
E lulzz
F JackF

• +908

 » 4 months ago, # |   +93 As a tester, I must say problems are really interesting !! Good luck to all :)
•  » » 4 months ago, # ^ |   +37 Oo maa go TURU SPOILER
•  » » » 4 months ago, # ^ |   -17 vai prochondo hastasi ei comment deikkha,A no problem er statement e thik silo na,onek kisu missing silo,pore obosso correcition korse,,,contest suru howar aghe eisob dekhe na ken bujhi na
•  » » 4 months ago, # ^ |   +12 I will not trust you again.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +2 Problems were interesting (that idk) but till now I don't have any proof of solution of problem B!! I was submitting all the different possibilities and one of them passed :)
•  » » 4 months ago, # ^ |   -9 Meme...
 » 4 months ago, # |   +533 My plan succeeded! Now I will always be the lexicographically first tester!
•  » » 4 months ago, # ^ |   +39 Indeed, your plans are beyond someone's imagination
•  » » 4 months ago, # ^ |   +103 As a tester, nice to see 1-gon as a tester.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 Hmm.. I'm sure that after you have posted this, at some point of time a user will make his/her name "1-" thus foiling your plans.It seems unlikely that such a scenario will ever occur, but let's wait....:)
•  » » 4 months ago, # ^ |   +17 we love to see your name in the first place.Here is some suggestion that you should choose as lesser ASCII value as possible like this one -is-this-fft- can challenge you for first place. Just saying.
•  » » 4 months ago, # ^ |   +1 We want cf round from you :)
•  » » 4 months ago, # ^ |   +21 Unless...
•  » » 4 months ago, # ^ |   +7 i am wondering why there is no 0-gon
 » 4 months ago, # |   +72 Did he really thank Anton w/o any jokes? :upside_down_face:
•  » » 4 months ago, # ^ |   +115 Picture
 » 4 months ago, # |   +111 As a tester, good luck. You would need it.
•  » » 4 months ago, # ^ |   -30 Is it that hard?
•  » » » 4 months ago, # ^ |   +75 Just me trying to comment something different for all the rounds I test.
•  » » 4 months ago, # ^ |   +19 This statement seems like a challenge
•  » » 4 months ago, # ^ |   +3 Now I know why you said You would need it. ;-;
 » 4 months ago, # |   +253 Whenever authors recommend reading ALL problems...
 » 4 months ago, # |   +12 Looking forward to go gray in this round. This green is off-putting.
 » 4 months ago, # |   +18 Chance for master xD
•  » » 4 months ago, # ^ |   +12 good luck!
•  » » 4 months ago, # ^ |   +9 All The Best. And, My Chance to become a Specialist xD :(
 » 4 months ago, # |   +59 As a fellow victim of antontrygub I wish you a speedy recovery after the round
 » 4 months ago, # |   +39
•  » » 4 months ago, # ^ |   0 As a what .-. ?
•  » » 4 months ago, # ^ |   +23 You're liar!!!!!!!!!!!! YOU ARE hUaAnS
 » 4 months ago, # |   -41
 » 4 months ago, # |   +93 I request authors to disclose problems rejected by Anton.
•  » » 4 months ago, # ^ |   +6 +1
•  » » 4 months ago, # ^ |   +7 They are just waiting for the coordinator to change and suggest them again;)
•  » » 4 months ago, # ^ |   -45 I request authors to stop making contest for a while.
 » 4 months ago, # |   +28 okwedook Is it blue tears in ur pfp after rejection of 29 problems by Anton?
•  » » 4 months ago, # ^ |   0 What's pfp? And why blue??
•  » » » 4 months ago, # ^ |   +19 OMG, I've googled it. It's a nice assumption, but the photo was taken before any rejects:)
•  » » » » 4 months ago, # ^ |   0 And there is some intention behind having that blue tear :P or I am just overthinking by seeing it?
•  » » » » » 4 months ago, # ^ |   +8 Yeah, you're definitely overthinking;)
 » 4 months ago, # |   +235
•  » » 4 months ago, # ^ |   -10 Even you reposting your memes
•  » » » 4 months ago, # ^ |   +43 I just saw this picture and felt it fits it more and it's not a problem to repost 1 year old meme so many could not have seen it and that's not the first time I repost a meme
•  » » » 4 months ago, # ^ |   +4 Howdie! Detective want some real coke?
•  » » 4 months ago, # ^ |   0 true :XD
 » 4 months ago, # |   0 The KING of Ad-hoc is back again as a coordinator!
•  » » 4 months ago, # ^ |   0 This is his 1st round as a writer, isn't it?
 » 4 months ago, # |   -18 Upvote this comment for Good Luck! ¡Gracias! 
•  » » 4 months ago, # ^ |   0 De nada mami.
 » 4 months ago, # |   +1 OMG 29 problems were rejected !! Can you share some of them after contest?
 » 4 months ago, # |   +3 Scoring shows 7 questions but you said there will be 6 questions.What is correct?
•  » » 4 months ago, # ^ |   +8 I think Problem C will have both an easy and a hard version.
•  » » » 4 months ago, # ^ |   0 So they are counted as one question? Okay, got it
 » 4 months ago, # |   -17 "My first message from message from MikeMirzayanov was more than a year ago!"Shouldn't that be "My first message from MikeMirzayanov was more than a year ago!"?Or is it a message from a message...:)
•  » » 4 months ago, # ^ |   0 I never get to figure out why some comments receives upvotes beyond imagination, while mine are always downvoted :(
 » 4 months ago, # | ← Rev. 3 →   -37 An unrelated question I've already asked a few times before — how long is codeforces going to lie about its Python version?
•  » » 4 months ago, # ^ |   0 I don't give a damn if morons are downvoting!
 » 4 months ago, # |   0 I hope I won't choke this round...
 » 4 months ago, # |   +4 If Anton would have been rejecting 29 problems in 135 minutes of the contest time that would make "a speed of rejection" almost about a problem every single 5 minutes (4.6551724137931... to be exact) 
•  » » 4 months ago, # ^ |   -13 Meme
 » 4 months ago, # |   -12 antontrygubO_o deserves applause for rejecting so many problems to make the round interesting
 » 4 months ago, # |   +32 Problem D: Anton and Rejection
•  » » 4 months ago, # ^ |   +26 This will also get rejected! xD!
•  » » 4 months ago, # ^ |   +37 answer may be very large, so compute the answer modulo 1e9+7
•  » » » 4 months ago, # ^ |   0 answer is 1e9 + 6 XD
 » 4 months ago, # | ← Rev. 2 →   -16 please tell how to solve "C" after contest:) Update::first tell how to solve "B"
•  » » 4 months ago, # ^ |   +6 sometimes i feel like how life would be if i donot get downvotes!
 » 4 months ago, # |   0 Please notice the unusual Score distribution. i.e. it seems that C1 will be easier than B.
•  » » 4 months ago, # ^ |   +42 I wouldn’t infer that. It could be true, but I find it more likely that the problem as a whole is 1500, and if you can only solve it on reduced constraints you get half marks.
 » 4 months ago, # |   0 All the best guys.
 » 4 months ago, # |   0 C is interactive. Change my mind.
 » 4 months ago, # |   +10 I have some questions:1- Can the rejected problem be modified and proposed again?2- If not, can we have rejected problems in Gym added by setters?
•  » » 4 months ago, # ^ |   0 As you know, if the problem was rejected, then it is not prepared, because why
 » 4 months ago, # |   0 Hope I get my green shade back this time
 » 4 months ago, # |   0 Score for problem C is 750 so it means it will be easier than the problem B (having score 1000)?
•  » » 4 months ago, # ^ |   +9 problem C will be an interactive problem
•  » » » 4 months ago, # ^ |   +1 I too think so
 » 4 months ago, # |   +10 note: unusual duration XD
 » 4 months ago, # |   0 When Author tells "Don't forget to read ALL the problems." I think D or E will be easier than B or C. But I find D or E as same difficult as others contest.
 » 4 months ago, # |   +5 Meme![ ]()
 » 4 months ago, # |   +1 Not long left GL everyone HF!
 » 4 months ago, # |   +1 I hope you didn't set all math problems
 » 4 months ago, # |   0 @cp1307 time se aajana
 » 4 months ago, # |   +1 Why I am not improving !!!?
 » 4 months ago, # |   +4 Getting you have submitted the same code, but I haven't made any submission!!
•  » » 4 months ago, # ^ | ← Rev. 3 →   +1 Got same problem. And now i am sure that i just banged my head by giving this contest.
 » 4 months ago, # |   +9 I'm not sure what' happening. I can't seem to send a solution for A. It always says I have sent this solution before, but when I look in my submissions I don't see it. I don't see anything. I have tried putting random stuff in it, I have tried from another browser. Nothing.
•  » » 4 months ago, # ^ |   +8 I'm having the same problem... Can't submit anything.
•  » » 4 months ago, # ^ |   0 make an empty loop ... i think it will work
 » 4 months ago, # |   -9 IF I ask more than 40 queries in problem C1, what error will I get? I am getting TLE. I want to know if its due to asking > 40 queries.
•  » » 4 months ago, # ^ |   0 You can't it will be a wrong answer you are supposed to find it in 40 or less
•  » » » 4 months ago, # ^ |   0 Thank u very much sir.
•  » » 4 months ago, # ^ |   0 I asked a genuine doubt related to the contest. You all be upvoting a lame MEME and instead of answering, u guys are downvoting it. Hope u guys are doing fine.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 IF I ask more than 40 queries in problem C1, what error will I get? Potential verdicts — WA and TLE. It could be either of the two. If you asked just as many, or less queries than the number of them that would fit within the time constraint of the question, then your code would give a verdict WA not TLE. Although if you asked more queries than the number that would have run within the time limit of the problem statement, then it would give you a TLE not a WA. I am providing the links of submissions I made to demonstrate either cases hope it helps.WA-107883927, TLE-107883969PS Don't bother about the downvotes UwU.
•  » » » 4 months ago, # ^ |   0 Thank you for such a nice explanation and for the sample submissions.
 » 4 months ago, # |   -6 I really appreciate the efforts behind setting these problems. Everybody knows it was interesting. However all the problems starting from A were of a slightly higher level than usual. I understand the need to set interesting problems. But div2 is literally the most frequent round that is held, which means it needs to be catering to most ratings atleast for the first 3 problems. In that aspect, I am forced to think this round was a failure. I might be just another noob but I have only solved the first problem. But I know for a fact that the rest weren't the same level as other div2 rounds.
•  » » 4 months ago, # ^ |   0 Dude, respect for you. You at 1600 could solve only A till now, I don't know how noobs like me are exepected to compete in this round.
•  » » 4 months ago, # ^ |   0 Even i could solve only AI didnt try B because C1 seemed more interesting but dang it was too hard for me and I couldnt crack it
•  » » 4 months ago, # ^ |   0 Yeah this is so true...Every problem I tried gave WA...idk this round killed me.
 » 4 months ago, # |   +4 Its time to leave earth (after seeing problems). Bye guys! Anyway problems were interesting :)
 » 4 months ago, # |   -51 I wonder why antontrygubO_o didn't reject all of your problems :(
•  » » 4 months ago, # ^ |   +12 that's rude :v
•  » » » 4 months ago, # ^ |   -11 Not more than problem B :'(
•  » » » » 4 months ago, # ^ |   +3 Your inability to solve a problem doesn't make it rude!
•  » » » » » 4 months ago, # ^ |   +4 I am sorry. I got carried away. I will be waiting for the next round by okwedook to perform well.
•  » » » » » 4 months ago, # ^ |   0 Just evil!
•  » » 4 months ago, # ^ |   0 +1
 » 4 months ago, # |   0 Problem D is really interesting. However, My greedy approach failed :(
 » 4 months ago, # |   0 Problem D looks similar to this
•  » » 4 months ago, # ^ |   +2 Nope.
 » 4 months ago, # |   +42 A& B look like :
•  » » 4 months ago, # ^ | ← Rev. 2 →   +6 lol agree
 » 4 months ago, # |   +6 DifficultForces :(
 » 4 months ago, # |   +6 After seeing the problems I am sure why @antontrygubO_o rejected all your questions last time (that was really a nice story). Ok but as you told the questions were really interesting. "! But you should be in between the difficulty level of div2 !" Very first time I am seeing that the contest blog page upvotes are decreasing after and during the contest.
•  » » 4 months ago, # ^ |   0 +1
•  » » 4 months ago, # ^ |   +1 This particular comment didn't age really well:) Just practice more and you'll get to solve more problems
 » 4 months ago, # |   0 what is pretest 5 for c1?
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 did you try Input: n = 51hidden array = [50,49,48,47...(decrease by 1)...3,2,1,51] my code was making more than 40 queries (bcz, for this input, my code was running in the linear fashion instead binary search fashion) so, didn't submitted the code :(
 » 4 months ago, # |   0 Pretest 4 for E?
 » 4 months ago, # |   +4 damn, what's test 7 on D?
 » 4 months ago, # |   -18 ONCE AGAIN EASY D (1750)
•  » » 4 months ago, # ^ |   +3 What's the approach, my sol gets WA on test 7
•  » » 4 months ago, # ^ |   0 nice brute force submission on D
 » 4 months ago, # | ← Rev. 2 →   +19 as a youtuber, here is the video solution to problem C2: https://youtu.be/TvosdMg9GXE submission link: https://codeforces.com/contest/1486/submission/107881420
 » 4 months ago, # |   0 problem D: how to sort subarray ??
 » 4 months ago, # |   +3 ![ ]()
•  » » 4 months ago, # ^ |   +20 better than
 » 4 months ago, # |   +1 I bet all of my life on E, farewell everyone here!
 » 4 months ago, # |   +1 Well, I learned that an array of 1 elements is in increasing order the hard way
•  » » 4 months ago, # ^ |   0 5 WAs for this :)
 » 4 months ago, # | ← Rev. 2 →   0 I think the the blue tears in the profile picture of the round setter are shown to tell the participants that you're going to have those tears during the contest. Literally feeling like crying!!
»
4 months ago, # |
0

Please help why i am getting compilation error in C1,C2 ? i think my code is fine , help needed ?

help
•  » » 4 months ago, # ^ |   0 Correct me if i'm wrong but isn't that comment in // fflush(stdout); } including the brackets?
•  » » » 4 months ago, # ^ |   0 No dude it only comments fflush not the brackets !! what is my mistake can u tell me ? it is showing compilation error u can go to my profile and check the whole code !!
•  » » » » 4 months ago, # ^ | ← Rev. 2 →   0 There isn't a ; after int res = -1 edit: there is also no main function
•  » » » » » 4 months ago, # ^ |   0 ohh , fuck thanks dude !!
•  » » » » » » 4 months ago, # ^ |   0 no dude , it did not resolve the problem again it is showing the compilation error !!
•  » » » » » » » 4 months ago, # ^ |   0 Try to read your code carefully, you need to add the main function
 » 4 months ago, # |   0 Will binary search on BIT work in problem D ? Gave wrong answer on test 4
 » 4 months ago, # |   -8 How to solve B? I thought iterating $x$ in $[median(X_i) - 100, median(X_i) + 100]$ and $y$ in $[median(Y_i) - 100, median(Y_i) + 100]$ would suffice the solution.
•  » » 4 months ago, # ^ |   0 Exactly my thought too, tho instead of median, i did average, and from -5 to +5
•  » » » 4 months ago, # ^ |   0 Lol. We're brute forcing instead of solving it mathematically.
•  » » 4 months ago, # ^ |   +9 an easy hack against your solution, n=2 points at (0,0) and (1000,1000) the whole square is solution.
 » 4 months ago, # |   +6 Reading the problem D: Aha! A similar problem, just use the sliding window mediumFew moments later: Why I always failed at pretest 7?
•  » » 4 months ago, # ^ |   0 Subarray size can be at least $K$.
•  » » 4 months ago, # ^ |   0 Happened to me too
•  » » 4 months ago, # ^ |   0 Same, also fall into that trap. For those who want to use a dynamic size sliding window, you can try this test case 9 3 3 3 3 1 1 1 4 4 4 
 » 4 months ago, # |   0 Damn I was just able to solve E theoretically with like 2 minutes left :(( Can someone tell me if this is the solution? You build a graph with V_even and V_odd. You run Dijkstra, but instead of updating the the distance of V_odd, you simply add all the options of parents to it, together with the weight of the edge and the weight of the last edge. Then when it's Vodd's turn, you go over all it's neighbors and choose the best combo of path + (edge1 + edge2)^2. The problem — it runs in m^2. The solution — w_i <= 50 so you don't have to save all the options, just the best option for every 1<=w<=50! then you iterate over all the neighbors at most 50 times Is this the correct solution?
 » 4 months ago, # | ← Rev. 3 →   0 Solution of B already available on stackoverflow
•  » » 4 months ago, # ^ |   0 Why didn't you solve B then :p
•  » » » 4 months ago, # ^ |   0 found it just after the contest. Could have submitted with 30s more
 » 4 months ago, # |   +4 holly shit I got WA on pretest 2 on A don't know why then I jumped to B and didn't know how it could be solved then jumped to C and got TLE on pretest 4 I wish my meme is true cause I will lose 170 rating ugh that hurts
•  » » 4 months ago, # ^ | ← Rev. 2 →   +1 you can check for this test case: 54 2 5 1 3 this will be taking more than 40 queries for larger n
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 damn I didn't have the time to think about this cause i submitted in the last minute
•  » » 4 months ago, # ^ |   0 Holy shit, feel you bro. Can't still understand why sum>=n*(n-1)/2 ? "YES" : "NO" will give the wrong answer on test case 2
•  » » » 4 months ago, # ^ |   0 Because you can swap only ith to (i+1)th.
•  » » » 4 months ago, # ^ |   +3 Consider the array 0 0 6. The sum is >= 6 but because we cannot move blocks leftwards, we cannot make it strictly increasing.
•  » » » 4 months ago, # ^ |   +2 Your code will fail on the following test case: n=5 1 1 0 3 5 You should check sum>=i*(i-1)/2 on every index or try a different approach.
•  » » » » 4 months ago, # ^ |   0 Yea, we have to check sum(0...i) >= i*(i-1)/2 for every i from 0 to n-1. I dunno why I couldn't figure this easy logic in the contest
 » 4 months ago, # | ← Rev. 2 →   0 For problem D, this was helpful https://codeforces.com/blog/entry/21103If you are need a test case that break your solution, these may help 7 4 5 5 4 4 4 5 5  11 6 5 5 5 4 4 4 4 4 5 5 5 And I foresee problem D will become yet another coding interview question.
•  » » 4 months ago, # ^ |   0 Yeah for D, you can also have a look at Edu binary search step 4
•  » » 4 months ago, # ^ |   0 The second test case's N should be 11 not 4
•  » » » 4 months ago, # ^ |   0 Oh yes thank you
•  » » 4 months ago, # ^ |   0 I don't understand what Reyna is saying. Can someone explain more celarly?
 » 4 months ago, # |   0 Why am I getting idelness limit exceeded? 107863650
•  » » 4 months ago, # ^ |   0 try using cout.flush()
•  » » » 4 months ago, # ^ |   0 But I flushed the output several times and also used endl...
•  » » 4 months ago, # ^ |   0 Sorry for bumping but I can't really get the problem that the solution gives idelness limit exceeded
•  » » » 4 months ago, # ^ |   0 I guess it's because endl has a flush effect. try #define endl '\n' on the top of the code
 » 4 months ago, # |   +4 People like me, who had seen Cf Edu Binary Search step 4, can easily get the intuition for D. Loved the problemset. D was savior.
•  » » 4 months ago, # ^ |   0 Can you please give the link of "Cf Edu Binary Search step 4" , which you mentioned ? (Beacuse , I want to read that first before upsolving D )
•  » » » 4 months ago, # ^ |   +1 https://codeforces.com/edu/course/2/lesson/6/4 it's just in the menu above
•  » » » » 4 months ago, # ^ |   0 Thank You !
 » 4 months ago, # |   +5 B killed me
 » 4 months ago, # |   +32 Problem D is exactly the same as this oneFor problem F, you can copy this code (statement: calculate how many pairs of paths intersect with each other) and 1336F - Journey then subtract the answer from the previous one.
 » 4 months ago, # |   0 Implemented some simple brute force in E which passed in ~800ms, now assume systest will make it fail. How to correctly solve E?
•  » » 4 months ago, # ^ |   0 time limit is 4 seconds . Why it will fail ?
•  » » » 4 months ago, # ^ |   +6 I am basically iterating all paths of len=2 and build a second graph from that. That feels to simple to be the right solution.
•  » » » » 4 months ago, # ^ |   +16 It should ideally fail, consider any star graph, that will give you $O(n^2)$ edges in the new graph.
•  » » » » » 4 months ago, # ^ |   0 Yes. Funfact, it passed the systests, so I got the nice plus delta, then later was hacked ;)
•  » » 4 months ago, # ^ |   0 Your first solution to E was skipped on main tests. What is it why does it happen?
•  » » 4 months ago, # ^ |   0 It didn't failed ;) . Was that due to to weak tests ?
•  » » » 4 months ago, # ^ |   +3 Yes.
 » 4 months ago, # |   +1 How to solve B?I know it's lame to ask... but please, any short solution would work.
•  » » 4 months ago, # ^ |   +4 Try plotting some random points on Desmos or some other tool and brute force the answers. You'd see the pattern.I tried proving the solution for an hour, gave up and this seemed the only option left. :p
•  » » » 4 months ago, # ^ |   0 Noiceee!!
•  » » 4 months ago, # ^ |   0 I can give you a hint if you want. Ia a rush rn.It's related to median. For both x and y coordinates.
•  » » » 4 months ago, # ^ |   0 Yes, I know that relation, but wondering how wd that be useful here.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +3 Problem B is a 2D problem which can be broken down into two independent 1D problems. First, minimize the sum of |xi-x| and then do the same for |yi-y|. The median of an array comes into play here.For array ai .... an, you have to choose a value k such that summation of |ai-k| is minimized. This can be done using median. You can apply it to the above 1D problem.It is a very vague explanation but hope this helps !!
•  » » » 4 months ago, # ^ |   +1 Thanks a lot!
 » 4 months ago, # |   +1 C was a really nice use of binary search. Hope pretests were strong enough.
 » 4 months ago, # |   -12 Now I can truly understand why your problems got rejected in the first place
 » 4 months ago, # |   0 Someone please tell me why my solution is wrong and the other solution is correct. http://codeforces.com/contest/1486/submission/107798098 http://codeforces.com/contest/1486/submission/107782432
•  » » 4 months ago, # ^ |   +10 In your submission, you do: else { f = 1; break; } so you break early before you finish reading all of the input. Because there are multiple test cases, the input then spills over to the next test case, and everything gets messed up.
•  » » » 4 months ago, # ^ |   0 Thanks a lot, Finally understood my mess after submitting it almost 4-5 wrong submission. :-:
•  » » » 4 months ago, # ^ |   0 Your handle is also "smax", are you the author of Problem C1 and Problem C2? hhh...
 » 4 months ago, # |   +3 For B question .. why does the count from avg-1,avg,avg+1 fails ?
•  » » 4 months ago, # ^ |   0 Average is not a correct answer to get minimum distance. For example, if we look only on X-axis and points at 0, at 4 and at 4 again, the average of them will be 8/3~2.66, but the best point to get minimum distance will be 4
•  » » » 4 months ago, # ^ |   0 sorry but i forget to mention .. for cases with distinct nos like x[]=1,2,5,10,100; any intuitive/ mathematical proof ( generalized )
•  » » » » 4 months ago, # ^ | ← Rev. 3 →   0 In any case we need to use median instead of average. Lets imagine, that we have array of N different points and N = K*2 + 1 (just to make the explanation easier). Lets then pick median of this array as point P and calculate total distance to all points, it will be some number D. We may notice, that K points are to the left of P and K points are to the right of P. Denote distance to points to the left of P as D_left and distance to points to the right of P as D_right. So D = D_left + D_rightThen look at neighbour point P - 1 and calculate total distance: New distance = D_left - K * 1 (because we reduced distance to K points by 1) + 1 (we increased distance to initial point P by 1) + D_right + K * 1 (we reduced distance to K points by 1) = D_left + D_right + 1 So by picking any other point then P we will increase total distance.
•  » » » » » 4 months ago, # ^ |   0 Got it !! Thank you so much dude :)
•  » » » 4 months ago, # ^ |   0 i handled the repeating cases separately
•  » » 4 months ago, # ^ |   0 Take this array as example [2, 2, 11]. The avg is 5 which results in a total distance of 12. But if you use median instead of the avg, you definitely would get a better result. In this case when you choose 2 (which is the array's median) instead of 5 the total distance will be 9, which is better than 12.
•  » » » 4 months ago, # ^ |   0 sorry but i forget to mention .. for cases with distinct nos like x[]=1,2,5,10,100; any intuitive/ mathematical proof ( generalized )i handled the repeating cases separately..
•  » » » » 4 months ago, # ^ |   0 [2, 3, 1000]your ans: 1330 correct ans: 998The median is an optimal choice, because if x is smaller than the median, the sum becomes smaller by increasing x, and if x is larger then the median, the sum becomes smaller by decreasing x. — CP handbook
•  » » » » » 4 months ago, # ^ |   +3 Thank you so much :)
 » 4 months ago, # |   +6 This is the first-ever time I got an idea on how to solve Problem D, to know the median in constant time we can use two heap approach, I made the window as two heap's and each time I move the window I insert an element into heap O(log K) time, but I don't know how to remove a random element from the heap in the logarithmic time since while sliding the window we need to pop the 1st element of the window each time. so I went by removing elements in O(K) time, but went with TLE in Test case 7. can someone help me on how to remove random elements from the heap with less complexity or any other better approach to solve the D problem?Attaching my Python Solution. MY solution in Python Using Two Heap
•  » » 4 months ago, # ^ |   +1 If codeforce were kind enough to accept sortedcontainers you could use SortedList. Also I think your solution would only return the maximum median of subarray of size exactly k and not at least k. so on n=5 k=2 a=2 1 2 1 2 your algorithm would answer 1 instead of 2 if it considers subarray of size 3.
•  » » » 4 months ago, # ^ |   0 Thanks for pointing it out, I misread the question, I taught max median in window size k question, but it's actually max median in window of size at least k. I taught I can solve DI have seen about sorted containers, since it's not allowed in most websites(i don't know why), I went with the 2 heap approach. is there any efficient way to remove random elements from the heap? and what is the efficient way to solve this question in python?
•  » » 4 months ago, # ^ |   0 I once wrote a simple class to maintain a median, where you can add and remove values in O(logN). see this submission
 » 4 months ago, # |   0 Memory limit exceeded for using map in problem B. Anyone, any trick to modify this code to avoid MLE. I used map for storing the visited points in a recursive function.
 » 4 months ago, # |   0 Once again a question directly from Google, problem B!
 » 4 months ago, # |   +44
 » 4 months ago, # |   +1 Le me after this round - Spoiler...
 » 4 months ago, # |   +12 Poor me created 5 cpp files for the contest and I only solved A (-_-)
 » 4 months ago, # |   0 What is the failing case for this submission? https://codeforces.com/contest/1486/submission/107861220
•  » » 4 months ago, # ^ |   +3 Test with array $[1, 2, 3]$: INPUT OUTPUT 3 ? 1 3 2 ? 1 2 1 ! 2 
•  » » » 4 months ago, # ^ | ← Rev. 2 →   0 Yikes! I did try [1 2 3 4 5] during the contest, smh. Thanks!Edit — The one I submitted before this didn't have this problem. Can you think of some case for this one too? https://codeforces.com/contest/1486/submission/107847201. I tried to come up with something by myself but couldn't.
•  » » » » 4 months ago, # ^ |   +3 With array $[8, 9, 6, 7, 4, 5, 2, 3, 1, 10]$, you get the following: INPUT OUTPUT 10 ? 1 10 2 ? 1 2 1 ? 3 10 4 ? 3 4 3 ? 5 10 6 ? 5 6 5 ? 7 10 8 ? 7 8 7 ? 9 10 9 ! 10 Can you see the pattern? If I use a larger array with the same pattern, you will definitely exceed the query limit.
•  » » » » » 4 months ago, # ^ |   0 Yes I get it. Thanks again!
 » 4 months ago, # |   +10 Before realising the intended solution to E, I was thinking about using Convex Hull Trick to optimize dijkstra in the following way. If I am at some vertex $u$, for every edge $(u, v)$ I insert into the convex hull data structure (initially empty) the line $mx + c$ where $m = 2 * w(u, v), c = dist[v] + w(u, v) * w(u, v)$. After inserting all of them, then for each vertex v I do $dist[v] = min(dist[v], w(u, v) * w(u, v) + query(w(u, v)))$, where query is the usual query for the convex hull trick data structure (returns the minimum function value) and $dist$ is an array containing the answer for all the vertices. I think implementing this directly in dijkstra won't work for a variety of reasons. I wanted to ask if there is any way in which we can use this trick to solve this problem for arbitrarily large edge weights (say $1 \le w \le 10^9$).
 » 4 months ago, # | ← Rev. 2 →   -13 .
 » 4 months ago, # |   +5 In problem B "sum of distance" instead of "summary distance" would have saved time of both setters and participants .
 » 4 months ago, # |   0 Is there any solutions somewhere that I can find?
•  » » 4 months ago, # ^ |   0 Problem B is directly from stackoverflow. Here is the link: https://stackoverflow.com/questions/10402087/algorithm-for-minimum-manhattan-distance
 » 4 months ago, # |   0 Wow!What a wonderful contest! It made my day :D
 » 4 months ago, # | ← Rev. 2 →   0 Can D be solved using ordered multiset and considering the subarrays of size k only? like this, Codeint main() { ordered_set o_set; int n,k, ans = 0; cin >> n >> k; int a[n]; for(int i=0;i> a[i]; for(int i=0;i
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 I tried something like this, Got WA on pretest 5.
•  » » 4 months ago, # ^ |   0 I think it will fail on test 7. I did the same approach
•  » » 4 months ago, # ^ |   0 3 2 2 1 2 actual answer is 2 your answer is 1, but it I still wonder if you consider only k and k+1 if it would work
•  » » » 4 months ago, # ^ |   0 I ran the same approach for k to k+10, it passed test 7 but it failed test 8 then
•  » » » 4 months ago, # ^ |   0 I found https://stackoverflow.com/questions/55785883/how-to-calculate-the-maximum-median-in-an-array, which proves that subarrays of 2 or 3 are sufficient when k is 1. However I don't think that proof generalizes to a constant number of subarrays for an arbitrary k, you need at least 2k or 2k + 1 to apply the same logic used in one of the comments.
 » 4 months ago, # |   +34 Impressive, Qzy___ solves B on 0:11 (107793144) and D on 0:12 (107794288). How do you guys do it with such difference in the code style? Do you keep two different templates for some reason?
 » 4 months ago, # | ← Rev. 2 →   0 107793970Where does my solution fail in A. Can anyone help
•  » » 4 months ago, # ^ |   0 Your early return causes issues since you still need to read all $n$ integers.
•  » » » 4 months ago, # ^ | ← Rev. 3 →   0 My goodness!!A contest could not be worse
•  » » 4 months ago, # ^ |   0 You are returning from the function without completely reading the input
 » 4 months ago, # |   +12 why the brute-force is passing problem E????
 » 4 months ago, # | ← Rev. 2 →   +26
 » 4 months ago, # |   +10 Can someone tell me whats wrong with this solution for problem A: https://codeforces.com/contest/1486/submission/107836476
•  » » 4 months ago, # ^ |   +2 You are answering before reading the whole array.
•  » » » 4 months ago, # ^ |   0 Oh my god, how could I be so dumb! Even failed system tests for C1, Bad day!
•  » » » » 4 months ago, # ^ |   +1 Happens, you can tell this incident here
•  » » 4 months ago, # ^ |   +1 Brothers!!
 » 4 months ago, # |   0 Did someone else also face pretest 3 failing in C2? It has to be quite a good pretest!
 » 4 months ago, # |   +3 The pretests for A were that good, that there was no test where submissions without long long would not pass. Good job!
•  » » 4 months ago, # ^ |   +3 How do you check how many solutions FSTed? Is it through the status tab?
•  » » » 4 months ago, # ^ |   +3 On standing page, on the bottom.
 » 4 months ago, # |   +38
•  » » 4 months ago, # ^ |   0 I hope I promote to pupil :D
•  » » » 4 months ago, # ^ |   0 I hope I promote to expert :D
•  » » 4 months ago, # ^ |   +2
 » 4 months ago, # |   0 Please release the editorial.
 » 4 months ago, # |   +16 Which was the point of E? It was just an easy and classic Dijkstra.
•  » » 4 months ago, # ^ |   +21 The system test is TOO WEAK.
•  » » » 4 months ago, # ^ |   0 I also thought so.
 » 4 months ago, # |   0 can someone pls tell me how to try different testcases of interactive problem in my IDE
 » 4 months ago, # | ← Rev. 2 →   0 The official can tell me why my code was skipped for C1 question, I didn’t give anyone my code.
•  » » 4 months ago, # ^ |   0 Your submition skips when you submit another one that passes pretests.
 » 4 months ago, # |   +7 Today I learned a lesson — don't participate in a contest while sick with (probably) COVID-19. :)
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 It's official now. Can my last rating drop be reverted on compassionate grounds upon submission of the positive covid test result. Just kidding... :)))
 » 4 months ago, # |   0 For the first time, in my room no solution failed system tests!! Thanks for strong pretests!!
•  » » 4 months ago, # ^ |   +8 Well, it's easy to make it appear like there are strong pretests when systests are absolutely garbage :)
 » 4 months ago, # |   0 Thanks for your good problems that help me be the Candidate Master!
 » 4 months ago, # |   0 c1 should have larger amount of queries, my code was right but i did not bother to do a simple optimization on queries as there was already a c2 with less queries.
•  » » 4 months ago, # ^ | ← Rev. 2 →   +6 Your mistakes should be fixed by you, not by problems setters.
•  » » » 4 months ago, # ^ |   0 Yes, sorry i agree that it was my mistake, but c2 with less queries just messed that thing in my mind.
 » 4 months ago, # | ← Rev. 2 →   +9 How can a $O(n \times m)$ solution pass the system testing (or even the pretests) on problem E?This is the submission. Clearly two for loops.107866037
•  » » 4 months ago, # ^ |   +16 له له له
 » 4 months ago, # |   0 Can anyone tell me whether the meaning of strictly increasing suits a sequence with 1 element or not?
 » 4 months ago, # |   0 I think Problem C1 and C2 are just like one problem? I can't feel the gap between them.
•  » » 4 months ago, # ^ | ← Rev. 2 →   0 In C1 you can perform two queries in each iteration of binary search which gives a simpler solution than that for C2.
 » 4 months ago, # |   0 OK. As it seems someone really tried to make weak pretests. There was so obvious error in my code. And I got pretests passed. What's the point of giving feedback, if obviously wrong solutions pass pretests? just look what have I written: "if(ans==ind)r=mid,l=mid;" and it passed pretests. I will worry about my rating, but it's funny
 » 4 months ago, # |   +30 E should be retested.
 » 4 months ago, # | ← Rev. 4 →   0 Can anyone tell me what does the Error in this solution means https://codeforces.com/contest/1486/submission/107864397, And can someone give me one TC on which this solution fails. Helping in even one would be highly appreciated . Thanks in Advance
•  » » 4 months ago, # ^ |   +1 With array $[1, 2, 3, 5, 4]$: INPUT OUTPUT 5 ? 1 5 5 ? 1 5 5 ? 5 5 The last query shown above is invalid, since the subarray needs to have at least size 2.
•  » » » 4 months ago, # ^ |   0 Is this the Error that the CF judge has also mentioned BTW Thanks for your help
 » 4 months ago, # |   +1 I made a stupid mistake and used k+1 instead of k in D, passed pretests, but failed in system testing:(And I went all the way from Rank 3 to Rank 23:(
•  » » 4 months ago, # ^ | ← Rev. 2 →   +13 Looks like you a red coder in your main account.
 » 4 months ago, # |   +40 E should be retested. There are codes that solves E by making a M^2 edges Graph
 » 4 months ago, # |   +73 To not keep you waiting, the ratings updated preliminarily. In a few hours, I will remove cheaters and update the ratings again!
 » 4 months ago, # |   +11 The problems were really interesting!Kudos to the authors, and the coordinators involved! :)
 » 4 months ago, # | ← Rev. 2 →   +19 okwedook MikeMirzayanov I would like to request a rejudge of E because the judge behaviour is inconsistent: 107850881 is TLE and 107877393 is AC but both are the same code (you can check with Compare)UPD: of course, the algorithm itself is not randomized in any way
•  » » 4 months ago, # ^ |   0 This comment might be able to explain the mentioned judge behaviour.
•  » » » 4 months ago, # ^ |   -17 I understand why this may happen, but I think that it is not my problem if the CF server was a bit slower in one of the runs. The behaviour should be consistent because, if I understand the situation correctly, I passed the pretest during the contest and failed the same pretest afterwards. This is clearly unfair because I was lured into the fake sense of security by 25! strong pretests, and (based on the "passed pretests" verdict) decided not to optimize my solution further during the contest not to lose points.
•  » » » » 4 months ago, # ^ |   +29 You passed pretests with 3992ms. And then decided to not optimize further? Sorry, but that is known to be no good idea.
•  » » » » » 4 months ago, # ^ |   0 When I see such execution times on a high number of pretests, I think "oh, they must be quite strong". Regardless of what I think, CF cannot implicitly assume that I should optimize my code whenever I see high execution times on pretests because I may fail the same test later.
•  » » » » » » 4 months ago, # ^ |   0 Well... CF can. And does.
•  » » 4 months ago, # ^ |   0 Ok, after a bit of thinking I came to the conclusion that rejudge is not a good solution in a long run, and my best idea so far is not to re-run the pretests during the system testing. This way my argument about inconsistent behaviour will not be as legitimate.
 » 4 months ago, # |   0 wrong answer Integer parameter [name=query_r] equals to 27671, violates the range [27672, 99999]Could anyone please tell me what this means? I got this for C1
•  » » 4 months ago, # ^ |   0 I too had the same error , it means that in a query , your l and r are equal
•  » » » 4 months ago, # ^ |   0 Ok thank you
 » 4 months ago, # |   +9 Great question C2 really liked it
 » 4 months ago, # |   0 Problem B statement: Are there any non-2D planes? And "восточная выставка" is "oriental fair" in English. ;)
 » 4 months ago, # |   +5 what a great set of problems. thank you and thanks to the coordinator for rejecting the other problems.
 » 4 months ago, # |   +8 very weak test cases in C2, E....
 » 4 months ago, # | ← Rev. 2 →   0 I am getting runtime error on testcase 6 for the E problem , here is the link of my submission , can some one please check it!!, What I have done is kept n*51 states and edge of weight 0 between (u,0) & (v,w) , edge of weight (a+w)^2 between (u,a) & (v,w) , for the edge u,v with weight w given in question, I applied dijkstras on transformed graph..
 » 4 months ago, # | ← Rev. 4 →   +15 Strange
•  » » 4 months ago, # ^ |   +8 See This blog
•  » » » 4 months ago, # ^ |   0 Thanks
 » 4 months ago, # | ← Rev. 2 →   -18 i whink DE is a bit too easy for its position, D ia a sinple binary search and E's dijkstra solution is O(m log 50m)maybe better if put them in CD and get a harder problem for E
 » 4 months ago, # |   0 Question B Why not consider that a point may have multiple homes？
 » 4 months ago, # |   +1 For problem E, O(NM) passed system tests. The hack cases can be generated easily with a simple source. It's amazing that the system tests didn't had any hack cases for the O(NM) solutions...
 » 4 months ago, # |   +3 Can someone help me to find what's wrong with my solution for Problem A ? 107831213
•  » » 4 months ago, # ^ |   +3 You are not taking the complete input.
 » 4 months ago, # |   +1 the approach discussed in Question B can be extend to 3D plane also ?
•  » » 4 months ago, # ^ |   +8 Yes, any number of dimensions. They'll all be independent.
•  » » » 4 months ago, # ^ |   0 Thank you for the problems okwedook, really nice contest although I solved only one, I enjoyed during the contest and after the contest learning through it.
 » 4 months ago, # |   0 Can someone elaborate how you all are creating graph before applying Dijkstra?
 » 4 months ago, # | ← Rev. 2 →   0 I am observing about a 2x difference between the runtimes of two solutions, by just changing the way I am indexing the array. I understand that this is because of different localities of reference between the solutions.Yet, I am not able to figure out why one of these has a higher locality of reference. If someone can help me figure out the same, it will be greatly appreciated.These are the two submissions: 108047029 108047388
 » 4 months ago, # |   0 why aren't any difficulty level tags provided for any of the questions which falls under this contest ?
 » 4 months ago, # |   0 can anybody tell me what is wrong in my code for problem D my solution my solution is in python3 it is a brute force approach for problem D. it may give Time Limit exceed but the point, it is giving Wrong Answer in test case 7. i don't know why because i feel the logic is correct. can you find the edgecase (why it is giving wrong answer verdict)thank you in advance.