### Vovuh's blog

By Vovuh, history, 6 months ago, translation, ,

This time I have nothing to say except that this round will consist of 7 different problems!

<almost-copy-pasted-part>

Hello! Codeforces Round #552 (Div. 3) will start at Apr/16/2019 17:35 (Moscow time). You will be offered 6 or 7 problems (or 8) with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 (or 8) problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</almost-copy-pasted-part>

UPD: Thanks to le.mur for idea of one of the problems.

UPD2: Editorial is published now!

UPD3:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 ysluo2000 7 229
2 fake_delete_pls2 7 251
3 KefaKuma 6 178
4 Zhao-L 6 222
5 haimiaoyuzhao 6 240

Congratulations to the best hackers:

Rank Competitor Hack Count
1 wzw19991105 49:-4
2 ScreaMood 42:-1
3 I_love_Maria_Krylova 35:-5
4 Hacked_ 31:-1
5 Zombie358 30:-7
949 successful hacks and 502 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A MinatoYukina 0:01
B MinatoYukina 0:04
C Chess_fan 0:08
D nikizakr 0:07
E FluffyTT 0:21
F FluffyTT 0:09
G 1tst 0:14

• +200

 » 6 months ago, # |   0 Expecting this round to be full of awesome questions with strong pretests!!!
 » 6 months ago, # |   +35 Every problem you create is nice! Thanks for your efforts, wish you luck, Vovuh
 » 6 months ago, # |   -15 I can smell an easy and a hard version problem.
•  » » 6 months ago, # ^ |   -22 it seems that each problem of div3 contest will be divided into two part: hard version and easy version LOL
 » 6 months ago, # |   -31 i like div 3
 » 6 months ago, # |   +18 I will do my best to try to became an expert in this round, I wish high rating to everybody!
•  » » 6 months ago, # ^ |   0 Sorry if I said something wrong, I didn't mean to to this...
•  » » » 6 months ago, # ^ |   +16 You said nothing wrong, dont have to sorry for it
 » 6 months ago, # |   -6 Hope this contest is balance one like last DIV3.
 » 6 months ago, # |   -10 Hope to AK. Fighting
 » 6 months ago, # |   +2 The problems of each Div3 rounds are awesome. I believe if one regularly upsolve(solve the problems that one can't solve during contest time) the problems, then (s)he must learn something new and improve gradually.
 » 6 months ago, # | ← Rev. 3 →   +26 1tst solved 3 problems in 2 minutes !! how that possible ?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +17 Maybe he or she has 300wpm and 300iq :)
•  » » » 6 months ago, # ^ | ← Rev. 2 →   -48
•  » » 6 months ago, # ^ |   0 am I reading it wrong or this profile really solved QUE E in 6 seconds?
•  » » 6 months ago, # ^ |   +2 it's simple.. Cheating
•  » » 6 months ago, # ^ |   0 Mabay he had solved them early in the constest but submit them later at the same time
•  » » » 6 months ago, # ^ |   +2 i think no one does that, even if they do that, they will loose the rank. i will agree with @supaHotFire
 » 6 months ago, # |   0 How to solve problem E?
