Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

### fcspartakm's blog

By fcspartakm, history, 3 years ago, translation, ,

• +52

 » 3 years ago, # |   0 Can someone explain how to prove a particular greedy approach , like the one given in the editorial for D. For the D problem I tried a approach of splitting the max(a, b) into blocks of length k and placing the other tea in between them . If I have some more tea bag left I fill them in blocks of k in between the previous one. I got WA in test 9 For example 9 2 5 4 First I get GGBGGBG Now I fill the remaining 2 B before the first G so my final output is BBGGBGGBG
•  » » 3 years ago, # ^ |   0 I haven't read your code, but I guess I can provide a counter-test for your solution. Consider the following test 11 3 6 5. First you get GGGBGGG. After that, you insert remaining four G's in the beginning. But you can do that, because K equals to 3.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Sorry , here is my CODE My output for your test case is BBBGBGGBGGG
•  » » » » 3 years ago, # ^ |   0 LUL dat code xD
•  » » 3 years ago, # ^ | ← Rev. 13 →   +1 Let me attempt a proof at the solution for Problem D:Let the predicate be that the greedy algorithm will find the solution iff it exists.Now, how do we know if a solution exists in the first place?Now, there are 2 cases: Two teas are of same quantity. Two teas are of different quantity. For the first case, it is obvious that the solution exists since we can just take one at a time.The second case is more tricky. Let us recognise that we need to find a mapping between blocks of tea A and blocks of tea B.Let tea A be the tea of lesser quantity. Now, in every mapping, we must map at least 1 of A to at most k of B. Hence, |B| can be at most (|A|+1)*k since we can place combine pairs of k Bs and 1 A together. Now, we can place at most k Bs at the right of the last A. Now that we know how to tell when a valid solution exists, we need to prove our original predicate.Let's assume that the solution exists based on our above conditions (i.e. there is a valid quantity of B and, we can always find mapping from at least 1 of A to at most n (<=k) of B).Case 1 is trivial as the greedy algorithm will pick one of each tea in alternating steps.For case 2,Let tea A be the tea of lesser quantity, and tea B be the tea of greater quantity.For case 2, the algorithm will pick at most n (<=k) from tea B (n is maximised). Now, we will pick 1 from tea A since |B| >= |A| at all times. Hence, we have a block mapping from A to B. This choice will repeat until all of A and B have been used up. Note that the choice for A is minimal. Hence, even for a minimum quantity for A, the greedy algorithm will always find the solution.Now we must prove in the other direction: if the greedy algorithm finds a solution, then the solution exists (is valid).If the greedy solution finds a solution, then all of the A and B must have been used up since we run the algorithm while |A| > 0 and |B| > 0 and there exists a one to one mapping from each block of A to each block of B.Hence, the greedy algorithm will find the solution iff it exists.Do correct me if I am wrong.
 » 3 years ago, # | ← Rev. 2 →   +11 Here is an alternate solution for D:First let us take a as the smaller number and b as the bigger number.Now for optimal arrangement,we have to arrange it as:_ a _ a _ a _ a _ and so on. The underscores represent the places where some numbers of b can be placed.Now we see that the max underscore are (a+1). Therefor maximum b can be (a+1)*k . If b is more than this, than it is not possible.Now let us first place single b's in the first 'a' underscores.(since b>=a) Then excess amount of b's are (b-a).Now let us iterate from the first underscore to the last and in every iteration , if there are any excess 'b's left, let us add them to that underscore.(Keep in mind that we cannot add more than k-1 for the first 'a' underscores and k for the last underscore).Code-23106386 Also use long long instead of int!(My solution in sys tests because of overflow :( )
•  » » 3 years ago, # ^ |   0 Thanks a lot I got accepted now.
 » 3 years ago, # | ← Rev. 3 →   +2 When you see the constraints and refrain to think more! Unorthodox approach in Problem C. Simulate the entire ride as answer will never be greater than 1e6. :DCode
•  » » 3 years ago, # ^ |   0 how did you gauge that time should only be integers, I planned to simulate but couldn't figure out way to deal with decimal timings
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Two cases: Walking all the way — obviously integer Walk for a while (t >= 0) then switch to tram, then you could just wait for the tram anyways, as the tram always arrives the destination at the same time regardless of the time of you taking the tram, thus obviously also an integer.
•  » » » » 3 years ago, # ^ |   0 Suppose the tram is coming to pick you up, by walking in the direction of destination are you not cutting down on the time needed? I don't understand why standing at x1 is same as moving in the direction of x2.
•  » » » » » 3 years ago, # ^ |   +1 Let's consider this simple case where I saw it on a book.Say Bob is going to school, he could either walk 30 minutes to school, or wait 10 minutes for the bus and reach school in 10 minutes, or you could ride the bus just like in the Tram question we are concerning.Notice that no matter where you pick up the bus, it's still the SAME BUS. That alone means it is always arriving the school after 20 minutes, as the bus always reaches the destination at a fixed time.
•  » » » » » » 3 years ago, # ^ |   0 Yeah right, I get it now. Thanks ! Nice Approach.
 » 3 years ago, # | ← Rev. 3 →   +8 in F, moving the right pointer, if we can fit the song full or partly, we fit the song partly? i dont think that always works, for example 3 1 10 3 3 8 the pointer would take 3 as a partly song and wont fit 8 but we can make 8 the partly song and listen to the full setalso E has weak test casesfor this case: 6 20 4 6 2 2 1 3  my program AC outputs: 2 5 6 4 1 3 while the solution 1 4 6 2 5 1 exist EDIT: checked my solution http://codeforces.com/contest/746/submission/23099017. it looks like there are some testcases (like tc #6) that are giving different minimum answers, the jury comment says "OK, answer exist"), so does this mean we only need to check for the answer? the problem says minimum amount of changes...
