### geranazavr555's blog

By geranazavr555, 4 years ago, translation,

Hello, Codeforces!

We are glad to invite you to take part in Codeforces Round #568 (Div. 2), which will be held on Jun/19/2019 17:45 (Moscow time). The round will consist of 7 problems (possibly, plus subproblems). It will be rated for Div. 2 participants.

We, geranazavr555 and cannor147, are students of ITMO University. And we have recently joined the developers team of Codeforces and Polygon. We have prepared this round for more careful acquaintance with the system. We hope that you will enjoy the competition.

Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such rounds. MikeMirzayanov suggested to make this to be rated for the second division.

Many thanks to MikeMirzayanov for the tremendous work on the creation and development of Codeforces and Polygon and coordinating our work. Also, special thanks to Vshining, awoo, nooinenoojno, vovuh, Lewin, Dave11ar, T-D-K and Azat_Yusupov for testing the round.

Good luck!

UPD1:

The scoring distribution will be: 500 — 1000 — (1000 + 750) — 2000 — 2250 — 2750 — (2750 + 750). The round will last 2 hours and 15 minutes.

UPD2:

Congratulations to the winners:

UPD3:

Editorials are available here.

• +328

| Write comment?
 » 4 years ago, # |   +48 Another rare round with 7 problems in Div.2!I hope the contest provides great experience to both the problemsetters and the contestants.
 » 4 years ago, # |   +33 Congratulations!! for organising first time.Hope it will be a good. Thank You.
 » 4 years ago, # |   0 Hope, no problems with big numbers. Good luck for everyone!
•  » » 4 years ago, # ^ |   +29 Lol, I can see the scar of the previous contest.
•  » » » 4 years ago, # ^ |   +4 even problem C was easier to implement than B
•  » » » » 4 years ago, # ^ |   -15 really, C was filled with corner cases while B was just sum of big numbers with single corner case.(ending with 0).
•  » » » » » 4 years ago, # ^ |   +17 What corner cases C had?
•  » » » 4 years ago, # ^ |   +6 it was a really big scar );
•  » » 4 years ago, # ^ | ← Rev. 2 →   +17 try python. Some problems are easy if implemented in python. Especially problems does not constrain strictly on complexity.
 » 4 years ago, # |   +22 Wish you the best of luck for organising your first contest
•  » » 4 years ago, # ^ |   +24 Thanks!
 » 4 years ago, # |   +63 Initially, we had prepared the round for Div. 3. This round would have been a rare Div. 3 in which vovuh's not a setter.
 » 4 years ago, # |   -6 Good luck and have fun everyone! :)
 » 4 years ago, # |   -14 lol
 » 4 years ago, # |   +82 Div(2.5) XD
•  » » 4 years ago, # ^ |   +44 It's a Div.3, but rated for blue and purple ones. Doesn't happen every day :)
•  » » » 4 years ago, # ^ |   +64 It seems it turned out to be a typical Div. 2 round with a greater number of problems. I hope that everyone in Div.2 will find interesting problems for him/her.
•  » » » » 4 years ago, # ^ |   0 I love interesting problems
•  » » 4 years ago, # ^ |   +16
 » 4 years ago, # |   +20 Congrats for your first rated round.Hopes your hard work pays off and we can get many more round in future. Good Luck!!
•  » » 4 years ago, # ^ |   +19 Thanks a lot! Wish you high scores on the contest! :)
 » 4 years ago, # | ← Rev. 2 →   0 Is div2 contest rated for div3 (<1600) participants? Can someone explain the rules.PS: i googled it, but couldn't find the answer.
•  » » 4 years ago, # ^ |   0 Yes.
•  » » » 4 years ago, # ^ |   0 Thanks for your reply, but any idea on why it is mentioned "it will be rated for div2 participants" in above contest description?
•  » » » » 4 years ago, # ^ |   0 div_x_participants = ∑( i=x -> i=3 ) div_i_participants
•  » » » » » 4 years ago, # ^ |   +55 Wrong answer on test 1 Input x = 1 Output 1 + 2 + 3 Answer 1
•  » » » » » » 4 years ago, # ^ |   +62 Successful hacking attempt!
•  » » » » » » 4 years ago, # ^ |   +5 My fault, since I'm just a poor div2 participants, this is totally extracurricular knowledge for me QAQ
•  » » » » » 4 years ago, # ^ |   +5 So if x = 1 + 2(div1 + div2)?
 » 4 years ago, # |   +10 Initially, we had prepared the round for Div. 3, but after testing, it became clear that this round is harder than usual such roundsMy prediction : A, B, C, D, E are easy problems with some implementation. F is of level div2 D, and G is hard.
 » 4 years ago, # |   +35 hope it will not be hard code as the last div 2
 » 4 years ago, # |   +1 Codeforces Round #568 (Div. 2.5)
 » 4 years ago, # | ← Rev. 3 →   +27 Notable points on distribution 750 gap in BC CDE are in similar level G has 3500 points By the way, 2 hour 15 minutes for 7 problems.. Our hands will not be able to stop during contest :(
 » 4 years ago, # |   0 Back to back rounds...yeahhhh!!!...Thanks for the effort..
 » 4 years ago, # | ← Rev. 2 →   +28 AB — Div3 CDE — Div2 FG — Div1 Overall — (1*2+2*3+3*2)/7 = 14/7 = 2 So we are having a Div2 today with +/- error of "possibly, subproblems"
 » 4 years ago, # |   +13 We need more problems!
 » 4 years ago, # |   +4 Now there are more and more subtasks in the problems.
 » 4 years ago, # |   +13 Hope pretests pass=>system test pass,becomes true in this contest.
 » 4 years ago, # |   +11 Can the contest be longer? That seems like a lot of problems for 135 minutes..