•  » » 6 months ago, # ^ |   +2 The way I did it was using: A segment tree with lazy updates to find the maximum The painter's problem using disjoint-set-union to travel the array even after the 'deletion' of foster elements It's a lot to know and implement. I'm assuming there's an easier solution because of that
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +49 This is the precise definition of overkill. You can use set to find maximum element, and store nxt[i] and prev[i] -> index next and prev to i, which is not still in a team. So you will have to move O(k) itmes in each iteration and there will be atmost O(n/k) iterations as, each iteration removes atleast k elements.
•  » » » » 6 months ago, # ^ |   +3 Exactly as that, decided to delete my comment because i didn't think i explained it properly.
•  » » » » 6 months ago, # ^ |   +3 Thanks it Helped!!
•  » » » 6 months ago, # ^ |   +7 My approach: Keep a set with pair {position, value} and another set with pair {value, position}. So second set gets the first element and the other set gets the (currently) adjacent ones. (I use this idea a lot, although there may be easier methods). My submission here https://codeforces.com/contest/1154/submission/52846244
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +6 I also tried to do this, I finished now, FINALLY!!!! The main code is here: https://codeforces.com/contest/1154/submission/52877899
•  » » 6 months ago, # ^ |   0 u can use two ordered sets, where each element is a pair, and in first ordered set store each (val[i], i) and in second ordered set store (i,val[i]). this made it quite easy.
•  » » 6 months ago, # ^ | ← Rev. 2 →   +3 All I did was just kept track of the right and left index of any given index at any moment. And after each iteration, I updated them as necessary.You can view my code here: 52867981Just a normal implementation.
•  » » 6 months ago, # ^ |   0 doubly-linked list + max-heap
•  » » 6 months ago, # ^ |   0 I think the easiest way is using doubly-linked list + sorting the values. Using a set(as max heap) also seems easy to implement.
 » 6 months ago, # |   +7 Is it possible to solve problem F without the constraint k is not exceeding 2000?
 » 6 months ago, # |   -12 A: That minus just before a+b is not a minus, it is just a dash. Thank you, but that killed the fun for me.
•  » » 6 months ago, # ^ |   -32 me, me too I pour my 1 hour on that problem
•  » » » 6 months ago, # ^ |   -73 B: Lowest positive Integer is not 1, it is 0. Haha, very funny. C: ans overflows if not defined long long. D: Look like dp, but is not. Really funny.
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   +129 B: Are you really serious? There is at least 4 places in the statement where is said NON-NEGATIVE value $D$.C: If your calculations are somewhat inaccurate why are you trying to blame us for it?D: If you think that the problem topic is DP it is not our fault too.And about A: there is a place in the output section where all four numbers are defined without any "dashes" or "minuses".
•  » » » » » 6 months ago, # ^ |   +2 i still think the dash is confusing and missleading which is exspecially bad for a problem A. (can this still be changed for users who solve this later?)
•  » » » » » » 6 months ago, # ^ |   +34 Okay, I will change this dash to colon. But I still think that users should read statements more carefully. Just see the old problems on Codeforces, their statements are so short and many almost obvious things are just not described. But now we are going to explain almost every thing which may be ambiguous. I think that after several hundreds of rounds participants will ask what does "integer" mean or somewhat similar. And it is very upsetting.
•  » » » » » » » 6 months ago, # ^ |   +10 But I really enjoyed this contest. Thank you. And for problem A at some point I managed to find out that I was wrong and I got correct answer. I think reading carefully a problem is a part of a problem. I really enjoyed this contest. Than you. Sorry for my bad english
•  » » » » » » » » 6 months ago, # ^ |   +18 I’m not trying to blame you. I just want to make excuse for my poor job :( I’m sorry I hurt you
•  » » » » » » » 6 months ago, # ^ |   0 I respect that you have invested a lot of work, and thank you for it. Even though I did not like this one competition, it's still great to have people doing the job.
•  » » 6 months ago, # ^ |   -18 me too
 » 6 months ago, # |   0 How to solve problem G?
