By AdvancerMan, history, 5 months ago, ,

Hello Codeforces!

We're glad to invite you to Codeforces Round #610 (Div. 2), which will be held on Dec/24/2019 17:35 (Moscow time). It will be rated for all participants with a rating below 2100. You will be given six problems and two hours to solve them.

The problems were invented and prepared by the team from ITMO University: Supermagzzz, Stepavly, AdvancerMan, unreal.eugene, MikeMirzayanov.

Special thanks to MikeMirzayanov for great systems Codeforces and Polygon and coordinating round preparation.

UPD1: Special thanks to the ITMO University testers team: Nebuchadnezzar, Alexvsalex, Darui99, golikovnik, sharepoLOVEDDD, Mr.Hakimov, zergey.gad, MeowMr, Ilya-bar, 1ncendiary

There is an interactive problem in the round. You can read the guide for interactive problems here.

UPD2: Scoring: 500 — (500 — 1000) — 1750 — 2500 — 2500

We hope you will enjoy the problems. Good luck, wish you a high rating!

UPD3: Congratulations to the winners!

Editorial will be published soon.

UPD4: Editorial is out!

• +157

 » 5 months ago, # |   0 hoping good contest :D
 » 5 months ago, # |   +1 Any subtasks?
•  » » 5 months ago, # ^ |   -184 This is an online contest so there will be no subtasks
•  » » » 5 months ago, # ^ |   -57 I think you meant: This is an Official Codeforces Round so there will be no subtasks
•  » » » 5 months ago, # ^ |   -8 He seemed to mistake subtasks of problems to subtasks of pretests. Why is everybody going so hard on him lmao?
 » 5 months ago, # |   +286 I am very worried about the fact that Mirzayanov’s pawns can hold two contests a month, while the rest are waiting in line for six months
•  » » 5 months ago, # ^ |   +143 New pawn of sorry_marymarine
 » 5 months ago, # |   -35 Hello everyone — Good luck for all I hope I can become a Candidate Master after contest
•  » » 5 months ago, # ^ |   +3 I am sure you will, brother. ALL THE BEST!
 » 5 months ago, # |   -149 Before round:Round is rated for Div.2 participantsAfter round:UNRATED!Sad story......
•  » » 5 months ago, # ^ |   +26 that is a very bad joke.
 » 5 months ago, # |   +15 Finally there is an interactive problem after 9 rounds ! :D
 » 5 months ago, # | ← Rev. 2 →   +58 hope interactive problem is not a binary search. pleaaase
•  » » 5 months ago, # ^ |   -21 It can be a geometry problem too.
•  » » 5 months ago, # ^ |   -29 or a probability one
 » 5 months ago, # |   +1 are there interactive problems in ICPC contests !
•  » » 5 months ago, # ^ |   +18 Yes there are!!!
 » 5 months ago, # | ← Rev. 3 →   +16 hope for short statements like the last round !
 » 5 months ago, # |   +3 it's look like interesting contest
 » 5 months ago, # |   -21 I hope this contest should be good.
 » 5 months ago, # |   -24 We can see interactive problem in Codeforces after a long time.so everyone should learn what is interactive problem and be ready for contest. All the best and wish u high rating
 » 5 months ago, # |   -13 Can someone please explain what is an interactive problem and whats the difference between and regular problem and an interactive one?? Bcuz i did not really understand the meaning by reading the blog from MikeMirzayanov :) tnx for your help!
•  » » 5 months ago, # ^ |   +2 Interactive problems(over simplified): the input isn't given all at once, or it's in a "Q&A" style.
 » 5 months ago, # |   -23 Which problem will be Interactive ?
 » 5 months ago, # |   -20 I just finished my graduate entrance exam.It is so excited that I can join contest now.
 » 5 months ago, # |   -25 Exciting for contest after semester exam.
 » 5 months ago, # |   -11 Interactive problem and 20 questions ..
 » 5 months ago, # |   0 can somebody help me with interactive problems
•  » » 5 months ago, # ^ |   0 you give the jury some numbers and it will give some information about that. then you should use this information for next question or guess the answer.
 » 5 months ago, # |   0 What interactive problem will be A,B,C?
•  » » 5 months ago, # ^ |   0 Unlikely
 » 5 months ago, # |   +115 I bet that 80% participants of this contest has no girlfriend. It's Christmas Eve!! Go hang out with friends!!