•  » » 4 years ago, # ^ |   -8 it seems it is not a bad contest with lots of implementations because its 9 problems :)
 » 4 years ago, # |   +6 contest is going to be interesting.i hope more 10000 people will do participate.
 » 4 years ago, # |   -9 Is it a wise idea to write contest on mobile and not using paper-pencil due to power-cut?
 » 4 years ago, # |   +28 It can be true that the number of participators will be greater than 10000.
 » 4 years ago, # |   +31 Why was the game delayed by 10 minutes?
 » 4 years ago, # |   0 Delayed for 10 minutes!!
 » 4 years ago, # |   +162 Hi. Sorry, the delay is my fault. I forgot to change the contest type from ICPC to CODEFORCES. Now it is fixed.
•  » » 4 years ago, # ^ |   0 Never mind :)
•  » » 4 years ago, # ^ |   0 Anybody helpful enough to tell the difference between the two types? :)
•  » » » 4 years ago, # ^ |   +2 ICPC -> Educational + Div3Codeforces -> Score Based. 500 -> 1000 -> .....
•  » » 4 years ago, # ^ |   0 I thought it was delayed to reach the 10k mark. Is it happening for the first time though?
•  » » » 4 years ago, # ^ |   +3 was and 11k
•  » » » 4 years ago, # ^ |   +5 11,769 is highest registration in any Codeforces Round (Hello 2019), It looks highest registration for any division 2 Round.
•  » » 4 years ago, # ^ | ← Rev. 3 →   +22 come on, you just wanted 10k+ registrants
 » 4 years ago, # |   +15 First time I have seen more than 10k participants.
 » 4 years ago, # |   +23 This is the biggest contest I've ever seen on Codeforces, both tasks wise and participants wise.
 » 4 years ago, # |   +9 for any one have trouble use
 » 4 years ago, # |   +24 I think it is bad to give 2750 points for problem G1
•  » » 4 years ago, # ^ |   +213 I think it is bad to write anything about problems during a round.
•  » » 4 years ago, # ^ |   +1 Maybe people learn to read all problems :D
•  » » 4 years ago, # ^ |   0 +1As soon as I solved G1. I wasn't motivated to think about G2.
 » 4 years ago, # |   +5 OMG this was the BEST contest ever! Incredible one!
 » 4 years ago, # | ← Rev. 2 →   0 Daaaaamn if just 2 minutes I could've tried D edit : Nevermind it was wrong XD
 » 4 years ago, # |   +11 Great round, thank you a lot!
 » 4 years ago, # |   +235 You should've left it as Div 3.
•  » » 4 years ago, # ^ |   -21 2 hours would have been enough too
•  » » 4 years ago, # ^ |   +11 at least it doesn't contain a lot of hacks like your rounds
•  » » » 4 years ago, # ^ |   -36 Ye, ofc it's much better to have 6 dummy problems without hacks than nice problems with hacks
•  » » » » 4 years ago, # ^ |   -36 yes it is better, because what is the point of solving great problem and then get hacked because of silly bug ?
•  » » » » » 4 years ago, # ^ |   -9 Maybe you shouldn't write code with bugs. (:
•  » » » » » » 4 years ago, # ^ |   -12 i think even tourist sometime writes code with bugs
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   +6 Tourist does write code with bugs sometimes, and he every gets hacked occasionally. But do you think he goes and blames the problem setter when this happens?(I mean maybe he does, ¯\_(ツ)_/¯)
•  » » » » » » » » 4 years ago, # ^ |   +5 anyway this is pointless discussion, for me i hate problems with weak cases and i think getting points by easy problems is better then getting them from hacking
•  » » 4 years ago, # ^ |   +1 At least they could hide that the problems were originally for a Div 3 contest, as this hinted that it would be a speed-coding contest and put pressure on contestants (or at least me).
 » 4 years ago, # |   0 How to solve D?
