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 |

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 |

Expecting this round to be full of awesome questions with strong pretests!!!

Every problem you create is nice! Thanks for your efforts, wish you luck, Vovuh

I can smell an easy and a hard version problem.

it seems that each problem of div3 contest will be divided into two part: hard version and easy version LOL

i like div 3

I will do my best to try to became an expert in this round, I wish high rating to everybody!

Sorry if I said something wrong, I didn't mean to to this...

You said nothing wrong, dont have to sorry for it

Hope this contest is balance one like last DIV3.

Hope to AK. Fighting

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.

1tst solved 3 problems in 2 minutes !! how that possible ?

Maybe he or she has 300wpm and 300iq :)

am I reading it wrong or this profile really solved QUE E in 6 seconds?

it's simple.. Cheating

Mabay he had solved them early in the constest but submit them later at the same time

i think no one does that, even if they do that, they will loose the rank. i will agree with @supaHotFire

How to solve problem E?

The way I did it was using:

It's a lot to know and implement. I'm assuming there's an easier solution because of that

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.

Exactly as that, decided to delete my comment because i didn't think i explained it properly.

Thanks it Helped!!

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

I also tried to do this, I finished now, FINALLY!!!! The main code is here: https://codeforces.com/contest/1154/submission/52877899

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.

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: 52867981

Just a normal implementation.

doubly-linked list + max-heap

I think the easiest way is using doubly-linked list + sorting the values. Using a set(as max heap) also seems easy to implement.

Is it possible to solve problem F without the constraint k is not exceeding 2000?

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.

me, me too I pour my 1 hour on that problem

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.

B: Are you really serious? There is at least 4 places in the statement where is said

NON-NEGATIVEvalue $$$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".

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?)

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.

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

I’m not trying to blame you. I just want to make excuse for my poor job :( I’m sorry I hurt you

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.

me too

How to solve problem G?

yeah..i'd like to know ,too...

Just fix the gcd and find two smallest numbers with such gcd. I think that's very easy problem for G.

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:

Do you know why this gives tle, when it should amortize to nax(log nax), where nax=1e7?

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

It should amortize to nax*log(nax)

I know, but you can check this in custom invocation:

For nax=3e6 it works >3000 ms. What is wrong when it should be only ~60kk operations?

you save over 10^9 values in divisors...

How did you came up with such estimation?

For lim=1e7 it gives ~162 * 10^6.

whoops i meant 10^8... the problem is the random memory access and vector resizes.

Is there any smart way to optimize it?

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)$$$

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.

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.

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?

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...

Ok thanks for explaination.

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)?

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)

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...

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.

I did the following thing:

The number of operations should not exceed 2.4e8.

You could check my implementation here: 52849391

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.

I have a funny solution for G. ACC at the moment but probably hackable. The idea behind my solution is to try as many

promisingpairs 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/52868067

The 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:

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.

Default seed for Random in Java is current time in milliseconds.

you don't need to hack based on the seed... the propability of this working is quite low...

Congratz on the hack! Would you like to share the hack input?

a lot of unique primes and a few composite values

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.

Yeah, I think it will be good for everyone that rating below 1600 solve all the problems after contest.

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.

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

I, for one, spent 15 minutes to realize I've declared an array using 'bool' instead of 'int'. Yeah.

XD it's funny but also painful

happened with me, spent 40 minutes on C, Accepted just after 2 minutes when contest was over. Now I am feeling useless X_X

Can anybody help me with problem E?

Why this code TLE https://codeforces.com/contest/1154/submission/52858503

and this Code AC https://codeforces.com/contest/1154/submission/52867179

Maybe my code can give you some help?Actually problem E is not as complex as we thought...Your text to link here...

You can check out my soln- I did it using doubly linked list https://codeforces.com/contest/1154/submission/52864142

What is the problem in my E solution? I m getting TLE in TC #37 solution: Solution

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)

how to do that?

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.

U r too good in explaining...thanx buddy

I hope you are sarcastic.

I got two wrong submissions in Problem D because at last in

Outputsection they said that print the maxsegmentwhere 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 gotAccepted. It's wrong they must have mentioned thatNwill 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

Outputpart. And that led me almost 30-40 penalty plus I wasn't able to submit E, which was quite easy.Vovuh I'm trying to hack problem G and got unexpected verdict while hacking. Hacking id is 550275.

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 :)

can someone please give some hint for problem F and G?

Problem F:

SpoilerYou only care about the k (k<=2000) cheapest shovels, the rest are useless. The same for the special offers

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?

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.

No. You need to buy exactly k shovels

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.

Can you please explain this in detail?

Finally!!

Expert :)

Big OOF

problem E : Why when the array is sorted the program runs several times longer? I don't understand why.

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$$$:

I've tried... Really tried...

Just curious how did this cause the bug in the checker ?

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.

Oh. Really a tough thing to notice. Anyways problems were nice and it didn't affect much :)

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.

sure you can use your battery during sunlight whenever your battery > 0; but that's not optimal strategy

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.

unfortunately very weak tests, only 11 tests for problems A B C. Please do more tests in the future.

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.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.

The problem A look like -a+b, a+c, b+c and a+b+c before the update

This silenced me for 20 minutes. :<

WOW! such strong pretests -_-

Thank you guys for this contest. I really enjoyed solving the problems and do think that it was a well balanced contest. :)

Weak pretests for B :(

what according to you is a strong pretest?. There were only 5-6 conditions which were needed to be handled

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

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

Is this round rated? system test had finished, why my score isn't update?

Wait

Also, my contests tab shows "no items". Did I do anything wrong or it's not updated yet?

Not yet updated! It takes some time (filtering out copied submissions)

thank you, i hope my rating change to Specialist.

Hd7 Your rating will be around 1430

Wow! It's exactly 1430. How do you calculate the rating? or you have just seen it.

Google "cf-predictor" =D

Thank you! I did it =)))

You are welcome. Congratulations!

is it rated?

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]

Radewoosh Swistakk Your worst nightmare became true :P #NOSTALGIA

What a trash mention

Sorry about that! XD

.

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

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?

sorry I made a mistake, you should start on Tuesday to make output 5

In problem E Using long long got TLE Using int got AC Why??

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.

Hii, I am new to java. Can anyone plz explain why this solution of F is getting TLE on test 66. 52900731

Arrays.sort on primitive types is quadratic worst-case. Try using Arrays.sort on Integer or Collections.sort.

How to solve F?

Thank you for interesting contest, vovuh, waiting for editorial!

Can anyone provide some hint for how to solve G?

This might help: soln

Got the solution, THanks:)

Problem G is exactly the same problem that has been asked on StackOverflow before. Link

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.

I don't know, that's just accidental

How to solve F?

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.

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.

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.