•  » » 5 months ago, # ^ |   0 Code with gf =)))
•  » » 5 months ago, # ^ |   0 Why you don't go !?
•  » » 5 months ago, # ^ |   +7 I guess that 100% is much more accurate!!!
•  » » » 5 months ago, # ^ |   +3 for sure 1% of this 10000 person have girlfriend.Don't you think?
•  » » » » 5 months ago, # ^ |   +6 Well that sounds true but I'm confident enough they are not more than 5%!
•  » » » » » 5 months ago, # ^ |   +3 Me either.
•  » » 5 months ago, # ^ |   +23 Yesterday I was broken up with her. :< Sad ChristMas
•  » » » 5 months ago, # ^ |   +3 Pressing F for you
 » 5 months ago, # | ← Rev. 2 →   -6 [deleted]
 » 5 months ago, # |   0 Can anyone provide link to the mirror website m1/m2/m3 I am not sure where to find it
•  » » 5 months ago, # ^ |   0 They will put it just before the contest I think.
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8
•  » » » 5 months ago, # ^ |   0 Tnx.
•  » » » 5 months ago, # ^ |   0 Thanks
 » 5 months ago, # |   +23 Merry Christmas!!!
 » 5 months ago, # | ← Rev. 3 →   -21 Good contest
 » 5 months ago, # |   -9 feeling orz................
 » 5 months ago, # |   +50 Problem statements are longer than my hair.
 » 5 months ago, # |   +5 Hope for strong pretests. Merry Christmas!!
 » 5 months ago, # |   0 What is test 6 for D?
 » 5 months ago, # |   0 What is the test case 2 for Problem B.
 » 5 months ago, # |   +2 Am I the only one who over-killed C with segment tree and stuff and later realize it could have been done simply:((
•  » » 5 months ago, # ^ |   +5 Am I the only one who doesn't know how to do C?
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 I think C cab be solved by Sorting by overriding the comparator function. if we create array and sort this such that after sorting wrt mandatory time i.e. by giving most preference to the problem with least mandatory_time. Arr[i] holds info about problem (actual index of the problem, it's mandatory time and it's easy/hard). and putting some constrain on current time and total time while going through this sorted array can solve this.I didn't got time to submit. I will do it after system_testing
 » 5 months ago, # | ← Rev. 5 →   +29 I think problem C has some problemProblem C- In statement: 2 <= n <= 1e5Whereas just changing maxn=1e5+5 to 2e5+5 changed an RTE to ACThis should be rejudged with proper input files and first ac submission should be counted.UPD5: sorry seems like, I've missed the announcement
•  » » 5 months ago, # ^ |   -7 It's written 2e5 in C statement
•  » » » 5 months ago, # ^ |   +11 It was 1e5 at the start of the round and updated during the round.
 » 5 months ago, # |   0 How to solve D?
•  » » 5 months ago, # ^ |   +30 Solution of D : You can get length of required string and number of 'b' by asking two queries. String of 300 a's will give you value = 300 — n + no. of b's. String of 300 b's will give you value = 300 — n + no. of a's. Plug them to get above length and no of b's. Take a string of n a's and start locking the indexes in order by using provided answer and no. of b's left to be selected.
•  » » » 5 months ago, # ^ |   +11 Just curious: Are you intentionally dropping your ratings?
•  » » » » 5 months ago, # ^ |   -8 No.
 » 5 months ago, # |   +32 My approach for D, making at most $n+2$ queries: 67539477First make two queries, one with 300 A's and the second with 300 B's to figure how many A's and B's are in the string, and therefore its length.Notice that the edit distance from a string of length $k$ with all of the A's already placed is $n-k$ if and only if between no two A's we have more B's than in the hidden string (as then we could not make only insert-operations).Using this, add B's before the first A until the edit distance doesn't decrease, then place the first A and repeat. Thus after the $i$th operation, we know a prefix of length $i$ of the hidden string. Thus after $n-1$ operations we know the entire string (as we know character counts). Including the first two queries, we make at most $n+2$ queries in total.