•  » » 4 years ago, # ^ | ← Rev. 3 →   +63 There are three cases: Remove maximum element Remove minimum element Remove an element that is not maximum nor minimum The first two is trivial. For the third one, notice that the maximum and minimum value will not change, and you can use these two value to reconstruct $d$ (which is $\frac{max - min}{n-2}$) and then find the element you need to remove.
•  » » » 4 years ago, # ^ |   +9 Please don't put it like this. You make me sound so stupid for not being able to solve it. (pun intended) (T_T)
•  » » » 4 years ago, # ^ |   +1 For 3rd case, it should have been divided by n-2 instead of n-1, since we are assuming after deleting one element, we get the AP correct. Great approach, implemented yours way, and it became so easier to write :)
•  » » » » 4 years ago, # ^ |   +2 My mistake. Fixed.
 » 4 years ago, # |   +26 What was the shit about TC21 in D?
•  » » 4 years ago, # ^ |   +9 same question...
•  » » » 4 years ago, # ^ |   +4 :(
•  » » 4 years ago, # ^ |   +9 I think this is a test-case where the whole array forms an arithmetic progression and either the largest element's position is not n or the smallest element's position is not 1.
•  » » » 4 years ago, # ^ |   0 I don't think so.
•  » » » » 4 years ago, # ^ |   +55 Maybe this is not your problem. But I got WA on pretest 21, and my mistake was that in case that the array already forms an arithmetic progression, I was printing n (then fixed it to print the position of the largest element before sorting).
•  » » » » » 4 years ago, # ^ |   +13 Wasted an hour on this bug, thank you for explanation :)
•  » » » » » 4 years ago, # ^ |   +13 Ohhh. Same mistake.Thanks.
•  » » » » » 4 years ago, # ^ |   +9 I was printing 1.:(
•  » » » » » 4 years ago, # ^ |   +6 I was thinking of this bug for literally an hour and forty five minutes during the contest and was not able to get it as I was not giving any test cases related to it thinking that it was obvious.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 Try this 5 3 4 1 5 2 
•  » » » 4 years ago, # ^ |   0 Thanx man :)
•  » » 4 years ago, # ^ |   0 exactly ???
 » 4 years ago, # |   +8 what is the pretest 21 of problem D :(
•  » » 4 years ago, # ^ |   +1 It was the first test with big n.
 » 4 years ago, # |   +19
•  » » 4 years ago, # ^ |   0 Ah, here lies the Gold among so much Clutter.
 » 4 years ago, # |   +41 That moment when you read G1 when 10 minutes remain and realize your strategy for the contest sucked.
•  » » 4 years ago, # ^ |   +4 I read and coded it in less than 8 minutes and was also wondering why didn't i read all the problems before.even problem A took me more than 8 minutes :p
 » 4 years ago, # |   0 A person who solved all the problem has lesser score than some people who solved 8 problems ...well played Codeforces!
 » 4 years ago, # |   +11 So doing G2 first and submitting both is way less fruitful than quickly submitting G1 and then coding G2 again? That sucks!
 » 4 years ago, # |   +188 What was problem F about? Write bruteforce? Probably C requires more thinking.Also I don't like subtasks in codeforces format. Today correct strategy was to write G1 first, and then think about G2. It is strange.
 » 4 years ago, # |   +205 Problems with subtasks are completely inappropriate for codeforces contest format. For example, today to maximize score one should probably implement a stupid solution for G1 at first and then G2. Such problems are ok on IOI format (without penalty for wrong submissions and time) but have weird drawbacks here. Also, in most cases including one of the versions in the contest is unnecessary because only one of them contains some idea and another one is well-known optimization or oppositely an obvious realization task and could be removed.
•  » » 4 years ago, # ^ |   +55 Yes, I agree. It will be fixed somehow.
•  » » 4 years ago, # ^ |   +22 Or they can be given scores according to their difficulty. It seems really unfair to give 70-80% of score to the easier part (which is mostly about to brute-force) and remaining to the harder one.Like, for today's G, it should be like 750 for G1 and 2750 for G2.
 » 4 years ago, # |   +21 Problem D is similar to this problem from cookoff: link
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Yeah, D is a very known problem
•  » » 4 years ago, # ^ |   0 But they were different. I can tell you one more similar (but that too differs from the problem D). https://codeforces.com/problemset/problem/382/C
 » 4 years ago, # |   +103 I don't think the solution of G1 & G2 is strongly related, not even close.G1 can be solved by simple mask DP, but G2 is completely different (although it's still DP).The scoring distribution for prob.G is totally a joke. G1 is too easy, and G2 deserves a higher score!
