На этот раз мне нечего сказать, кроме того, что в этом раунде будет 7 различных задач! :)
<almost-copy-pasted-part>
Привет! В Apr/16/2019 17:35 (Moscow time) начнётся Codeforces Round 552 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Наверное, участникам из первого дивизиона они будут совсем не интересны, а для 1600-1899 покажутся простыми. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
UPD: Спасибо le.mur за идею одной из задач.
UPD2: Разбор опубликован!
UPD3:
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | A_Forgotten_Handle | 7 | 229 |
| 2 | fake_delete_pls2 | 7 | 251 |
| 3 | AntiDHero | 6 | 178 |
| 4 | Zhao-L | 6 | 222 |
| 5 | haimiaoyuzhao | 6 | 240 |
Поздравляем лучших взломщиков:
| Место | Участник | Число взломов |
|---|---|---|
| 1 | wzw19991105 | 49:-4 |
| 2 | ScreaMood | 42:-1 |
| 3 | OnlyDeniko | 35:-5 |
| 4 | Hacked_ | 31:-1 |
| 5 | Epitomize | 30:-7 |
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | MonstaKite | 0:01 |
| B | MonstaKite | 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.
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://mirror.codeforces.com/contest/1154/submission/52846244
I also tried to do this, I finished now, FINALLY!!!! The main code is here: https://mirror.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-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".
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://mirror.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 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 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://mirror.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
Can anybody help me with problem E?
Why this code TLE https://mirror.codeforces.com/contest/1154/submission/52858503
and this Code AC https://mirror.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://mirror.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.
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:
You 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 \lt 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.
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.
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.
Всегда мечтал быть среди победителей в блоге раунда...