•  » » 5 months ago, # ^ |   +30 To get number of A's and B's you can also query a single "a" first, and then an all "b" string of length equal to answer of first query.
•  » » » 5 months ago, # ^ |   0 I think I did this, but I'm getting WA on Q5 with the comment:Do you know what is wrong?My solution is failing with input abababababababab, and the error message iswrong answer Line [name=s_17] equals to "", doesn't correspond to pattern "[ab]{1,300}"However, when I tested locally it seems to work, and I also added asserts to check that I never output empty strings. My code is below.http://codeforces.com/contest/1282/submission/67561919Thank you!
•  » » » » 5 months ago, # ^ |   0 I couldn't solve the problem, but I think you should look over here probably. This comment
•  » » » » 5 months ago, # ^ |   0 Hey simp1eton, Could you tell what the problem was. I am receiving the same verdict as you mentioned. I used 300 a's and 300 b's to find the length. Here is my submission 67569644
•  » » » » » 5 months ago, # ^ |   0 I assumed wrongly how edit distance is computed. I think if your program throws and exits for any reason, the checker says that your program outputs an empty string
 » 5 months ago, # |   0 Can anyone help me why I am getting wrong answer for Div2 B1??? My approach- Sort the array. Check if you can buy all items till index 'i' supposing that you got i-1 item for free. 67533371
•  » » 5 months ago, # ^ |   0 Do you consider the case when you purchase the first item itself, and not for free?
•  » » » 5 months ago, # ^ |   0 YES
•  » » 5 months ago, # ^ | ← Rev. 3 →   0 1 6 4 2 1 1 1 1 2 2 Your program outputs 4 for this, but should be 6
•  » » » 5 months ago, # ^ |   0 Can you please clarify your test case what are you taking?
•  » » » » 5 months ago, # ^ | ← Rev. 3 →   0 The test case is as follows -16 4 21 1 1 1 2 2
•  » » » » » 5 months ago, # ^ | ← Rev. 2 →   0 Answer should be 4 right???
•  » » » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 No, you can buy all, choose the 2nd 1, the 4th 1 and the 6th 2Update — I think you somewhere forgot to do i += 2
•  » » » » » » » 5 months ago, # ^ |   0 please explain solution of B1 i am beginner here
•  » » » » » » » » 5 months ago, # ^ |   0 Sure, for the case of $k = 2$ (which is easier actually, since you need to solve the problem in $O(n)$ time); first of all, sort the array on the basis of prices. Now try to understand the points mentioned here as to why they're true. Now, going ahead, since k is just 2, you either choose the first one and then keep taking 1 on 1 as the offer; or you take all goods on offer, the answer is the max of the two.
•  » » » » » » 5 months ago, # ^ |   +1 with two 1's can take other two other 1's and with one '2' can take other '2', in all 6 while spending 1+1+2=4.
•  » » » 5 months ago, # ^ |   +8 Got it. We can apply the offer again and again. I thought that we can apply it only once. Wasted an hour on this.
•  » » » » 5 months ago, # ^ |   +4 Oh shit dude (cries in corner)
•  » » 5 months ago, # ^ |   0 what is the hack of B2??
•  » » » 5 months ago, # ^ |   +3 O(k*k) Algorithms will not work. While there were no tests as such in Pretests.
 » 5 months ago, # |   0 how to solve B2?
•  » » 5 months ago, # ^ |   0 first sort all items. then you make a list with size k that ith element is the cost if you take i starting elements alone. for each item(after k initial items) you update the list.
•  » » » 5 months ago, # ^ |   0 can you please elaborate more?
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +2 Sort the array first.Try to understand the following facts - If not choosing to use the offers, you should buy only the first few(< k) items, and not from any later part of array. Once you buy some or all of the first k items, you would only use the offer now, and no individual buyings.
•  » » » » » 5 months ago, # ^ |   0 thanks a lot.
 » 5 months ago, # |   0 Can someone please explain why I got TLE in the problem Div 2-B2 ? Here is the link to my solution.Solution
•  » » 5 months ago, # ^ |   +1 Because PriorityQueue.remove() function has O(n) complexity instead of O(log n) in Java
•  » » » 5 months ago, # ^ |   0 Got it thanks a lot. There was actually no need of priority queue. I just removed it and got the solution accepted.
 » 5 months ago, # |   +4 16 17 2 60 0 1 0 0 17 6 3 7 10 12Why should that give us 1 as an output? (Problem C-petya and exam) can someone help me?
•  » » 5 months ago, # ^ |   +2 At t = 2, you can solve any one of the non mandatory easy problems
•  » » » 5 months ago, # ^ |   +4 oh thank you man, I've understood it now
 » 5 months ago, # |   +33 Ultra fast system testing
 » 5 months ago, # | ← Rev. 2 →   -59 Ok codeforces
