☀ ☀ ☀ Привет Codeforces ☀ ☀ ☀
Лето заканчивается, а я и моя команда рады пригласить вас поучаствовать в Codeforces Round 894 (Div. 3). Раунд состоится 24.08.2023 17:35 (Московское время). В нём будет 7 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи были придуманы и написаны: diskoteka, pavlekn, playerr17. С идеей одной из задач нам помог Ivang.
Также хочется поблагодарить следующих людей:
Vladosiya за координацию нашей работы
MikeMirzayanov за прекрасные платформы Polygon и Codeforces
michao, induk_v_tsiane, Phantom_Performer, vladmart, dmkozyrev, LordVoIdebug, vrintle за жёлтое тестирование раунда
Zixel, Egorsa, MADE_IN_HEAVEN, Thost, FiniteMoves, mewnya, natalina, Insightful за синее тестирование раунда
artew, tnaito, akwa_blue, Zeyad_Hekal, NgJaBach за бирюзовое тестирование раунда
Желаем всем удачи и высокого рейтинга!
UPD: Разбор опубликован
Привет!
Обожаю соревнования Vladosiya.
В последнем соревновании Vladosiya я апнул зелёного.
Надеюсь в этом соревновании тоже апну!
Спасибо Vladosiya!
Видно, ты очень его любишь)
As a tester, I really liked the problems. I wish you good luck and have a nice day!
thats what they all say
I suggest you eat ice cream while writing this contest. Problems are very interesting!
I think that the following round will be Full of new ideas
Btw what is red blue and green testing?
As a participant I will participate and be pupil again: : : : :
do not have a point of 1900 or higher in the rating.
Should it be 1600?
idk why, but it was always 1900
no
I guess you don't understand what that part means. First, you should probably read the last paragraph of this blog.
From the blog:
-- We will exclude from the official standings of Div. 3 rounds and put in a separate rooms all those who can’t be reliably called to be a real participant. Accounts that materially participated in less than 2 rating rounds (materially means solved at least one problem there) before the start of the Div. 3 rounds, and those who have ever gained 1900 or more rating units will not get into the official standings and will be assigned to separate rooms. However, this does not mean that there is no rating recalculation for them. Thus, the rating will be updated for all users whose rating is strictly less than 1600 at the time of the start of a round.--
In short, everyone who has $$$ \lt 1600$$$ rating will receive rating change after the round, but only some of these participants will be shown in the "official standings". Namely,
These rules are in place to try to make sure that everyone in the "official standings" is actually at Div.3 skill level and not someone much better just having low rating. I think it is more fair to make this rating upper bound at $$$1900$$$ than $$$1600$$$, since reaching $$$\ge 1600$$$ rating doesn't mean you are actually that good (you could've gotten lucky).
rainboy
As a tester, I demand my name in the blue testing list and can assure that problemset is very well balanced and no problem is a cakewalk and wish everyone good luck and recommend to read all the problems
But your name isn't on blue testers within the blog ?
lol people thought I am fraud and downvoted me heavily haha
What about Vika from your last contest
you will find vika in this contest too .. no worries
I'm worried now.
Who is Vika?
Now you know (Given that you have given the contest)
I thought it was a real person
As a participant, I will participate and be pupil again
I have the impression that the contest would take place on 8/26 (Sat.) Has it really been moved up, or did I get the date wrong?
You are correct, it was moved.
I hope I can reach Master AFTER this round :v
XD
Have a nice day >^< bro
hi,i'm from vietnam too.probably i'm younger than you.can i chat with you about solutions,idea and ways to deal with problem?
It's alright, I will provide support in my freetime. However if you want to discuss more actively, I suggest you joining Vietnamese Olympiad in Informatics (VNOI) community. At the moment, they are available on Facebook, Discord, ... There are many experts in CP so that you can ask for help
thank you.can i get the VNOI discord link
Okey, check your DM for the link
As a participant I will participate hoping to be an expert XD
Sauce for artwork
Wish to be blue !!!
I'm really grateful for the opportunity this contest gave me to reach the blue！
I hope to be blue after this contest.
Fingers crossed that this time around, the problems are easy to understand unlike your previous round.
Is that the girl in the blog Vika, which you mentioned in your last contest? Whoes stories were hard to decode >_<
How is it going with Vika
No offense, but pls no Vika in this round
I dont understand what is the Vika Problems? Is it Thanos ?
It is problem A that I managed to solve on 41 minute
I am crying because of interactive problem will be in contest.
Where is it written that there will be ?
The post must've been edited for some reason, I'm also pretty sure that at first it said there was going to be an interactive problem.
Smile :)
hope I'll regain blue soon...
that's not yellow it's orange sir.
.
why you copy others comment copied from Noobish_Monk
What does red/green/etc. testing mean? I thought, tests are the same for everybody
Hoping for great div3 contest__
Yall will like the problems.
.
Did you even read the announcement?
If your rating is less than 1600, then the round will be rated for you.
Hope to become an expert!
I am so excited
Hope my color will change after this round . Lets go !
It will...... .......................................... .......................................... ............................ ............................ ............................ ...................... be green hh
Really hope to reach pupil this time!
good luck for everyone :)
((upvote) ? rating++ : rating--); I HO
:(
I can't wait, I'm so excited about Div 3
So many Yellow and Blue testers for a cyan, green & grey round
form last
diskoteka how is your vika now ? after reading last contest's problem statements
This is my first time being a tester, I am very excited and wish everyone perform well in the contest :D
Expert round?
Maybe.
35k participants
why 'custom invocation' not working ? (: diskoteka
he can't control that , even mike can't , it's not working as it is contest time and too much pressure on the judge
Good contest, enjoyed it !!
when it's bout div.3, diskoteka never disappoint us.
gg, this was my first contest and i didnt know what to expect from it. The questions were great, but my solutions aren’t(had to scour over StackOverflow for a few places...). but congratz!
<333
Tough C.
For some reason my solution to A got all different outputs than what I got when I ran it on my PC, lost 2 hours because of that, is that normal during contests or was that some kind of bug? I switched to C#, wrote the exact same code and it got accepted...
Your uzeli array is uninitialised so has random undefined contents on each run.
then why did it always work on my PC? So basically I had to set all values of that array to false?
You got lucky I guess (different compiler / optimisation settings may produce different results). It isn't worth trying to work out why it works sometimes when you have undefined behaviour, just fix the undefined part and it'll work everywhere.
if you declare it as
bool uzeli[m]{};instead ofbool uzeli[m];it will be default initialized (which for bools is all false).Having spent lots of time for E because of the third test case, that's really confuse because of the note. I got AC because of predicting the actual problem LOL.
1，3，5，6 ? 2，3，5，6 ? I was totally confused during the contest :D
Yes, it really pissed me off.
D is on oeis:(
what is error in this code For Problem F https://mirror.codeforces.com/contest/1862/submission/220289269
your template.
mid=(lo+hi)/2forcesYes solved the problem D with quadratic and got WA, and I know it time to use bi-search
D can be solved without binary search.
Here's my submission — 220221455
can you please explain you solution. thanks in advance :)
If you observe carefully there is a pattern in the solution — 2,3,3,4,5,4,5,6,7,5... So it is like -
2,3
3,4,5
4,5,6,7
5,6,7,8,9
and so on
If you solve the equation nC2=r, where r=required number of different ice creams, you will get n = (1+sqrt(1+8r))/2, so just calculate this value if it is an integer it will be your answer, and if not, then it will be the first number of the row in which your answer is present so just add the diff between r and the value for which you got the answer which you can find by simply putting it back in the formula nC2 and that will be your answer.
Sorry if I was not clear, but the main thing is finding the pattern and the quadratic then you can solve this question.
bro but in sample test case 4 for 179 why do we need 27 , by nc2 it can be wo also right because 20 c2 is 190 more than 179
In question D. it is given that exactly n type of ice-cream has to be made, not greater than that not less than that. for test case 4 answer is 27 because you need 19 unique ice-cream flavor and 8 repeating flavor. e.g. 1,1,2,2,3,3,..
19c2 = 171.
since you have repeated 8 flavor you can make 8 unique combinations of (1,1),(2,2) ....
That’s what I thought too. I spent like half an hour tryna understand until the general announcement then got AC right away
Extremely short solution without binary search: https://mirror.codeforces.com/contest/1862/submission/220208197
I cannot get the test details in E, can you help me what wrong with my code ? This is my code
:(( I know I cannot get more rating after this contest :(
Do you fully understand the statement, that's confuse. If you are, the problem is just maintaining a priority queue to keep track of the largest value, and maintain the size of queue to be less than or equal to m.
I think the problem is that d*i can give overflow , when you're calculating res
Thank you Geothermal for this trick while using bitset.
I don't know if problem C was actually confusing or maybe I'm dumb enough not to understand it.
Can someone hack this F solution for the case when water and fire > 1e5? https://mirror.codeforces.com/contest/1862/submission/220284156
solved G after 2 min end of the contest(
for D i noticed it's . find the nearest lowest X for X choose 2 then add n-(X choose 2) . but since it failed on the last test since it's a very big number so is my logic correct and bad implementation? Edit: ok nvm i was an idiot and made r in the binary search n not 1e9 :).
Good problems!Thank you! And I want to know is there any brute force ways for F?I got wa using my brute force way :(
Problem D:
I used binary search on k, trying k choose 2. If I found kc2 == n, answer is k.
If such a k does not exist (for example, n = 7), I found the greatest k such that kc2 < n, and then added duplicate balls. So for 7, 4 choose 2 is 6, add 1 duplicate ball (e.g. {1, 1, 2, 3, 4}) to get 5 as the answer.
This strategy worked for test 1 but not test 2. During the contest I believed it was a binary search bug but now I wonder if this strategy is valid.
Yes it is a valid strategy. I solved D using same approach.
I did the same thing tho https://mirror.codeforces.com/contest/1862/submission/220247861
Just got F a moment after the contest ...
Here is my Live Screencast of solving problems [A -> F] (with commentary in HINDI).
PS: Don't judge me by my current rating :(
Nice problemset. Thanks for listening to the feedback on last round and made your contests better . Loved D
Can someone hack my F. 220282299
How could problem E be approached? What I observed is that we optimally must select the shortest continuous subarray starting at 0 because we will always remove -d * len(a), where a is that subarray. Then we can pick maximum $$$m$$$ positive values, but how to determine the length of that subarray? Would a priority queue work and at each index check the maximum m values + -d * i?
You don't need the shortest continuous subarray. The answer is maximum of: for each position sum of the greatest m positive elements to the left minus the position multiplied by d. If you get more than m positive elements to the left, you just erase the minimum of the set or the priority queue and update the sum.
F is an interesting dp problem. Unfortunately, I was not able to solve it for the limited time.
My F solution was Iterative dp with memory optimisation
Same
I used knapsack to solve F, gave me a very easy implementation!
lognforces
another step back?
yes but prove him wrong!...
220296987
What is making my solution slow for G? (time limit exceeded) I would want to hear some advices on how to use sets and what to avoid to not get tle in the future.
I had a similar solution, mine was segmentation error (I believe to be memory exceeded)
Thanks for interesting tasks! A was too hard for me)
Nice problemset.
Most confusing problem "D" :) && Besides lots of announcement increases the confusion level further except clearing.. ConfusingForces
Hey Cheater, why have you inserted unnecessarily string/char etc. in your code of D.
Could you point out the unnecessary string/chars you saw in his code? If you are referring to blank lines, they don't matter anyway. Could you clarify what part of the code made you believe the person you accused a cheater is actually a cheater?
Nvm. Very my fault for commenting without checking the problem of the solution. Thought it was this Contest's D.
I am not sure if you and the accuser are the same person. But accusing someone a cheater is not something we should take lightly. Your reasoning of accusing someone cheater because you thought the code was for this contest is not only unacceptable but also unforgivable. At least check the problem ID before calling out someone a cheater. Anyway, I hope you have learnt from your mistake and would take this seriously in future.
I didn't accuse him. I literally specified it in the previous version that I neither accuse nor defend.
If "Hey Cheater" is not accusing someone a cheater then I don't know what does accusing means. Anyway, I am not quite sure why are you replying? Are you and ccpp same person or distant cousins?
I have no idea who he is, but I didn't say "hey cheater" in any of my comments, in the CF history of this account.
My bad then, I think you should have replied in the separate thread. Cause, my question was specifically to ccpp. And I did not get any answer. Your comment confused me.
Sorry, Actually I went to saw Sol of D in his profile (submissions) then I saw this soln. I did not realize that the soln was od another contest and presumed that he had done it to pass plagrasims. I am extremely sorry to have created this confusion.
i knew that grays dont have brains. i was unaware that they cant even see properly
Extremely sorry bro, I mistakenly thought you cheated. Sorry please forgive me. Sorry Again.
It's Ok bro.. Understanding the coding aspect is enough.
That's actually not unnecessary strings/char. That's called template. We mainly use it for writing code faster in contest time, Cause you already know your coding speed will impact your contest performance
My solution for F is slight different from others, I binary searched on time, and got amount of fire and water. Now if any of these is greater than sum, this time works. Else, I try to fill knapsack of fire in most optimal way, (by optimal I mean, filling it in such a way that it has least remaining space possible) and check if remaining sum can be filled in water knapsack. Similarly, tried to fill water knapsack in most optimal way and check if remaining can be filled in fire knapsack.
Here is link to submission
if((sum-dp[F]<=W)||(sum-dp[W]<=F))You only need to check one of these. Suppose
sum-dp[F] <= Wis true:dp[F] is the sum of a subset of monsters
sum - dp[F]is the sum of the remaining set of monstersSince
sum - dp[F] <= W, we can kill the remaining set of monsters with W. In other words,sum - dp[F] <= dp[W].Therefore,
sum - dp[W] <= dp[F] <= Fand the second statement is true as well.The same argument applies if you want to prove the second statement implies the first.
i did the same
Hello, can someone provide a hint for problem E
Thanks :pray:.
Lol i thought it was question F nvm mb
Try to think of what the final cost/result looks like if you know which indices to choose.
Now try to think of which indices will give the best cost.
Have a good day!
Video editorial for problems A&B&C&D: https://youtu.be/aEB8NXX-lxA
Thought would be useful
IN ENGLISH
Great problems, D and F were really interesting, and E was also nice. Hope to get to expert after the rating changes :)
In problem F, I've seen many solutions that use this bitset idea, but I'm just lost at what it does.
Can someone explain what it's supposed to be happening here?
this is the equivalent of
for i from 1 -> n:
for j from sum -> a[i]:
dp[j] |= dp[j — a[i]]
generates all subset sum which are possible.
OK, I think I got it!
For the interested:
dp[amount]should be $$$1$$$ when we can formamountby summing some elements ofstogether, and $$$0$$$ when we cannot.Therefore
dpshould have enough size to store all possible different amounts. In this case, from $$$0$$$ to $$$10^6$$$.Initially
dpwill have all values set to $$$0$$$ (we don't know yet which values we can form), except for the $$$0$$$-th bit (we always can sum up to $$$0$$$, just choose no elements from the set).The line that sets the $$$0$$$-th bit to
1is:dp.set(0).Then we iterate over all elements of our set. Say that our set
sis{3, 2}.In the first iteration of the
for, we know that we can forms[0]— that is, when we choose only the first element to form our sum — so we should set thes[0]-th bit ofdpto $$$1$$$.After the first iteration, the $$$3$$$-rd (and $$$0$$$-th) bit of the bitset will be $$$1$$$:
dpequals00000 ... 0001001.In the second iteration, when considering
s[1], we know that for each value we already know we can form, we can also form that value +s[1]. Since each bit already set indprepresents a value we know we can form, by left shifting each bit $$$1$$$ ofdpbys[1], we get all new values we can form.In the example, since
s[1]is $$$2$$$, by shifting all bits ofdpby $$$2$$$, we have:dp << 2equals00000 ... 0100100(now we know we can form 2 and 5).By using
|betweendpanddp << 2, we join all the values we already knew we could form and these new values we just learned we can form:dp |= dp << s[1].dp|=dp << 2equals00000 ... 0101101(we can form 0, 2, 3 and 5).The same idea for
s[1]is valid for anys[i]that comes after, and after thefor, we know all values from $$$0$$$ to $$$10^6$$$ that can be formed, since they're set to $$$1$$$ in the bitset.There are probably better and shorter explanations elsewhere, but since this is a Div3, I think it means no harm putting mine here.
I found prblem F and C very cool.Nice contest
It's very unlikely that 1000 people will solve F during contest, I think heavy cheating is going on maybe those Unofficial Experts , CM, M.. provide these fellow cheaters the solution :(
F wasn't that hard to be honest. I needed around 30 minutes to solve it(spent 10/15 minutes on E after solving C). I immediately had the binary search plus knapsack idea. But wasn't really sure if it would pass(I was thinking about normal knapsack not the bitset one). Then I was able to reduce it to only knapsack without the binary search.
I participated virtually though!
What's the t.c. of bitset idea? Is it O(sum + n)
O((n * 1e6) / 32 + n)
can you explain it please.
performing an operation bitset has a time complexity of n / 32 or n / 64 depending on your computer, but in codeforces it seems like it is 32.
we iterate through every number, then we take the whole bitset and we perform OR operation with (bs << val), this takes O(ceil(SIZE / 32)), SIZE in this case being sum which is 1e6.
we do this n times, which gives us the total time complexity of O(n * ceil(SIZE / 32)) or O(n * 1e6 / 32)
I think you meant OR operation. Anyway, thanks for the explanation.
yes, my bad, thanks for the correction
I was also surprised
Python users, for Problem G anyone knows the source of this SortedList template 220199018? (huangxw, yuki_keshiki)
I was getting TLE with the PyRival implementation.
I copy the SortedList template from someone's submission in Atcoder contest，it is crazy fast，prefect to solve this problem.
White spaces and endl seem no difference to checker. 220288316
yeah , I never use " " , I always use "\n" and never had a problem.
4 1 2 3 4
and
4
1
2
3
4
both are correct almost always
Cool! I knew that trailing spaces do not count. But never knew that new line is also fine. No more space handling from now, then.
Can problem E be somehow solved using binarysearch?
Yes. 220222897
I did the same thing but rather than using binary search i directly find ans using n*(n-1) = 2*x but not sure why it is failing in test 9 https://mirror.codeforces.com/contest/1862/submission/220283634 any idea?
My solution also failed at test 9. I suspected that it has something to do with the precision of the sqrt function. So I just took the floor and subtract 1. Then run a loop until k*(k+1)<=2*n. I saw some people got AC with sqrtl in C++. Not familiar with python's precision. But maybe something you can check.
I have modified your code and it’s accepted. 220375579
Thanks, sqrtl seems to work fine https://mirror.codeforces.com/contest/1862/submission/220339038 but not sure why same python code not working :( i thought python has much larger precision than cpp...
Hey everyone, I'm a newbie. I want to ask why this round is not rated for me. Thanks.
I remember after hacks there is system test later.After that,it will be rated :)
the observation, maximum difference between adjacent elements of the array for problem G is damn cool !!
Why are the rating changes not out yet, hacking is over right
There is always the daunting 2-3 hour wait after system tests before rating updates. Hoping to get pupil, I’m at 1199 right now!
That’s great congrats
And I just noticed that you’re two points away from specialist. Congrats to you too!
nice contest i like it , F problem is so goood
where is the systerm test?
Can E be done using sliding window?
But you need to kill all monsters, not just a subset
Hope to reach pupil after this contest. Solved 4 problems
Same! Hopefully both of us get pupil
А почему в рейтинг не засчиталось(
Идёт системное тестирование. Терпение:)
Why don't start system test immediately ?
Why don't start system test immediately!!!!!
Why don't start system test immediately ?
I am a python user but I dont know what is the alternative of multiset of C++ in python?
I guess you can use heapq as an alternative
Good round in total, but problem A is very boring, problem D and F are a little boring, the others are interesting!
Now i have become expert the destroyer of division 3.
NICE! Congratulations!
commented on a wrong round sorry
Lmao I binary searched on F and created a dp table every time not realizing I could've just created a big one to start. Oops.
Attention!
Your solution 220250441 for the problem 1862E significantly coincides with solutions wont_give_srsly/220246281, manvendrasinghshekhawat/220250441, bdyby11/220257824, pmqwerty/220262992, Swarupa/220264041, pranavkumarreddy567/220268055, DarkDreamin/220269225, nitiksharma/220269800, jvamshi36/220271912, jolly_79/220273460, Tintintani/220275635, absolute_07/220277807, jkoushik_iiitn/220278018, abhay5a/220278945, anjan_reddy/220279911, kunaltelangi/220280520, Mobbbbb/220281738, i_decided/220284890, Adityaraj834/220285184. Such a coincidence is a clear rules violation. Note that unintentional leakage is also a violation. For example, do not use ideone.com with the default settings (public access to your code).
I recently received this mail stating that I was accused of plagiarism for a problem 1862E. I didn’t know any of these people nor did I share my code with anyone or use any online ide. I am 100% sure that this violation has not happened from my end.
I have personally looked at all the other submissions and none of them match exactly with mine other than using ‘multiset’ and the problem logic. I request you to please check again MikeMirzayanov.
My Submission: 220250441
Other Submissions:
220246281 220257824 220262992 220264041 220268055 220269225 220269800 220271912 220273460 220275635 220277807 220278018 220278945 220279911 220280520 220280520 220281738 220284890 220285184
please update the problem ratings, it has been more than 20 days since the contest is finished and yet problem ratings are not updated.