•  » » 3 years ago, # ^ |   +6 Woah! the checker isn't checking if the answer is minimum or not. This is highly surprising.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 I wonder why the author or problem setters are not replying to this query. That means the question statement is wrong? Then the contest should have been unrated :P. Edit: By trial and error, I have found that number of exchanges need to be <= m to get accepted. So, a simple solution of taking n odds and evens(from set of [1,m] and given numbers) and then fixing already present numbers gets AC.
•  » » » » 3 years ago, # ^ |   +30 Oh, it really was a bug in the checker. We are terribly sorry all our checks didn't prevent this. We'll try out best to be even more careful with checkers.Regarding this problem, we will fix it in the problemset. Thank you for pointing this bug out!
 » 3 years ago, # |   0 Please explain solution of 746E — Numbers Exchange, from editorial it is not clear..
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 Let's say we have some pointers for odd number and even number. This pointer is used for which odd/even number we can use next.First, check each number which has duplicate in original array. If the number has duplicate Change that number in this way : 1.) If the number is odd and the number of odd numbers is more than even numbers, then change that number with next possible even number 2.) If the number is odd and the number of odd numbers is less than or equal to even number, then change that number with next possible odd number (Vice versa if the number is even number)Then, after change every duplicates, we can have a condition when number of even numbers is different than number of odd numbers. So for every "new array" elements, we check whether if it's odd or even. If it is odd and the number of odd numbers is more than the number of even numbers, we should change it with next possible even number (vice versa with even number in the "new array")To calculate the number of cards exchange, simply we compare each element in our "newest array" (the one we have after the second "change") with the original array from input.What case makes it impossible? For every case of changing cards, we check whether our current available odd/even number is more than M.
•  » » » 3 years ago, # ^ |   0 The checker is not checking for minimum number of exchanges. See Test Case 6
•  » » » » 3 years ago, # ^ |   0 That's interesting. The problem even says to find the minimum number of exchanges.
 » 3 years ago, # |   0 Please explain problem F. It is not clear from the editorial
•  » » 3 years ago, # ^ |   0 Idea: Use two pointers to keep track of the maximum amount of the tracks you can listen if you start from [left for left in range(n)] (find the corresponding right [left, right]).Say if we have [left, right] already found, it is easy to maintain the sum of decentness while traversing the two pointers, the problem left is how to find the corresponding (right) for each (left). We will use greedy to minimise the listening time, that is to partially listen for the wth longest tracks.In order to maintain the listening time in a decent time, we should use heaps to keep track of the tracks that are being partially listened and those who are not, and maintain the sum. We should also use two pointers for keeping track of the total listening time — manipulate the heaps and the sum of listening time whenever a track is included / excluded to the current segment.
•  » » » 3 years ago, # ^ |   0 How does minimizing the listening time will maximise the total pleasure?
•  » » » » 3 years ago, # ^ |   0 Since you're listening to a continuous segment of the playlist, the more music you listen, the more pleasure you gain (as listening to a music partially does not result in receiving partial pleasantness). You should check if a segment [left, right] can be listened within k seconds, and to achieve that you should compute the minimal time of time required to verify it.
•  » » » » » 3 years ago, # ^ |   0 Thanks for your reply. Actually I wanted to ask how do you decide if a song has to / has not to be listened to ?However it is indeed correct that since listening to half of the time does not reduce the pleasure we will listen to the maximum length songs for half time only.
•  » » » » » » 3 years ago, # ^ |   0 // Actually I wanted to ask how do you decide if a song has to / has not to be listened to ?By the two pointers technique, you fix the left pointer at a place, then you try to extend the right pointer further to the right.So the iteration will be... Try to move the right pointer, while doing so, include the songs into our calculation of the total time, and update the answer until we ran out of time or reached the end of the playlist. Try to move the left pointer, while doing so, exclude the songs from our calculation of the total time, until there's enough time to listen to all of the songs we included, then update the answer. h1: the heap used for storing songs that are being listened partiallyh2: the heap used for storing songs that are being listened fully
•  » » » » » » » 3 years ago, # ^ |   0 Oh, I understood it now!Actually I was under the confusion that we can skip the songs from in between. Read the problem statemnet again and your solution became clear.Thanks buddy. You really helped a lot.
•  » » » » » 3 years ago, # ^ |   0 Secondly, what is the user of h2 in your code?
 » 3 years ago, # |   0 Can anyone explain G problem ? It is not clear from the tutorial.
•  » » 3 years ago, # ^ |   0 I can, if u stiil need it. And give u even more: another cool solution. But my english is pretty bad :)