•  » » 6 months ago, # ^ |   0 yeah..i'd like to know ,too...
•  » » 6 months ago, # ^ |   +3 Just fix the gcd and find two smallest numbers with such gcd. I think that's very easy problem for G.
•  » » » 6 months ago, # ^ |   0 I did the same, however i got tle. I tried to precalculate all divisors of numbers in range (1,1e7+5) using 2 nested loops, like this: Your code here... for(int i=1;i
•  » » » » 6 months ago, # ^ |   +3 Instead you can try saving indexes of each number and it will be faster due to constant.See this submission (even instead of calculating gcd dividing by i is enough and makes the solution slightly faster): https://codeforces.com/contest/1154/submission/52851693
•  » » » » 6 months ago, # ^ |   0 It should amortize to nax*log(nax)
•  » » » » » 6 months ago, # ^ |   -8 I know, but you can check this in custom invocation: #include using namespace std; const int k=3e6; vector dzielniki[k]; int main() { int nax=3e6; for(int i=1;i3000 ms. What is wrong when it should be only ~60kk operations?
•  » » » » » 6 months ago, # ^ |   0 you save over 10^9 values in divisors...
•  » » » » » » 6 months ago, # ^ |   0 How did you came up with such estimation?
•  » » » » » » » 6 months ago, # ^ |   0  ll res = 0; for (ll i = 1; i < lim; i++) { res += lim / i; } cout << res << endl; 
•  » » » » » » » » 6 months ago, # ^ |   -8 For lim=1e7 it gives ~162 * 10^6.
•  » » » » » » » » » 6 months ago, # ^ |   -13 whoops i meant 10^8... the problem is the random memory access and vector resizes.
•  » » » » » » » » » 6 months ago, # ^ |   -8 Is there any smart way to optimize it?
•  » » » » » » » » » 6 months ago, # ^ |   0 not like this. I dont believe you can actually save all divisors off all numbers less than 10^7. What i did was to save for each value a prime divisor(with sieving) then if i need to find all divisors of a number i can factor it recursively and generate all divisors in $O(divisors)$
•  » » » » » » » » » 6 months ago, # ^ | ← Rev. 3 →   -8 Thought about this solution as well. So you think that it should be faster? I think you are right actually. I did not suspect vectors to be this slow.
•  » » » » » » » » » 6 months ago, # ^ |   -8 it is quite much faster... The problem is not the vector. Enumerating all divisors off all numbers less than $10^7$ still takes 10s. But you don't need all divisors off all numbers.
•  » » » » » » » » » 6 months ago, # ^ |   0 Ok, thanks. But why do you say that it is not vectors fault when we only do ~ 150 KK operations. It should take ~ 1 sec. And pushing back is the only operation we use?
•  » » » » » » » » » 6 months ago, # ^ |   0 memory allocation is the problem... if you use more memory allocating even more takes even longer... in fact savin all those values would take $640$mb of ram wich would even give you memory limit...
•  » » » » » » » » » 6 months ago, # ^ |   0 Ok thanks for explaination.
•  » » » 6 months ago, # ^ |   0 I just found one accepted G in PyPy 2. Is it possible for this question to AC with Python 3 solution? I mean, it's terrifying to find every possible gcd within the time limit. Is it necessarily O(N^2)?
•  » » » » 6 months ago, # ^ |   0 finding every possible gcd of all pairs is bounded by $O(n\sqrt{n})$ (in fact its even fasert since the divisor function grows much less and we can sieve)
•  » » » » 6 months ago, # ^ |   0 I just wrote another solution which uses a priority queue (heapq in Python 3) which is pretty nice until test 77. Test 77 involves input of all primes and the expected output are those largest repeated primes. This is the worst input for my approach.I tried adding a prime sieve to tackle such special case when the input are all primes. But just the prime sieve itself took up 3000ms, and the bad news is, my heap solution alone took up nearly 900ms for some tests. That's frustrating when it's so close...
•  » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Finally got it to work. Not the most elegant solution you would expect. In fact, it's pretty ugly I feel like my face is turning red just by looking at it. But at least that's an AC.EDIT: The above solution got hacked for TLE, and I tried switching to another approach. But with Python 3 this is not gonna work (TLE), with PyPy 3 the same solution got AC. The main idea of this approach is to iterate all factors from 2 to 10000000 and find the two smallest multiples in the list. Can't get away when the factors of the answer itself are very large, and plenty of time is wasted on smaller factors.
•  » » 6 months ago, # ^ | ← Rev. 3 →   +6 I did the following thing: store the occurring index of each element in the range of a; loop through the whole range; which looping, just assume the current gcd we are checking is some multiples of current i, then the first two we find would be the local minimum, thus we should stop here. The number of operations should not exceed 2.4e8.You could check my implementation here: 52849391
•  » » 6 months ago, # ^ | ← Rev. 2 →   +14 Suppose we find $\underset{x | a_i \text{ and } x | a_j}{min} (a_i*a_j /x)$, Note that minimum lcm of any two values is the answer for the stated. Therefore solution to first problem is solution to second. Now to solve first, for a given x, for minimum, a[i] and a[j] must be minimum. Thus for each x, just consider its two multiples that exists in array.
•  » » 6 months ago, # ^ |   +12 I have a funny solution for G. ACC at the moment but probably hackable. The idea behind my solution is to try as many promising pairs as possible and stop just before we reach the time limit, hoping that we were lucky enough to find the best pair.My implementation is here: https://codeforces.com/contest/1154/submission/52868067The main computation is simply iterating all pairs in the order of smallest to largest. In order to speed up the computation we want to find a reasonable upper bound for lowest lcm before this main computation. This allows us to stop iterating i,j pairs when j>bound. I'm finding the upper bound by iterating all pairs of the lowest 30 non-duplicate items. Duplicate items can be used to construct a worst case scenario where we iterate the same pairs over and over again and reach the time limit before we get to try the optimal pair. We deal with duplicate inputs as a special case before the main computation. So the actual implementation is in this order: Deal with duplicates as a special case Find upper bound for lowest lcm by iterating all pairs of the lowest 30 non duplicate items Main computation: try all pairs from smallest to largest, with a speedup using the upper bound.
•  » » » 6 months ago, # ^ |   0 Idk Java. Is your seed fixed? If yes? Then for sure your soln is hackable, As far as duplicates is concerned. Find the smallest no which occurs twice. It is probable answer.Then create a array which contains all nos only once. Then work on it.
•  » » » » 6 months ago, # ^ |   +3 Default seed for Random in Java is current time in milliseconds.
•  » » » » » 6 months ago, # ^ |   +1 you don't need to hack based on the seed... the propability of this working is quite low...
•  » » » » » » 6 months ago, # ^ |   0 Congratz on the hack! Would you like to share the hack input?
•  » » » » » » » 6 months ago, # ^ |   +9 a lot of unique primes and a few composite values
 » 6 months ago, # |   +24 I think this is the definition of a perfect Div. 3 contest. All the tasks were well explained, simple to understand and most importantly DOABLE for someone with a rating below 1600. Maybe i say this because i finally managed to solve 5 tasks (lol), but it was a great experience. Looking forward to the editorial, to see how F and G were supposed to be solved.