•  » » 4 years ago, # ^ | ← Rev. 2 →   +12 what if, G2 Pass, G1 Fail.Like jtnydv25 solutions.
•  » » 4 years ago, # ^ |   +34 I agree. I think it would be more reasonable to award 2000 points for G1 and 1500 points for G2, or maybe even the other way around (1500 for G1, 2000 for G2).
 » 4 years ago, # | ← Rev. 2 →   +40 G1 can be done in $O(g*2^n)$ or even $O(g*T*2^n)$ with an obvious solution,those who read G1 first may get massive score which is unfair to those who read ABC first ...
•  » » 4 years ago, # ^ |   0 Lol, what's your problem, start reading with G1 too ....
•  » » 4 years ago, # ^ |   0 I had really easy dp With O(n^4*m) Witch has also had c=1/16
 » 4 years ago, # |   0 I solved C1 using multiset, but unable to see the pattern for C2. Any hint ?
•  » » 4 years ago, # ^ |   +9 since time was never greater than 100 u can use frequency array to store the occurrence of time till i and now when you want to fail someone just start with the largest time
 » 4 years ago, # |   +8 How to solve G2??
 » 4 years ago, # | ← Rev. 2 →   +42 I don't think the order of the problems is good.Because G1 can be solved by simple mask DP,and F can be solved in O(2^26).I think F and G1 are even easier than problem D and E because problem D and E have more details to notice.And the scores of F and G1 are just the jokes.
 » 4 years ago, # |   +37 I submitted an incorrect solution to both G1 and G2 initially. G1 passed the pretests but G2 didn't. I fixed the solution and resubmitted only in G2. G1 now failed systests, but I am pretty sure that the solution I have already submitted for G2 should work for G1 as well.I think problems with subtasks create unnecessary complications in such contests. Also, its really difficult to find a fair point distribution.
•  » » 4 years ago, # ^ |   -21 Well, your situation has nothing to do with point distribution or anything. You just did something stupid :)
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +24 Thank you for opening my eyes :)
•  » » » 3 years ago, # ^ |   0 :D
 » 4 years ago, # | ← Rev. 3 →   +37 F tests are so weak. 1 2 1 1 5 1 1 6 1 1 Can kill many solutions.
 » 4 years ago, # |   0 Hi, when i read problem C2 for the first time I didn't see the small limit for the times and I implemented a solution with a Treap but I got TLE, why is that? Is the limit for N too large for a treap?Here is my code
•  » » 4 years ago, # ^ |   +3 I solved it with a treap: 55768688
•  » » » 4 years ago, # ^ |   0 Interesting, the way you generate the random numbers is better somehow?
•  » » » » 4 years ago, # ^ |   0 It shouldn't be that much better. I'm just directly using the output of an std::mt19937_64 seeded from a bunch of sources while you're using std::mt19937 and std::uniform_int_distribution. It could be that std::uniform_int_distribution is slow or that Visual C++ is faster than G++.
•  » » » » » 4 years ago, # ^ |   +1 Mmmm, I will try it with this. But i was expecting solved the problem with Treap :cAnyway, thank you so much!
 » 4 years ago, # |   +82 Wow, another implementationforces round, so cool (no).
 » 4 years ago, # | ← Rev. 3 →   0 For problem D:TLE CodeAC CodeThe only difference is a line with "break" to avoid unnecessary O(n^2) operations and getting overall O(n log n). But i just want to say i was unable to notice this fail because of really weak pretests, because it was accepted during contest...
•  » » 4 years ago, # ^ |   0 I implemented an O(n^2) solution for small values of n and a different solution for larger values of n (taking the most common difference between consecutive elements after sorting). During testing, I set it to always use the O(n^2) algorithm, but because I'm an idiot, I forgot to change the code back before submitting it and it passed the pretests. Of course, I didn't notice this until system testing. I would have probably been stuck on TC 21 though even if my solution failed the pretests since my solution for large inputs had a bug.
 » 4 years ago, # |   +7
 » 4 years ago, # | ← Rev. 3 →   0 My solution to A had a misplaced semicolon after an if condition and it passed all the pretests. It also passed 40 tests before WA during system testing. link https://codeforces.com/contest/1185/submission/55757491 I don't know whether I should feel amused or sorry for myself :( I need to indent my code properly.
•  » » 4 years ago, # ^ | ← Rev. 3 →   -13 Какой же ты быдло кодер
•  » » 4 years ago, # ^ |   0 You should turn up your compiler warnings. Visual C++ outputted this when I compiled your code: warning C4390: ';': empty controlled statement found; is this the intent?
•  » » » 4 years ago, # ^ |   0 Thanks, I was using Code: blocks IDE, I don't know if it has an option for that. I will try Visual C++, I have been wanting to change my IDE for some time now.
 » 4 years ago, # |   0 Давайте поговорим серьезно ( я не хотел никого обидеть не надо минусить) раунд состоял из достаточно легких задач для див 2, но их было много, вроде бы компенсировали, но зачем делать контест 2 часа 15 минут ??? Let's talk seriously (I didn’t want to offend anyone, we shouldn’t offend) the round consisted of enough easy tasks for div 2, but there were a lot of them, it seemed to be compensated, but why make a contest 2 hours 15 minutes ???