•  » » 5 months ago, # ^ |   +5 *your worst
•  » » 5 months ago, # ^ |   0 Hey man, your contribution is already -26. So I strongly recommend you think twice before you make a comment .
•  » » 5 months ago, # ^ |   0 I agree tbh. The problem statements are overcomplicated and the score distribution is really not balanced. Who decided to put D = E?
 » 5 months ago, # |   +27 E was a very nice problem. Among the best I've seen in a while. Too bad I had a silly bug in my code during the contest.D was also nice. Hats off to the authors.
 » 5 months ago, # |   +1 One of the fastest one I've ever seen...
 » 5 months ago, # |   0 For problem B2, why are so many solutions getting TLE on test case 12 or 13?
 » 5 months ago, # |   +25 D&E are realy good problems! ABC — stupid idealess problems!
 » 5 months ago, # | ← Rev. 2 →   +73 Hello Codeforces, I didn't see the notification that the bounds for problem C were changed. As a result, I didn't notice the change for a long time. Would it be possible to unrate me? thanks! My first correct sub with wrong bounds: https://codeforces.com/contest/1282/submission/67543972 Changed to 2e5: https://codeforces.com/contest/1282/submission/67558110
•  » » 5 months ago, # ^ |   -103 No
•  » » 3 months ago, # ^ |   +8 Unrate :eric:
 » 5 months ago, # |   +14 Am I the only one who did B by handling $K >= \sqrt{N}$ and $K < \sqrt{N}$ differently?
•  » » 5 months ago, # ^ |   +8 Well, I was planning to do the same at first :D
 » 5 months ago, # | ← Rev. 14 →   +5 I'll post a screencast of the round within 12 hours. (I will also add those 5 minutes which I did not have enough to pass E).UPD I hope the screencast will be available tomorrow at 07:00(MSK) by this link in good qualityUPD2 It is available
 » 5 months ago, # |   +9 Approx 25% of all ACs of D ended up in fst, the edge case being bbbb...300 times. This was an obvious edge case and I do not get why you guys did not include it in pretests. Was this deliberate by any chance?
•  » » 5 months ago, # ^ | ← Rev. 2 →   +8 Fortunately, Tsypkokokokoko hacked my solution with this test case and I managed to correct my solutionCongratulations on your 1st rank, Tsypkokokokoko!
•  » » 5 months ago, # ^ |   0 Actually I do not understand what is the difference between bbbb… 8 times (as in test 4) and 300 times. What's more, I wonder why would anyone want to include the 300 constant in their program (and so, it's no longer an "Edge case")
•  » » » 5 months ago, # ^ |   0 Well I was checking your code and it seems the rand() part saved you. try printing just "a" in the beginning and you will know.
•  » » » » 5 months ago, # ^ |   0 Oh, that's like the weirdest thing that happened to me for the past 2 years on Codeforces :P If I print just "a" in the beginning (which I tried to do, submit #1...) I get TLE 4 (which is the first monochrome test). There are MANY such tests up to #67, so idk why those solutions make it that far...
•  » » » » » 5 months ago, # ^ |   0 Seem like you got really lucky :p
•  » » » » » » 5 months ago, # ^ |   0 More like time trouble :)With 5 minutes left, I couldn't figure out how to find |s| and I just made this leap of faith, hahaBtw, I was 110% sure this would fail the systests and even now I don't know why it passed (there were soooo many monochrome strings)
•  » » » 5 months ago, # ^ |   -15 My program uses aaa..aaa (301 times) as second query in this case and for some crazy reason it is not allowed. I would be very angry if this was an actual round for me, not the one where I do educational video.
•  » » » » 5 months ago, # ^ |   +26 Guess, it's time to rewrite this one :D https://codeforces.com/blog/entry/62744
•  » » » » » 5 months ago, # ^ |   -16 More like reread, and also the story with Golovanov399 and 22 vs 20. Yes, double standards.
•  » » » » » » 5 months ago, # ^ |   +25 Rereading this particular fragment would be enough I guess: Answer: Do you fucking read your questions? I like that "I can't solve the problem with operations in statement, can you provide better operations for me?"
•  » » » » » » » 5 months ago, # ^ |   0 Nope, this is not it. I didn't ask for a clarification. Also I'm not that mad to consider the problem bad because of small issue.
•  » » » » » » » » 5 months ago, # ^ |   +16 Well, you don't have to build so literal analogies. It's up to you to decide what conclusions you leave for yourself from this situation. I just suggest you to think why you call not allowing string(301, 'a') "crazy" and compare this to that sentence from your blog.
•  » » » » » » » » » 5 months ago, # ^ |   0 There is a clear divide between ranting about the problem during the contest in a clarification and ranting about the contest afterwards.Also I didn't call allowing crazy.And yes, I already did admit that there is a resemblance, what's the problem?
 » 5 months ago, # |   0 Test 67 for D?