•  » » 6 months ago, # ^ |   0 Yeah, I think it will be good for everyone that rating below 1600 solve all the problems after contest.
•  » » 6 months ago, # ^ |   0 I agree this was a great Div. 3 contest, although the tasks could have been explained better. I had to ask questions about 2 tasks because of ambiguities in the statements.
 » 6 months ago, # |   +5 That moment when everyone is thinking how to solve the problems and you are debugging some stupid mistake in your code that has nothing to do with the problem
•  » » 6 months ago, # ^ |   +1 I, for one, spent 15 minutes to realize I've declared an array using 'bool' instead of 'int'. Yeah.
•  » » » 6 months ago, # ^ |   0 XD it's funny but also painful
•  » » 6 months ago, # ^ |   0 happened with me, spent 40 minutes on C, Accepted just after 2 minutes when contest was over. Now I am feeling useless X_X
 » 6 months ago, # |   0 Can anybody help me with problem E?Why this code TLE https://codeforces.com/contest/1154/submission/52858503and this Code AC https://codeforces.com/contest/1154/submission/52867179
•  » » 6 months ago, # ^ |   0 Maybe my code can give you some help?Actually problem E is not as complex as we thought...Your text to link here...
•  » » 6 months ago, # ^ |   0 You can check out my soln- I did it using doubly linked list https://codeforces.com/contest/1154/submission/52864142
 » 6 months ago, # |   0 What is the problem in my E solution? I m getting TLE in TC #37 solution: Solution
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 Got 37 TLE as well at first, but try using next/previous arrays instead of the boolean 'taken'. Where next[i] — the next student after i that isn't taken in any team. (so goes with previous)EDIT : With the boolean array, the complexity can come close to O(n^2)
•  » » » 6 months ago, # ^ |   0 how to do that?
•  » » » » 6 months ago, # ^ |   +3 First set next[i] = i + 1 and prev[i] = i — 1 Then say you start with the biggest value in the sorted array. You go k positions up and k down (assuming you sorted the array keeping track of the original positions). Now say the position of the biggest value is POS, you go to POS + k and POS — k and you set next[POS — k — 1] = POS + k + 1 and vice versa, so that you won't go through them again. Lastly, instead of doing POS++ while going thorough the elements, you say POS = next[POS] or POS = prev[POS] to save time.I'm terrible at explaining.
•  » » » » » 6 months ago, # ^ |   0 U r too good in explaining...thanx buddy
•  » » » » » » 6 months ago, # ^ |   0 I hope you are sarcastic.
 » 6 months ago, # |   0 I got two wrong submissions in Problem D because at last in Output section they said that print the max segment where Robot can reach. So, I just added the remaining value of the battery and the accumulator to get the final answer, whereas it was wrong, and when I removed them, I got Accepted. It's wrong they must have mentioned that N will be the maximum value, where Robot can reach.I know it was written that Robot's target is to reach N. But clearly, there was no mention in Output part. And that led me almost 30-40 penalty plus I wasn't able to submit E, which was quite easy.
 » 6 months ago, # |   0 Vovuh I'm trying to hack problem G and got unexpected verdict while hacking. Hacking id is 550275.