•  » » 4 years ago, # ^ |   0 Do you mean we should give more or less time?
•  » » » 4 years ago, # ^ |   0 Less time )
 » 4 years ago, # |   -34 I am user Ankit211999 and my ratings for the contest #568 Div 2 had been deducted due to the coincidence of submission Ankit211999/55756528 with kotlin_hero987/55756305. Actually, I used ideone and I didn't knew that its use was prohibited. And the submission which matched was of Problem 118A which is a basic problem and I solved two more problems after that if the submissions would have matched it would be of all the three problems. It might be the case that the style of writing code of both the coders for that basic problem might be same. I worked hard for solving those problems please return my ratings for that contest. It will not happen again!
•  » » 4 years ago, # ^ |   -24 Well, since you said it will not happen again, we'll reconsider.
 » 4 years ago, # |   -20 C2 was more difficult than D,E,G1
 » 4 years ago, # |   -50 My verdict was skipped because of similarities with someone else's code but it could be coincidence because our style of writing code could be same. I worked hard for solving those problems please return my ratings for this contest. I will try hard to make sure it won't happen again.
•  » » 4 years ago, # ^ |   +90 It is not a style, it is the copied code:
•  » » » 4 years ago, # ^ |   -80 Yes.I have noticed the thing. there is a community belongs in our university. ZahinAwosaf is my team mate. He coded in notepad.pw and mistakenly uploaded it to online. There is a notification came to my pc and whenever I checked it..I was coping my code to upload it on my codeforces ide for submission. But whenever I wanted to submit it on my github account I have copied the wrong one(ZahinAwosaf's Code). I haven't noticed the thing as the simulation is pretty much similar and switch to next one. Even I also solved this code earlier. But due to that reason, it happens. You can impose penalty for me. I request you to give his points he deserved.
•  » » » » 4 years ago, # ^ |   +27 How did the variable names change then? xD
•  » » » 4 years ago, # ^ |   +12 Wouldn't it make more sense to keep them in the contest and let their rating drop
•  » » 4 years ago, # ^ |   -123 Indians!
•  » » » 4 years ago, # ^ |   +64 Dude his profile say he is from Bangladesh.Get your facts corrected before making any assumption.
•  » » » 4 years ago, # ^ |   +5 Trump Supporter btw you are from Mexico strangeee....
•  » » » 4 years ago, # ^ |   +3 Firstly look at your self dude
 » 4 years ago, # | ← Rev. 2 →   +8 Is there a simpler solution than treap for C2 if $t_i \leq 100$ condition is not present?
•  » » 4 years ago, # ^ |   +25 I used binary search on Segment Tree (works for any ti). Wouldn't say its a simple one though.
•  » » 4 years ago, # ^ |   0 I think you can use a BIT
•  » » 4 years ago, # ^ |   0 I used a treap, but another solution (in hindsight) is to coordinate-compress the items, then run a binary search on BIT for O(N log^2 N).
•  » » » 4 years ago, # ^ |   0 Can you please explain your solution. It will be helpful for me. Though treap is new for me. Btw Thanks in advance xD. :)
•  » » » » 4 years ago, # ^ |   +1 I will explain both:TreapA treap is just an implementation of a balanced binary search tree. What we will do is have a BBST that can support insertion and another special operation for this contest, call it search. This operation takes a parameter k, and determines the number of elements in the BBST that we can 'take' such that their sum is smaller than or equal to k. The implementation of this is rather simple: if the current node we are processing has a sum smaller than k, we can take the whole node. We take smallest elements first, in order to maximize number of elements taken. Then, we continually add elements to the BBST, and then perform a search on $M - v$, where v is the value of the element we are considering. Full solutionCoord compress + Bsearch BITIf we coordinate compress the components, then each element in our BIT is simply either 0 or the value of the element. In the same way, we want the largest $i$ such that the sum of the first $i$ elements is less than $M - v$. To find this, we can binary search, and use the BIT to get the sum of the first $i$ elements. Frankly im way too lazy to code the above, and this specific problem has a better solution because of the lax constraints. If you have any more questions dont hesitate to ask.
 » 4 years ago, # | ← Rev. 2 →   +25 Div.3 Rated for Blue and Purple ! very good contest .
 » 4 years ago, # |   +3 Editorials?
 » 4 years ago, # |   0 What is test case 30 for C2?
 » 4 years ago, # | ← Rev. 2 →   0 I think that the contest is perfectly fine for div 2. Perhaps a small issue was a point value for G2. It may be solved by giving to that subtask 3500 pts (and not treat this as a subtask or let G have 6250 pts in total). I believe that this affected not so many div2 participants (most of the comments to make it div3 came from unofficial contestants...).Perhaps a bigger, but unnoticed concern were weak tests for task F.Please take into account an objective level of difficulty. Reading all the tasks, familiarity with bitmasks dp, etc. — these are all the factors of competitive programming. Given that, I think that the difficulty of the tasks compared to the "regular" div2 rounds was the following: A B B C C D E D FWhich in my opinion makes it also a decent, regular div 2 round.
 » 4 years ago, # |   +3 Can anyone please explain how to solve c2? It will be helpful for me. Thanks in advance xD. :)