•  » » 5 months ago, # ^ |   0 bbbbb....300 times
•  » » » 5 months ago, # ^ |   0 67542439 Can you help me with finding out what is wrong with this solution? It works with 5b's, and I don't see anything that would make it not work with 300 b's.
•  » » » » 5 months ago, # ^ |   0 your code is probably printing 301 characters somewhere.
•  » » » » » 5 months ago, # ^ |   0 Thanks, I figured it out, it was because if there was 300 a's or b's, my code would continue after getting a query of 0.
 » 5 months ago, # |   +52 Amazing system testing speed. Like
 » 5 months ago, # |   0 In problem C, I created 2 sets one to store hard problems mandatory time and the other to store easy problems mandatory time. Every time I check first problem in Easy problem + a and first problem in Hard problem + b and i take the one which Solved eailer. then I check if any problem should be solve in this time and I add it I only update the answer if the time at the end <= the total time of examWhy this idea is wrong ? 67550974
 » 5 months ago, # |   +47 Checker for D is incorrect. This solution https://codeforces.com/contest/1282/submission/67555058 still outputting things after getting 0 as response for the test "b" * 300, but I got incorrect hacking attempt on this one.Hack is here https://codeforces.com/contest/1282/hacks/603027
•  » » 5 months ago, # ^ |   -8 In the problem statement it says that on such cases the checker will give an "arbitrary" verdict, which can include Accepted (depending on how the checker is written).
 » 5 months ago, # |   0 Good evening everyone! Help me please understand what am I doing wrong on the second problem, so for the input (n = 4, p = 9, k = 2) and the numbers { 2, 3, 4, 5 } the expected output is 4, mine is 3. Thanks in advance!
•  » » 5 months ago, # ^ |   0 If you buy the 2nd good then it will cost you 3, and you will get the first one for free and you will be left with p = 9-3 = 6. Then just buy a good 4 for 5 and get good 3 for free. Hence finally, you have 4 goods.
•  » » 5 months ago, # ^ |   0 Offer can be used more than once. You can pick 3 and 5,you get 2 with 3 and 4 with 5 for free
•  » » » 5 months ago, # ^ |   0 Yeah, cool!
 » 5 months ago, # |   0 Can someone tell what's wrong in this solution of D? 67559495
 » 5 months ago, # |   +39 How come the pretests for D didn't include a single string with max length? It seems the longest string in the pretests had only 17 characters.
•  » » 5 months ago, # ^ |   -6 to add a little bit of suspense, I guess :)
 » 5 months ago, # |   +19 Can not understand why let $O(k^2)$ solution pass B2 pretest.
•  » » 5 months ago, # ^ |   +1 how to $O(k^2)$?
 » 5 months ago, # |   0 Hello. Please AdvancerMan could you help me understand why 67555899 got WA. The problem is that when I run locally the 5th case it returns the correct spell.Thanks in advance
•  » » 5 months ago, # ^ |   +11 This is your outputa 15 b 15 baaaaaaaaaaaaaaa 9 abaaaaaaaaaaaaaa 7 aabaaaaaaaaaaaaa 8 aaabaaaaaaaaaaaa 7 aaaabaaaaaaaaaaa 8 aaaaabaaaaaaaaaa 7 aaaaaabaaaaaaaaa 8 aaaaaaabaaaaaaaa 7 aaaaaaaabaaaaaaa 8 aaaaaaaaabaaaaaa 7 aaaaaaaaaabaaaaa 8 aaaaaaaaaaabaaaa 7 aaaaaaaaaaaabaaa 8 aaaaaaaaaaaaabaa 7 aaaaaaaaaaaaaaba 8 bbbbbbbbbbbbbbba 9 Check how you calculate the edit distance.
•  » » » 5 months ago, # ^ |   0 that is exactly the problem. I am calculating the edit distance in a wrong way.Thank you so much
 » 5 months ago, # |   0 still myself need lot of work to put on DP
 » 5 months ago, # |   +1 I didn't submit because i couldn't solve Div2-B1. And i couldn't solve B because I kept thinking offer had to be applied once. I really think the setter should have clearly mentioned that :'( . Looking forward to next contest
 » 5 months ago, # |   +5 can someone explain how to solve C?
 » 5 months ago, # | ← Rev. 2 →   +8 I am getting WA for Problem D.The checker says I printed an empty line (" ") which not acceptable , but my code doesn't print any such line.Here it it : My SubmissionThanks in advance!UPDATE : Resolved! :)