•  » » 6 months ago, # ^ |   +3 It was because of one of my testing solutions. I was not sure that it is correct and just forgot to tag it as "time limit exceeded or correct". All is ok now, the main solution is fast enough and written without bugs :)
 » 6 months ago, # |   0 can someone please give some hint for problem F and G?
•  » » 6 months ago, # ^ |   0 Problem F: SpoilerYou only care about the k (k<=2000) cheapest shovels, the rest are useless. The same for the special offers
•  » » » 6 months ago, # ^ |   0 Thanks. Actually I have implemented the same solution but due to some bugs it is not passing! Btw did you know how to solve G?
•  » » » 6 months ago, # ^ |   0 Can the number he buy over the number he need to buy??? For example 6 1 5 1 2 3 4 5 6 6 5 If he buy 6 shovels,he can just pay 6 dollars.
•  » » » » 6 months ago, # ^ |   0 No. You need to buy exactly k shovels
•  » » 6 months ago, # ^ |   0 F : Just consider k shovels with least cost. And store for each 1 <= i <= k, maximum number of shovels you'll get for free, if you buy i shovels. Rest is just knapsack.
•  » » » 6 months ago, # ^ |   0 Can you please explain this in detail?
 » 6 months ago, # |   +6 Finally!!Expert :)
•  » » 6 months ago, # ^ |   +1 Big OOF
 » 6 months ago, # |   0 problem E : Why when the array is sorted the program runs several times longer? I don't understand why.
 » 6 months ago, # |   +23 I am very sorry about my bug in the problem G checker. It affected literally two people and just see how it looks:I'm just TRYING to read two distinct integers $i$ and $j$ where $i < j$: int i = in.readInt(1, n, "i") - 1; int j = in.readInt(i + 1, n, "j") - 1; I've tried... Really tried...
•  » » 6 months ago, # ^ |   0 Just curious how did this cause the bug in the checker ?
•  » » » 6 months ago, # ^ |   +28 If participant prints two equal numbers, this case will be considered correct and the checker will not raise any exceptions (in fact it should say that it is wrong to print two equal indices) and in case when LCM of $a_i$ and $a_i$ is less than the jury answer then checker will raise "FAILED" verdict and say that jury answer is incorrect.
•  » » » » 6 months ago, # ^ |   +23 Oh. Really a tough thing to notice. Anyways problems were nice and it didn't affect much :)
 » 6 months ago, # |   -25 In problem D:problem statement said: If the current segment is exposed to sunlight and the robot goes through it using the battery, the charge of the accumulator increases by one (of course, its charge can't become higher than it's maximum capacity).But it is not said that if the charge of the accumulator exceeds it's maximum capacity, then you can't use battery during sunlight. I thought battery can be used but the charge of accumulator will not increase in this situation, when accumulator has already maximum charge.Vovuh I think you should clarify this in the problem or give a sample input using such situation.