•  » » 4 years ago, # ^ |   0 https://codeforces.com/contest/1185/submission/55759892I've personally tried to do it using multiset. If you've done C1 by summing up every $a_i$ and if it crosses M , you declare an array $b_i$ that has all the elements up to (and not including) $a_i$ , you sort that array, and then you start from the biggest value to the lowest value and see how many students do you have to kick off, and you print that value. The problem with this task in C2 is time constraints. Sorting takes O(NlogN) and the $b$ array can be massive.The idea is to use multiset, because multiset is like a set except you can have multiple values (and $a$ can have multiple values), and a property of multiset and set (correct me if I'm wrong) is that they're always sorted, and they sort things in logN time.So when you insert each "student time" into the multiset, it will get automatically sorted in logN time, so when the sum exceeds M, you can just use the highest values in the multiset and find the amount of students needed to be kicked off.I'm not entirely sure why my code got TLE : https://codeforces.com/contest/1185/submission/55785240But it worked for Radewoosh: https://codeforces.com/contest/1185/submission/55759936Probably because he deletes something from his multiset, I'll debug it tomorrow.
•  » » » 4 years ago, # ^ |   +1 In the worse case, t[i] == M for all i which means every student will only pass if everyone in front of that student failed. This makes your solution O(n^2) since for every student you iterate through the entire set of previous students.Radewoosh's solution works in time because he observed that if the sum of the times for the students in the multiset exceeds M, we would always have to kick someone out in order for the later students to have any possibility of finishing. Therefore, we can kick out students until the total time of the students in the multiset is less than M.Since the total time of the students in the set is now always less than M, that time plus the time of the current student has to be less than 100 over M. Kicking out a student decreases the time by at least 1, so we only have to kick out less than 100 students in addition to the students that we've determined will always be kicked out.
•  » » » » 4 years ago, # ^ |   0 Thanks, I understand it now but why does he delete the second biggest (it-- makes it second biggest right?) and not the biggest in the set ?
•  » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 setel.end() points to the imaginary element right after the last element in the set, so decrementing it results in the largest element.
•  » » » » » » 4 years ago, # ^ |   0 it=setel.rbegin() is the same as it=setel.end() it-- ?
•  » » » » » » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes, except that setel.rbegin() is a reverse iterator which I didn't previously know can't be easily converted into a forward iterator that std::set::erase accepts. So I was wrong and the easiest way here is to decrement setel.end().
 » 4 years ago, # |   +3 Can anyone tell me how to solve G2?