•  » » 5 months ago, # ^ |   +3 > If the number of spells exceeds limit (n+2, where n is the length of the spell s, which is unknown to you), you will get the Wrong Answer verdict.That could be the reason
•  » » » 5 months ago, # ^ |   0 Yup I did check for that. My code always prints n+2 strings , no more than that!
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 AdvancerMan can you please have a look? Thank you!UPDATE : Resolved! :)
•  » » » 5 months ago, # ^ |   +17 Your program prints no more than $n + 2$ strings but it doesn't print the correct answer to the first test as well. Your output for the first test: Codea 4 aa 3 aaa 2 aaaa 2 aaaaa 2 aaaaaa 3 aaabb 2 
•  » » » » 5 months ago, # ^ |   0 Just came online to update this XDThanks I messed up edit-distance part!Thanks for the help! :D :)
 » 5 months ago, # |   +45 Awesome problemset, super fast system testing and rating change -> In a word a nice contest! This contest is also exiting for me, because I found my mistake in code for problem C last minute and submitted 30 seconds before the contest ends and it got Accepted, and became blue after a long gap.Thanks for the nice contest!
 » 5 months ago, # |   +3 div2 b is similar to house robber but cannot solve in the contest :(
 » 5 months ago, # |   +3 For a second I thought I can't solve B2 so i went for naive approach in B1. after writing some stupid long worthless code i tried B and solved it much faster and with less lines of code.Should have just sticked to B2.
 » 5 months ago, # |   0 My solution for D got AC code. But it is wrong, because i write always n + 2.. Ok.. This solution on C++11 got RE code. Then this solution got RE too. Can anyone explain me, how is it working?
•  » » 5 months ago, # ^ |   0 Try exiting the program if a == 0 or b == 0 as soon as you get them. I don't know why that would give an out of bounds error, but I had the same problem.
•  » » » 5 months ago, # ^ |   0 Ok thanks, it is really strange...
 » 5 months ago, # |   0 I don't understand the WA message wrong answer Line [name=s_8] equals to "", doesn't correspond to pattern "[ab]{1,300}" on D. I tested my solution locally and I am not printing any empty strings.
•  » » 5 months ago, # ^ |   0 you can't ask an empty string
•  » » » 5 months ago, # ^ |   0 No, I am not asking any empty strings.
•  » » 5 months ago, # ^ |   +13 It seems to me that checker does not handle termination after "-1" properly.
 » 5 months ago, # | ← Rev. 2 →   0 Shoudn't B2 be done this way?sort the given array. maintain K lists of prefix sum of (i%k) indices only. Then find upper bound of p in these lists, return the max. of these upper bounds. Also add to these upper bounds, those gifts which still can be bought without any offers, after each upper_bound applied. My submission is failing on 55th TC of 2nd test case. Can someone please help me with that? I am not able to get that particular test case, since it is not being rendered on CF.
•  » » 5 months ago, # ^ | ← Rev. 2 →   0 It is simple dp, where dp[i] is min money to pay for first i problems. Sort the goods by price.dp[i]==min(dp[i-1]+a[i], dp[i-k]+a[i])You can allways buy goods one by one, or choose at any point to buy k goods at once. Anyway, you allways buy the cheapest goods.
 » 5 months ago, # |   +10 What strange problems this contest have. I felt upset from Problem B(1).
 » 5 months ago, # |   +5 Problem DWhy if I do more than N + 2 requests (exactly 1000 times) "aabba" it passes 1st test? link. I guess that checker counts only unique requests, not the actual number of requests. My solution was making N + 3 requests (while I thought it was N + 2) and I was getting WA 5 the whole contest. I couldn't even think that the problem was with a checker :(
•  » » 5 months ago, # ^ |   +5 after first time you print "aabba" checker stop it 67562780
•  » » » 5 months ago, # ^ |   +5 I think that wasn't mentioned in the problem statement.
 » 5 months ago, # |   0 Anyone solve B with binary search..