•  » » 6 months ago, # ^ |   0 sure you can use your battery during sunlight whenever your battery > 0; but that's not optimal strategy
•  » » » 6 months ago, # ^ |   0 I got your point, I didn't think that way. I thought we can't use battery during sunlight in case after increasing the charge exceed the accumulator's capacity. Though I got AC thinking so and checking the condition, now I understood that the actual cause of not using battery is "not optimal".Thanks.
 » 6 months ago, # |   0 unfortunately very weak tests, only 11 tests for problems A B C. Please do more tests in the future.
 » 6 months ago, # | ← Rev. 3 →   0 In problem G, I got this in one of test cases wrong answer Integer parameter [name=j] equals to 557392, violates the range [557393, 1000000] What does it even mean! Solution link. UPD: Figured out the error.
 » 6 months ago, # |   +16
 » 6 months ago, # |   +6 My first CodeForces round ever! I'm really excited, I have also dedicated myself starting today to solve at the very least 3 programming problems daily.
 » 6 months ago, # | ← Rev. 2 →   +3 The problem A look like -a+b, a+c, b+c and a+b+c before the updateThis silenced me for 20 minutes. :<
 » 6 months ago, # |   +4 WOW! such strong pretests -_-
 » 6 months ago, # |   0 Thank you guys for this contest. I really enjoyed solving the problems and do think that it was a well balanced contest. :)
 » 6 months ago, # |   +5 Weak pretests for B :(
•  » » 6 months ago, # ^ |   0 what according to you is a strong pretest?. There were only 5-6 conditions which were needed to be handled
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +4 There were three cases in this problem: 1. Make all the elements equal to ak+d, 2. Make all the elements equal to ak-d, or 3. Make all the elements equal to ak. for any 1<=k<=n. If we get a constant d(in case of multiple values the smallest one) then it will be the answer otherwise print "-1". My submission gone wrong because I've missed the 3rd case which appears to be one of the basic case. 5 4 2 6 2 6 this test case covers the third case.I think which was missing in the pretests. My submission wthout handling 3rd case 52834854 and with handling 3rd case 52891662
•  » » » » 6 months ago, # ^ |   +1 Oh I didn't know that. If I could have found such a submission I could have made my first hack. Btw I am really inspired seeing your love for India
 » 6 months ago, # |   0 Is this round rated? system test had finished, why my score isn't update?
•  » » 6 months ago, # ^ |   +1 Wait
•  » » 6 months ago, # ^ |   0 Also, my contests tab shows "no items". Did I do anything wrong or it's not updated yet?
•  » » » 6 months ago, # ^ |   0 Not yet updated! It takes some time (filtering out copied submissions)
•  » » 6 months ago, # ^ |   +3 thank you, i hope my rating change to Specialist.
•  » » » 6 months ago, # ^ |   +8 Hd7 Your rating will be around 1430
•  » » » » 6 months ago, # ^ |   +3 Wow! It's exactly 1430. How do you calculate the rating? or you have just seen it.
•  » » » » » 6 months ago, # ^ |   +1 Google "cf-predictor" =D
•  » » » » » » 6 months ago, # ^ |   0 Thank you! I did it =)))
•  » » » » » » » 6 months ago, # ^ |   0 You are welcome. Congratulations!
 » 6 months ago, # |   -6 is it rated?
 » 6 months ago, # |   +15 my solution got compilation error during the system test case and when i coped the same solution and resubmitted it i got all correct vovuh please look at this as i lost my rating due to this bug of codeforces my submission link is[submission:52856023]