•  » » 4 years ago, # ^ | ← Rev. 4 →   0 I don't think this is the optimal solution.First calculate $H[i][j][k][sum]$ , this is defined as the number of subsets with $i$ songs of type $1$, $j$ of type $2$ etc and with length sum equal to $sum$.We can store this in a compressed 1d array of size Q1*Q2*Q3*T where Qi is the number of songs of type i.Once we have these numbers we just have to iterate over all values $H[i][j][k][T]$ and add $H[i][j][k][T]$ multiplied by an appropriate coefficient $F[i][j][k][end]$. which tells us given a specific subset of songs with those quantities how many suitable rearrangements exist, that finish with a song of type $end$. ( So for each $H[i][j][k][T]$ we add the product by the three $F[i][j][k][end]$ corresponding to the $3$ values of $end$.These coefficients can be calculated in time $3*n^ 3$ via a normal dp.Be careful when calculating the $H[i][j][k][sum]$, to make it faster process all songs of type 1 first, then type 2 etc and only fill the entries $H[i][j][k][sum]$ where the values of $i,j,k$ are less than the current numbers of processed songs.
•  » » » 4 years ago, # ^ |   0 How do you calculate the H values while also making sure that you don't chose the same element more than once.
•  » » » » 4 years ago, # ^ |   0 To do this transverse over the values i,j,k in decreasing order instead of increasing order.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +8 I guess my solution is not the official solution since it requires FFT:First, let $dp(i)(j)(k)$ be the number of ways that has $i$ songs of genre $k$ and the total length is $j$ minutes. It can be calculated in $O(n^2T)$. Then, we enumerate how many songs we are going to put in the playlist for each genre (in the worst case it's a loop that runs 17*17*16 times), so we are left to calculate $\sum _{i+j+k=T} dp(cnt1)(i)(0)*dp(cnt2)(j)(1)*dp(cnt3)(k)(2)$, and this is a simple fft application. To sum up, the complexity is $O(n^3TlogT)$, but in fact, it's just 4624 times of fft of size 2500, and my solution runs in 4.5s.
•  » » » 4 years ago, # ^ |   -8 Well, to be honest, the complexity of my solution is $O(n^3T^2)$, but my solution suns in 733ms.55809647
•  » » 4 years ago, # ^ |   +8 I used some sort of meet in the middle approach (after the contest).I computed $dp12[N][i][j][T]$ = how many ways to select $i$ songs from the first genre and $j$ songs from the second genre so the total sum of the durations is exactly $T$, using some of the items in range $0...N$. In practice, we can ignore the first dimension, so the dp will become $dp12[i][j][T]$. The time complexity will still be $O(N^3*T)$.We also compute $dp3[i][T]$ = how many ways to select $i$ songs from the third genre totalling $T$ seconds, in a similar way in $O(N^2*T)$.In the above dp's we ignore the order of the songs, so we will also compute another dp $perm[i][j][k]$ = how many ways to arrange $i$ songs from the first genre, $j$ songs from the second genre and $k$ songs from the third genre, so that there are no consecutive songs from the same genre. The time complexity for this will be $O(N^3)$.Now the answer to the problem will be $\sum_{i,j,k \le N, t \le T}dp12[i][j][t] * dp3[k][T-t] * perm[i][j][k]$.The final complexity will be $O(N^3*T)$ and the constant should be ok, since $i+j+k \le N$ will result in a $1/27$ constant. I got AC with 120 ms or something like that.
 » 4 years ago, # |   +9 When you realized that C2 had a low score after you solved it, even D had a higher score.
 » 4 years ago, # | ← Rev. 2 →   -31 How is that possible?The complexity of my solution to problem G2 is $O(T^2n^3)$, and there's a lot of mod, but I got an "Accepted".Could anyone give me an answer? Or is it just because the computer runs too fast?My solution here:55809647
•  » » 4 years ago, # ^ |   +8 I had the same idea with you :v I think it was accepted because lots of limitations you wrote. For ex, i + j + k <= n => for (i, j, k) will cost O(...) <= O(n^3 / 27) < O(n^2 * 2)
•  » » » 4 years ago, # ^ |   0 Well, I recalculated my complexity, it is $O\left(\dfrac{T^2n^3}{108}\right)$ instead of $O(T^2n^3)$, about $7\times 10^9$.I think it was accepted because of this: if(f1[i][t1]==0)continue; ... if(f2[j][t2]==0)continue; And also, the complexity of "%" is only $O\left(\dfrac{T^2n^2}{18}\right)$
 » 4 years ago, # |   -8 Can someone help me with my solution. 55778971 I am getting a Wrong Answer on Test 13.
 » 4 years ago, # | ← Rev. 3 →   +1 What is wrong with the while conditon? The value of j printed after while loop is 104 in codeforces IDE.It works fine in dev. [submission:https://codeforces.com/contest/1185/submission/55793048]
 » 4 years ago, # |   +9 My submission for B in Python WA-d during contest but got accepted after the contest.During contest: https://codeforces.com/contest/1185/submission/55760801 After the contest: https://codeforces.com/contest/1185/submission/55812461I wasted an hour trying to find a bug and ended up performing very poorly. I think it will be fair if my rating change is reconsidered.Also, can you please look into this and let us know why this incident occurred? Compiler seems to behave non-deterministically: here's the same solution, but WA on a different test: https://codeforces.com/contest/1185/submission/55812449
•  » » 4 years ago, # ^ |   +3 You can see, your answer is empty after some iterations. It seems that the thread exited so the line is empty. Maybe the thread is killed because the computation resource is depleted? That's my guess.
•  » » » 4 years ago, # ^ |   0 I was also guessing that it is related to threads, but I'm not really sure how exactly that could happen. What exactly do you mean by computation resource?I don't want to use threads but I don't really know how to increase the recursion limit without them. The inability to change it (without using threads) is really annoying as it renders Python useless for many problems.
•  » » » » 4 years ago, # ^ |   0 computation resource, I mean many submissions are judged the same time, they are competing for resource. Just a guess.Python is just for quick solutions for easy problems. Hard problems needs faster language.
•  » » » » » 4 years ago, # ^ |   0 This is a pretty simple problem and my solution is linear. It seems like the platform should support it.
 » 4 years ago, # |   0 How to solve G1?