•  » » 5 months ago, # ^ |   0 Not sure it would work. In this problem if you can buy x items, there is no guarantee you can also buy x-1 items.
•  » » » 5 months ago, # ^ |   0 But some are manage to pass by using binary search. Can't understand how.. sol 1 — https://codeforces.com/contest/1282/submission/67533137 sol 2 — https://codeforces.com/contest/1282/submission/67532628 In the second case the user use the binary search twice.. Can u explain the logic behind both the solutin... Thanks..
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +1 My submission using binary search: 67564167. Not sure if my idea is the same as those above.My idea is to sort the goods by their prices, then fix the number of goods that we have to buy separately (obviously, it's in range $[0,k-1]$), and finally using binary search to find the number of group of k goods that we can buy.If the numbers of good that we buy separately is i, it's optimal to buy the first i goods.Overall complexity should be $O((n+k)logn)$.
•  » » » » » 5 months ago, # ^ |   0 thanks, exactly same concept as describe by socketnaut and AngerAndMoney only implementation differ. Thanks.. Can us share any similar problem like this.
•  » » » 5 months ago, # ^ |   0 If you really want to you can binary search on the number of groups of size K you buy, then binary search on the number of singletons you additionally buy.
•  » » » 5 months ago, # ^ |   0 Yeah u are correct if your predicate is can we buy x items but if you consider predicate to be can we buy at least x items then BS can be applied code : 67538774
•  » » » » 5 months ago, # ^ | ← Rev. 2 →   +3 Thanks for replying, can u explain what does second while loop do i.e inside bs.
 » 5 months ago, # |   0 Can anyone explain that why in this solution https://codeforces.com/contest/1282/submission/67533137 they use midb and the for loop for midb, with using only mid as in normal binary search answer fail on first case on test case 7.. Pls explain why midb is necessary.
•  » » 5 months ago, # ^ |   +3 For binary search, your function needs to be monotonic, and this is not the case when you just use the "mid" approach. In the seventh case, note that it costs 7 to get three things, but 3 to get four. 4 6 4 3 2 3 2This is caused by being forced to buy mid%k items individually. The "midb" approach compensates for this by "rounding up" and checking the answer for the next multiple of k. This works because the cost for all values between mid and midb is greater than or equal to the cost of mid and the cost of all values larger than midb is greater than or equal to the cost of midb (proof left as an exercise).
 » 5 months ago, # |   0 How would the solution for D be affected if the strings were not binary? Let's say you had 26*(n+2) queries. Would the same technique work? If not, what would change?
 » 5 months ago, # |   0 Any similar problem like B?
 » 5 months ago, # | ← Rev. 2 →   0 How this test case in 1282C - Petya and Exam is getting the answer as 1. Shouldn't it be 0? 6 17 2 6 0 0 1 0 0 1 7 6 3 7 10 12 
•  » » 5 months ago, # ^ |   0 You can solve any of the easy problems and leave the exam at t = 2, which nets you one point.
•  » » » 5 months ago, # ^ |   0 Thanks, I got it.
•  » » 5 months ago, # ^ |   0 No At time t = 2 he can leave the exam after solving 1 easy problem.
 » 5 months ago, # |   0 WA because of integer overflow hurts again
 » 5 months ago, # | ← Rev. 2 →   0 In Problem C, second Testcase, the 12th test is 2 13 3 6 0 0 2 0 Since mandantory times are 2 and 0, and a==3 I would expect the answer to be 0, no problem can be solved in time, since the first solved problem is at t==3, that is after 0 (and 2).But grader says answer is 2, so both problems should be solvable in time.What did I get wrong, can somebody explain? submisson
•  » » 5 months ago, # ^ |   0 It is not necessary to start solving problem before it's mandatory time.
•  » » » 5 months ago, # ^ |   0 Ahhh, I understand. There is no need to solve the problems until mandatory time. Only, if one finishes after mandatory time, that problems must have been solved.Funny, that the whole first test and the 11 ones before the 12th work correct, even after getting the problem so wrong.
•  » » 5 months ago, # ^ |   0 Because T = 13, you can solve the two problems and leave at t = 6 (which is < T).Mandatory doesn't mean it has to be solved before that time, it means that if you don't leave before it becomes mandatory, then you cannot leave until you solve it (it doesn't matter when you solve it but you have to solve it before leaving), but you still have to do that before you run out of time (t=T).
•  » » » 5 months ago, # ^ |   0 Ok, got it, thanks.
 » 5 months ago, # |   -70 This was one of the worst rounds I've done. I hope none of real coordinators would allow problems ABE in the contest. D was nice, but forbidding to ask queries longer than maximal string is a bit silly. Still, having one nice problem is not enough to make a round out of it. I like when new people are starting in problemsetting, but next time ask for an actual coordinator who is willing to say that your problems are bad.
•  » » 5 months ago, # ^ | ← Rev. 3 →   +30 Just out of curiosity, what was bad in A and B other than the long problem statement?
•  » » » 5 months ago, # ^ |   -26 None of these problems are fresh in any sense.
•  » » » » 5 months ago, # ^ |   +29 Cool, makes sense. The problem ideas may seem old especially given your level of experience.Still according to me both A and B were good problems for beginners.
•  » » » » » 5 months ago, # ^ |   +5 The first time that I see Nutella's comments are downvoted!
•  » » » » » » 5 months ago, # ^ |   +33 U haven't seen many comments of Um_nik
•  » » 5 months ago, # ^ |   +30 I would agree on A (probably, suits Div.3 better). B seemed okay, but maybe too complicated statement for little thinking effort. E was nice although seemed too easy for the last problem. But in the end the contest seems to be well-balanced, maybe one more hard problem was missing.
•  » » 5 months ago, # ^ |   +43 Nah, nice contest :D
•  » » 5 months ago, # ^ |   +2 E was really nice
•  » » 5 months ago, # ^ | ← Rev. 2 →   +1 I think he forgot to look at... It was Div2 not Div1.
 » 5 months ago, # |   +24 What is the reason for having an upper bound on the size of string query you can ask?
•  » » 5 months ago, # ^ |   -6 Do stop people from bruteforcing everything.
•  » » 5 months ago, # ^ |   0 I'm guessing it's mainly for hacks. It's easy to forget the condition and print a 301 length string
 » 5 months ago, # |   0 i solved E with topological sort . Is there any other way (for finding the vertices permutation)
•  » » 5 months ago, # ^ |   0 Not sure if we can call it topological sort. It's just a simple circular cycle which isn't even directed. Maybe calling it a dfs is enough.
•  » » » 5 months ago, # ^ |   0 Guess i made it over complicated for me then
•  » » » 5 months ago, # ^ |   0 can you explain how to use dfs to solve this problem ?
•  » » » » 5 months ago, # ^ |   0 There was a bit of preparation needed before doing the dfs which was the crux of the problem, dfs was simple once you get the idea that — identify outer circle's edges (those which occur in only 1 triangle) create a graph using those edges (guaranteed that it will be a circle). then do dfs starting from any random node.
•  » » » » » 5 months ago, # ^ |   0 thanks.can you explain that idea which led to dfs as solution.I mean can you elaborate a little more.
•  » » » » » » 5 months ago, # ^ |   0 The main idea was - whenever there is a cut — the place where knife went and created an edge will have to be shared by two triangles. Those edges are of no use. So find those edges and remove them. And create a graph with rest of the edges. How to find those shared edges? Just count each edge in all the triangles like map[edge_a_b]++ . Whichever edge has count 2 are the ones where knife went.
•  » » » » » » » 5 months ago, # ^ |   0 I got what you are saying .Thanks
•  » » 5 months ago, # ^ |   0 I solved it like this: the last piece to be cut must contain a vertex which only appears once. So, find such a piece (let's call it [t,a,b], where t only appears once), remove it, solve recursively for the remaining pieces, then in the linked list obtained by solving recursively, replace edge (a,b) with edges (a,t) and (t,b).
 » 5 months ago, # | ← Rev. 2 →   0 Can some one help me find the mistake in my submission 67570438 for Problem D.
 » 5 months ago, # |   0 When you think your approach is wrong but after contest you realize it is just -1 which gives causes WA, it hurts.
 » 5 months ago, # |   +12 Master as christmas present!
 » 5 months ago, # |   0 Hello everyone,I have tried to make video solution for the first four problems of Codeforces Round 610 Div. 2, hoping to help people understand the problem and what was my approach for the same. Please do like the video and do subscribe for more such content.Video playlist: Codeforces 610 Div2 Video Solutions PlaylistSeparate links are as follows: A B1 B2 CHappy CodingDivyanshu Kumar
 » 5 months ago, # |   0 Using google translate for the editorial makes it super hard to understand :(
 » 5 months ago, # |   0 VERY VERY GOOD CONTEST
 » 5 months ago, # | ← Rev. 3 →   0 In problem B2, for the following test, why should the output be 1 and not 2? 15 2 310 1 3 9 2I am sure I am missing out something trivial. Please help me out.
 » 5 months ago, # |   0 Can someone help me with my submission for C problem.Getting WA in test2 445 numberMy approach is to first find time lastgreat<=t where it is possible to solve all mandatory problems and then in timeremaining = lastgreat-a*(number of mandatory easy problems upto lastgreat)-b*(number of mandatory hard problems upto lastgreat). I will add easy problems and hard problems if its possible that remain during the time interval where t>=time>lastgreat