•  » » 6 months ago, # ^ |   +1 Radewoosh Swistakk Your worst nightmare became true :P #NOSTALGIA
•  » » » 6 months ago, # ^ |   +18 What a trash mention
•  » » » » 6 months ago, # ^ |   0 Sorry about that! XD
 » 6 months ago, # | ← Rev. 2 →   0 .
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 try this, input : 1 2 3 it's supposed to print 5 because when you start on wednesday you can eat 2chicken, 2 rabbit and 1 fish, but yours print out 3
•  » » » 6 months ago, # ^ |   0 After Wednesday: 1 2 2 After Thursday : 0 2 2 After Friday : 0 2 1 After Saturday : 0 1 1 On Sunday it doesn't have food so is not answer 4 in this case?
•  » » » » 6 months ago, # ^ |   0 sorry I made a mistake, you should start on Tuesday to make output 5
 » 6 months ago, # | ← Rev. 2 →   0 In problem E Using long long got TLE Using int got AC Why??
•  » » 6 months ago, # ^ |   0 This may happen in many problems who have tight time complexity so it is better to use long long int only where it is needed and always use the fast input method. otherwise, in many cases, it becomes very frustrating to find these kinds of mistakes.
 » 6 months ago, # |   0 Hii, I am new to java. Can anyone plz explain why this solution of F is getting TLE on test 66. 52900731
•  » » 6 months ago, # ^ |   0 Arrays.sort on primitive types is quadratic worst-case. Try using Arrays.sort on Integer or Collections.sort.
 » 6 months ago, # |   0 How to solve F?
 » 6 months ago, # |   0 Thank you for interesting contest, vovuh, waiting for editorial!
 » 6 months ago, # |   0 Can anyone provide some hint for how to solve G?
•  » » 6 months ago, # ^ |   +3 This might help: soln
•  » » » 6 months ago, # ^ |   0 Got the solution, THanks:)
 » 6 months ago, # |   0 Problem G is exactly the same problem that has been asked on StackOverflow before. Link
•  » » 6 months ago, # ^ |   +27 And so what? Did you see fast enough solution to our version of this problem in the link you posted? We have seen this link, but still gave the problem because we haven't found any fast solution in google.
 » 6 months ago, # |   -12 I don't know, that's just accidental
 » 6 months ago, # |   0 How to solve F?
•  » » 6 months ago, # ^ |   +3 My Approach :We need to buy K shovels at lowest possible prices. We will obviously use the K lowest priced shovels. Thus sort the array. Now we only need to save the offers (x,y) in which x <= K as we cannot buy more than K shovels. Make hash array where hash[i] stores maximum number of free shovels we can get by buying exactly i shovels using one of the offers. hash[j] = 0 implies no offer available on purchasing exactly j shovels. Now time to apply DP! let DP[i] be minimum cost to buy i shovels. To calculate DP[i] iterate j = 1 to i, and find min of DP[j-i] + cost to buy j-hash[j] shovels starting from index i. (cumm[i]-cumm[i-j+hash[j]]) What we are doing is for every i simply apply every offer and check which gives minimum price and store it. DP[k] is required answer. Link to my solution.
•  » » » 6 months ago, # ^ |   +3 Can you tell me Why picking an offer first and then trying to minimize the cost by using this offer on number of shovels bought is a wrong approach, offers(x,y) are sorted in non-decreasing order of x. Link to code.
•  » » » » 6 months ago, # ^ |   +3 Hey The ordering of offers is not the correct thing to do.You may have to re use an offer after using some other offer!. In fact my first few submissions were using similar approch and was getting WA as well. Consider two offers (5,3) and (2,1) If we use offer (5,3) before (2,1) for k=8 and A = [1,1,2,3,4,5,6] we get cost as 12 while if we use (2,1) before (5,3) we get cost as 13. But for case k=8 and [1,5,5,5,5,7,10] if we use (5,3) before (2,1) we get cost 22 while if we use (2,1) before (5,3) we get cost as 20. So we can order the offers as one order may give better value in a few cases but higher values in some cases.