•  » » 4 years ago, # ^ | ← Rev. 2 →   +3 Straight forward bitmask DP. dp[mask][prv] gives the number of ways to arrange a subset of the given songs where prv is the genre of the last used song. Complexity $O(n*2^n)$
•  » » » 4 years ago, # ^ |   +3 $O(n*2^n)$
•  » » » » 4 years ago, # ^ |   0 My bad. Thanks
 » 4 years ago, # | ← Rev. 2 →   +9 When will the problem setters upload the editorials?
 » 4 years ago, # |   0 Great round, guys. So, will you post the solutions?
 » 4 years ago, # |   0 Can someone please help with my solution of problem C2. It's getting TLE on TC13.https://codeforces.com/contest/1185/submission/55818757I have used a multiset and every element is inserted and deleted from the multiset only once.So the time complexity should be O(nlog(n))any help would be appreciated.
•  » » 4 years ago, # ^ | ← Rev. 2 →   +1 For multisets, erase eliminates all the elements with value == parameter, instead of just one element which is what I guess you were trying to do. You should change erase(largest) to erase(s.begin()).
 » 4 years ago, # |   0 Can anyone help me find fault in the concept of my implementation for C2? linkI used the priority queue to get the maximum element which hasn't been extracted yet by previous elements. I am storing the sum of time taken by the just previous element. If prev_sum + input[i] <= m, the answer will remain the same as the previous element. Otherwise, I will extract elements from the priority queue and subtract it from my current sum till it becomes less than or equal to m and update the prev_sum to curr_sum.Please ignore the commented out code. Thanks!
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 check for: 6 15 1 2 3 4 10 5for 6th student answer is 1 (remove 5th student).
•  » » 4 years ago, # ^ |   0 your logic is OK , but here that array is not always sorted. So , it is possible that answer to ith term can be less than (i-1)th term. example:- 4 10 3 4 10 2See my soln i also used priority_queue. https://codeforces.com/contest/1185/submission/55817685i used two priority queues second one in ascending order. I think it will even work for ti<=10^5
•  » » » 4 years ago, # ^ |   +1 Thanks for identifying the mistake in my implementation. I scrolled through your code and got some idea. You should check out the implementation through multiset too. It is quite simple to follow.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 Your Code gives wrong answer for test case: 3 100 50 60 41 Your code gives 0 1 2 But it should be 0 1 1. Still your solution got accepted. Weak test cases maybe.
•  » » » » 4 years ago, # ^ |   +1 You just hacked my code. Thanks a lot man. I rechecked my code and improved it. https://codeforces.com/contest/1185/submission/55826242 Actually i thought about that case while submitting but since it passed all test cases i left.
 » 4 years ago, # |   +5 I think the score problem is totally wrong. C2&G2 should have more score.
 » 4 years ago, # |   +1 Please provide the editorials.
 » 4 years ago, # |   -8 Really good problems.Isn't it? Hope there will be more rounds like this(easy&many problems).
 » 4 years ago, # |   +11 any editorials?
 » 4 years ago, # |   +4 Editorial coming? :)
 » 4 years ago, # |   +1 Could anybody show me a solution for E?Thanks in advance
•  » » 4 years ago, # ^ |   +1
 » 4 years ago, # |   0 For problem E can anyone expalin me these two test cases test case 1 — 3 5..b..aaaaa..b..why their output is (NO) and test case 2-bcccthankyou.
•  » » 4 years ago, # ^ | ← Rev. 3 →   0 First case :in the question it is written clearly that first 'a' is written then 'b' which means that 'b' can overwrite 'a' but not vice versa. Hence answer is NOSecond:ans is NO because snake('c') cannot bend
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 But the second test case output isYES31 1 1 21 1 1 22 1 2 2... I realy didnt get this one suppose (A) overwrite (B) and then (B) overwrite (A) but then why we overwrite (C) with itself when (C) was there on that position???
•  » » » » 4 years ago, # ^ |   0 'a' cannot overwrite 'b'In question snakes are in order that first 'a' is written then 'b' then 'c', which implies a character can only be overwritten by a character after it. i.e 'e' can be over written by any character from 'f' to 'z' and cannot be overwritten by character 'a' to 'd'. Also there is only one snake of a character, so it cannot possibly overwrite itself as it cannot bend .But the second test case output isYES.....i guess you wanted to paste the sample test case b cb c ( which has the the above solution of 'YES') but you pastedb cc c(whose solution is 'NO')
 » 4 years ago, # |   0 when will the editorials come?
 » 4 years ago, # | ← Rev. 2 →   0 [deleted]
 » 4 years ago, # |   0 Now editorials are available.
 » 4 years ago, # |   +15 I think the solution which Radewoosh wrote for problem D is incorrect. It is showing -1 for this case: 5 2 4 5 6 8 The answer should be 3. :/
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 Yes the answer is 3. Earlier I thought that the array consists of 6 elements.
•  » » » 4 years ago, # ^ |   +5 How? If we delete 3rd element, it's a arithmetic sequence.
 » 4 years ago, # |   0 System tests for task D are so weak...This submission is AC: 55860779But it couldn't pass a few different tests:1)43 5 5 72)52 3 4 6 83)52 5 8 10 13