Обратите внимание на необычное время старта раунда.
Привет, Codeforces!
Во Mar/19/2024 11:05 (Moscow time) начнётся Codeforces Round 935 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. Задачи подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 8 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу)
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Задачи основаны на олимпиаде ВКОШП.Junior. Авторы задач: Kirill_Maglysh, NToneE, Gadget.
Большое спасибо:
Vladosiya за прекрасную координацию раунда.
nigus, Gheal, KKT_89, Noinoiio, systy, FBI, SiERic, moonpieXXIV, nik.danilov, JuicyGrape, Pa_sha, FedShat, an_na, khaser, MountAim, Boris_Ber, PUFL, blook, yakuri354, iluminat_Btopou_AkkayHT за тестирование раунда.
gurovic за ценные комментарии по условиям задач.
MikeMirzayanov за системы Polygon и Codeforces.
Всем удачи!
UPD: Разбор выложен
Auto comment: topic has been updated by Kirill_Maglysh (previous revision, new revision, compare).
Автокомментарий: текст был обновлен пользователем Kirill_Maglysh (предыдущая версия, новая версия, сравнить).
Different start time.
Thanks! Added to the announcement
Pay attention to the unusual round start time. ,hmm but whyyyyy, dont we deserve a reason -_-
The round is based on an onsite competition mentioned in the announcement, which, unfortunately, could not be postponed to the usual round start time :/
my bad i didn’t notice, thanks
Yay! Div3 Round. Note the unusual time!
same =(
As a tester, I tested some tasks
It's on my birthday!!! But I have to go to the school ... T_T
I see you are from china.It's astonishing to know that you are CM and still going school lovely_cyc
Hope to bring my rating back after this round
Good luck for everyone!
Agree with you
if i dont submit anything or may submit the first one,will my rating fall?
Any submission results in a rated contest. It won't be rated if you did not make a single submission tho, even you registered beforehand
Why is the timing so unusual? Problemsetters please try to hold contests in the regular times only as it's really inconvenient for people studying in universities(as most of them are students) and it's quite difficult to make it on a weekday on such an odd time.
CF Round >>> School/University 2hr lecture
Definitely, but low attendance == repeat course == :(
make good friend == do proxcy == problem solve
College uses biometric attendance machines == cutoff thumbs to give to friend for proxy == slow typing speed. Problem created.
1hr contest reset 1hr mid semester exam
maybe the olympiad will be hold at the same time
as a participant of the olympiad, it is held at the same time
good starting time...
I want to author a Div.3 , how I can do ? Vladosiya
What an unsual time! Maybe there will be less participants than usual days orz.
Cf round >>>>>>> school
Sleep schedule ruined enough to the point where a 1 AM contest will not affect my mental state. Good luck to all my fellow competitors, and may you gain a cool new color!
Автокомментарий: текст был обновлен пользователем Kirill_Maglysh (предыдущая версия, новая версия, сравнить).
Wishing everyone a great round and a positive delta !
I appreciate the unusual start time, much more convenient for me since contests are typically at 2am for me. You guys should do this more often :)
I am excited about Div3 but this time wont allow me to participate
School Time here in China :(
School time at 4:00 pm :skull:
(I hope that the school starts late right?)
If you see 7:30 a.m as an late time, then you are right.
:skull:
SPEEDFORCES!
speedforces!
Thanks for this "unusual time". In the month of ramadan this time is perfect for me( from Bangladesh)
also in Iran. for the usual timings, Iftar is at 18:30, and the round is at 18:05. it was really hard
fun fact!
today is the last day of the persian calendar (I guess it's called new years eve)
so, if the round was at it's usual time, most of persian users couldn't participate, so thanks for this
love from Iran, Happy nowrooz <3
What an unusual start time! But it's suitable for Chinese students.
great questions, but I wonder if problem setters intentionally make div3D easier than div3C most of the time. Problem C took way too much time to understand and implement.
How to do D ?
DP
Why DP if greedy works?
Assuming $$$f(i)$$$ is the minimum cost to stand at exactly position $$$i$$$, we have $$$f(i) = a_i + \sum_{j=i+1}^{n} min(a_j, b_j)$$$.
The answer will be the minimum of $$$f(i)$$$ under $$$1 \le i \le k$$$. All $$$f(i)$$$ can be calculated through a linear iteration of the array from $$$a_n$$$ back to $$$a_1$$$.
Nice solution, I tried to think in greedy way for some time and then gave up and settled with DP
At this point I don't know if this solution of mine is classified as DP or greedy :D
Kinda a mixture of both, DP in the way speeding up the calculation, greedy in the fact that $$$a_i$$$ and $$$b_i$$$ can interchange freely in the background without damaging the solution's validity.
while i > m, if a[i] <= b[i] jump to i
then find i <= m, with minimum cost of jump
Announcement for C was given only after I asked about n/2 being floating point number. Explanation could have been better, wasted so much time in C due to that
But overall problems were good. Not too easy. Even A and B required some math work.
Problem Statement of B and C was not good. Especially C
C makes me want to kick my keyboard.
Unusual timing and kinda tough.
C makes me want to broke my keyboard.
how to E
Follow the given algorithm strictly and at last swap positions of l and x's index
Why this works can you give idea or intuition
At all mids,
If p[mid] <= x, l=mid else r=mid;
So, basically you have to find what is the last index where l was updated.
and in some cases, l may not be updated at all, there after simply swapping the l's position and x's position will make your array valid.
please, bro, explain me : when the last ind you updated is greater than target and in between the process mid come to our target. now if we swap last ind and target then mid again comes to the last ind and moves in the wrong dirn because initially the num is =target but now it it > tar. in between my code got accepted without thinking this how i am still confused.
From my code,
https://mirror.codeforces.com/contest/1945/submission/252251419
I will not actually swap them
First I will let this loop run
where my l is getting updated only if p[mid-1]<=x
ll l=1,r=n+1;
while (r-l>1)
{ ll m=(r+l)/2; if(p[m-1]<=x){ l=m; } else{ r=m; } }and now after breaking out from them loop I will not care about the r. I will only think about the l.
Now if l == target's index then no problem else swap is required
so the answer will be
1 l target's index
Repeated this process until found a solution:
Please tell about it here https://mirror.codeforces.com/blog/entry/127381
C was implementation heavy....
before the edit, there were multiple solutions that they didn't accept.
I did it after the announcement
Ignore this comment. Deleted the tutorial, will wait for open hacking phase to complete.
god is back
Got the idea of problem E in just 10 minutes and the rest of the time passed just doubting myself that it cannot be this easy!!!
sorry to say, but the worst div3 statement i've seen in a while. It's just a troll if you don't have even the basic knowledge of english and you just set a problemset with whatever you want. Just a waste of time
agree
problem C was so hard to understand, atleast for me
B,C and H are the most awful problems ever.
What's wrong with them?
worst div3 ever seen
What an Extraordinary, Mind blowing Fantastic steps!! Tutorials please, Sir tickbird.
Skill-issued bird. Why don't you comment from the ac that part in the contest?
" had to use std::lcm for some reason, waste hour and 4WA until realize overflow :( " ?
jinsu
good Python job
statement of c was not clear at all
Man B & C was laden with the weight of implementation intricacies.!!
I beg to disagree. I would say that B and C are somewhat odd than usual, partially wordings, partially mathematical involvements, but implementations for them are nowhere near intricate.
Master, are you taking my comment personally? You see I am not as skilled as you Master. I am a newbie in Codeforces parlance. So I'm not as good at simple thinking & solutions as you are, Master.
Firstly, I think I should apologize if my words somehow felt like a personal attack. I never meant it that way.
Secondly, however, I do think my point still stand. Of course, there will be an observable bias coming from me, with more experiences around. However, I do understand where you are coming from to counter-argue, as I had been there (or so I thought).
For the problems themselves, B is a straight-up math problem, and C literally asks you to do whatever it tells you to.
Of course, it's not that easy at a glance for newcomers: B's nature might seem dodgy to code at first thinking of how to fit the timespan, or is it required to explicitly define the optimal timespan; C — for now we ignore all the problem statement issues — looks confusing for newer contestants for maintaining the left and right side of the split.
Still, what I wanna say to defend my point is, it's possible, and very likely, to generalize and abstract your thought process for a clean execution. The mathematical nature of B makes it a three liner if you understand how the math works, C is much cleaner to code once you could visualize how the states of the two sides change when we move the boundary.
Of course, you don't have to take my thoughtstreams above all at once. One thing, you need to develop your own. Another, it's a steady learning process. You'll get better the more you spend your time thinking and improving. For now, I only state what I did at the original comment, as an opinion that what you have witnessed in your experience is incomplete — I won't say mine is already complete and perfect, but at least today I could cover yours a bit.
Is it just me or today's G and H are worth Div2E at least...?
I was quite close to clear G, but cannot really make it — I thought it was just simulating the process but the initial queue order screwed me over.
I guess G was pretty tough considering jiangly took almost an hour to solve G
Definitely, clist rates G at 2593 and H at 2766.
Holy hell, no wonder....
It's nice to hear that, since I solved H in the contest. But my solution was so simple that I think the difficulty of H will be at most 2200.
UPD : I have posted my solution in this comment.
I think you don't understand how problem difficulties work.
I do, div3 problems get a lot of time after the contest before they are assigned a difficulty, there were a lot of problems in this contest and so most of the people could not reach H. I think in 2-3 days, it will have more than 400 solves (and of expert — CM range people (that's how problem difficulties work, right?)).
https://mirror.codeforces.com/blog/entry/62865?#comment-468443
Oh, I haven't read that.
I have read this blog though https://mirror.codeforces.com/blog/entry/126799.
I don't know if its a special case that if nobody solves the problem during contest then after the contest submissions are also considered (I'm talking about the 1919H case)
can u explain ur solution for problem F?
Maintain an ordered set of shrooms with nonzero magic power. There are two operations: remove a value and find k-th maximum. ordered_set supports both in logarithmic time.
How did you solve F?
i thought it's a ternary search...
Basically, you do what you are told to greedily.
Loop through all $$$k$$$ that satisfies $$$2k - 1 \le n$$$, each $$$k$$$'s answer will be the $$$k$$$-th largest element over the unaffected indices multiplying by $$$k$$$ itself.
To maintain the elements properly, we can make two BSTs (or more regularly streamlined in C++ STL as
std::multiset), one for the available elements, one for the already chosen one. Choose the largest element from available and throw it to chosen for the act of taking mushroom, and erasing element from either multiset (prioritizing available over chosen) for the act of "cursing".My implementation, for reference: 252244274
Thank you
Can you tell what is wrong in my solution? This is my solution for F.
Can't tell at a glance, but if your
ititerator is meant to get the max value around, is it a little bit too dangerous to let it "hang" around with all those multiset insert/erase calls?Maybe consider renewing it every time you need it. I don't yet see any other suspicious code, but stay alert while debugging.
How is the ans for the third test in problem F "8 2". Shouldn't it be "6 2"?
we are picking mushrooms with strength {4, 5}, min = 4, and there are 2 mushrooms so ans = 4 * 2 = 8.
Honestly, I was irritated due to very less or no notes in any of the problems.
Ramadan Mubarak Brother. I got it.. thanks!
a lot of people solved b : (m * 2 — m) / a + (m * 2 — m) / b + somethings and no body will know why LOL
pattern recognition from test cases
how to guess (a/m) + (b/m) + 2.
it's so hard
try this m=m+1 and then ans= ceil (m/a) + ceil(m/b) ,it will be the answer Reason: Consider the [a,a+m] and [b,b+m] to be included by incrementing m.
tq
https://imgtr.ee/images/2024/03/19/8f04bf5b44e908e9eb17be606d4e3021.png
this is the second test case in the first sample
the first line for the first installation
and the second line for the second installation
just notice that in the first line the fireworks firing at time 3 will end at time 13 so any one which will be fired before or with in the 13 is included
that's how I figured it out I hope it helps
thanks
The number of fireworks from an installation at any moment first increases and then becomes constant. The sum of these constant values from both these installations is the answer.
This constant value from first firework is equal to (m+a)/a and from second firework is (m+b)/b. You just need to sum them.
Can anyone give me intuitive understanding that why Following the given algorithm strictly and at last swapping positions of l and x's index is correct for Problem E?
Consider 2 cases, whether the target is among the elements visited by binary search.
If not, we can just swap the last l index with the position of the target since that will not change the search sequence itself.
If yes, we see that swapping the order of any p[m] <= target will not affect the search sequence, since we are setting the left limit regardless every time.
Still not understood the Yes part. Can you please Elaborate.
If $$$p_m \le x$$$, assign $$$l = m$$$.
Say we pick two indices $$$i, j$$$ from the visit sequence such that $$$p_i \le x$$$ and $$$p_j \le x$$$. If we swap $$$p_i$$$ and $$$p_j$$$, will the visit sequence change?
To add on to this, if $$$x$$$ is in the search sequence and is not $$$p_l$$$, then on the final time we set $$$l$$$, $$$p_l \lt x$$$. We can apply the previous statement to these two indices.
What if a[l]>target and target is visited ? In that case, search sequence will be altered ?
p[l] can only be larger than target if we have not visited target, since we only set $$$l = m$$$ if $$$p_m \le x$$$.
I used this logic during the contest and got WA on test2. Did your solution pass ?
I looked at your submission and I think you calculated m incorrectly. I submitted your code with this change
ll m = l + r >> 1and it passed. link
Generally, you would do
l + r >> 1for calculating m, but to avoid integer overflow you can dol + (r - l >> 1).Yeah, you are right. Unlucky me. Thank you for your help.
The 'm' value that you're talking about should not be visited as mid value in the Binary Search, Right?? So we have to pick that index 'm' that is not visited during the binary search as well as it satisfies the condition p[m]<target.
How are we sure that one such m will always exist???
The m I am talking about is the m in the problem statement. If we visit the target index during the binary search, we can always switch it with the last time we set l (see logic in previous comment).
First I assume that you are saying why this works, swap(1, position(x)) and then swap(1, l). or n instead of 1.
Consider the process of binary search. It goes to mid then maybe to right or left and so on, let's say we marked these positions where our mid went. Now, binary search will stop somewhere, why don't we just put x on the last l? because x might be somewhere that our binary search marked and when we replace it with the element at last l, it might change the sequence of our binary search, and then our replacement will not make any sense. But, what can we do is that we first put x at position 1 (or n). What will happen is, either it is itself last l or it does not occur in our marked positions. In both cases we are happy, now we can just swap(1, l).
UPD : Now, I get your question, my friend also told me this solution.
If x did not occurred in our binary search sequence (marked indices in the first solution) then it's easy to see that it will work.
Now, x also occurred at some position. All we care about is about the property that a[mid] <= x, when we came at the position of x we said that ok a[mid] <= x (actually = x) and then we went beyond to some other positions after that, but now if l was moved from the position of x, then the new positions it moved through were also <= x. So, when we swap(x, a[l]) then the properties does not change. The elements from which l passed through are still <= x. Hence, this solution works.
Thank you for the two-swap solution. I was wondering why two swaps are even allowed when it could be solved with at most one swap so easily. I thought it was meant to mislead us, haha.
252273129 It is the solution for Problem D.I don't know why I'm getting wrong answer on test case 3,jiangly approach and my approach is same even though I'm getting WA.Please help me to find the mistake.
You defined
intaslong long, howeverINT_MAXstays at its original value i.e. $$$2^{31}-1$$$, which might be smaller than the actual maximum possible answer of around $$$10^{14}$$$.Contest authors:
💯
the quality of the problems are comparable to div 2 ones really nice ones
Overall didn't enjoy the contest. Problem A was ok, for B I didn't like the method. A and B could have been swapped. C was horrible, I had to read the problem statement 4-5 times. There was some clarification about not rounding up n/2 was weird. I feel you were going for a heavy implementation round to make the problems more difficult, sadly I am not a fan of it. D and E were smartly designed and I have fun solving them. But for E, I didn't like how I had to put seed values as 1 and n+1...like I spent 20 mins to figure this out, which I felt could have been improved.
What is done is done. Thank you for the contest! I appreciate your efforts for the round <3.
Очень качественный раунд на самом деле, хороший Div.3
https://mirror.codeforces.com/contest/1945/hacks/1006163
~10 mins after the contest was finished, I realized I forgot to handle one case lol. This submission should fixed it. Anyway, my screencast is still processing and will be available here.
Hello could you give me the case which you used to hack your solution?
for D just a easy greedy! XD
Bro sent the code as a link or spoiler
This contest was an undercover div 2.
Problem Statement of B and C was not good. Especially C(2)
reading >>>> div1
In D-Question, (considering 1based indexing), how does taking the sum of indices m+1 to n inside the min variable actually matter?
My code(give WA on tc3) Code
Correct code Code
By just taking the ans variable out of that min part and directly adding, problem gets fixed I get it that it is more simpler, but I want to know why taking it inside the min part gives problem. Thanks in advance for your help.
i think it is because of the INT_MAX. You should have used 1e18.
Yeah got it, thank you.
The problem setters of this round have to enroll English course as fast as they can.
either bro is too smart or bro is alt id of MikeMirzayanov
check this out
In C, n/2 is not an integer division could save my 1.5 hours
same lol 2 hours and 1 wa still didnt get
My bad I didn’t notice, thanks
Why did you decide it's an integer division? Skill issue
Problem E (Binary Search) Video Editorial : (Audio : Hindi)
YOUTUBE EDITORIAL LINK --Click Here
it should have been 2:30 or 3:00 Hours contest , 2:15 wasn't enough
Does anyone know why my approach for G is incorrect? Basically I'm using a priority queue to check whether there's someone who already ate with higher priority than the current front of the original queue. I take the appropriate first guy and then schedule its insertion to the priority queue. I'm taking into account order of insertion when multiple ppl are to be inserted at once so idk what's wrong.
https://mirror.codeforces.com/contest/1945/submission/252292126
Nvm I'm stupid
H problem hint please:
i concluded that its enough to choose 2 elements for gcd and rets n-2 for bitwise and.. not able to proceed further.
I've added hints for H : GCD is Greater on CF Step
Fact : we only choose 2 elements for gcd.
We can say if we pick more than 2 then we can just shift them into AND and then it will be better, since gcd will increase or stay the same and AND will decrease or stay the same.
Now, think how can we use this that all of n — 2 numbers are in AND and only 2 in GCD.
When we pick 2 numbers for gcd, how does it effect the AND?
Think about cnt[bit] = number of elements which have this bit off.
What happens when cnt[bit] > 2? What happens when you pick 2 elements along with this condition?
It will be off in our AND, no matter how we choose 2 elements for gcd. Now, what to do if cnt[bit] <= 2?
Think about brute force. How many numbers are there which are troubling us (not making our AND determinable)?
only 2 * LG, since cnt[bit] <= 2, then those are troubling us. We just check them by brute force. After this, we will never put them in our GCD. What now?
Is our AND determinable now?
Yes, if cnt[bit] > 0, then this bit is surely off, otherwise it can't be off (since all of the numbers contain this bit). Now our problem is just gcd(x, y) > X (where X = fixed_and + x).
Complete Solution
I haven't implemented this yet, but I think it should be fast enough:
For each integer $$$1 \le x \le M,$$$ construct a list of numbers in the array which are divisible by $$$x$$$. Then, for each $$$g$$$ from $$$1$$$ to $$$M$$$, solve the following subproblem:
"Given a nonnegative integer $$$k$$$, choose all except two integers from an array $$$b$$$ (which in our case is the list of integers constructed for $$$g$$$), so that the bitwise AND of $$$k$$$ and the integers is minimized." We can solve this by going through the array and choosing one element to not take in $$$\mathcal{O}(\text{size})$$$ time, and each time going bit-by-bit to determine the optimal choice for this particular bit. I'm not sure if this is fast enough, but constant factor is probably not bad because it's just bit operations.
Beware whites , nigus is testing
in problem C: i have read the statement 10 times and i am still confused why in 4th test case answer is 3 and not 2
testcase ->
000
omg on each side never mind I thought half of the residents in total should be satisfied!!
For the problem F, can I know the answer for the following test case? 4 2 7 8 10 2 3 1 4
The number of mushrooms are 2 that's ok but how it says the answer is 16. In my logic, I'll pick 2nd and 4th mushroom because [1, k-1] elements will be power 0 then the answer will be 14 which is maximum possible. But the expected answer is 16, i think they picked the 3rd and 4th mushroom. But my question is if I pick 3rd element then power of that element becomes 0 as P3 = 1, which is < 2. Now, am I wrong to understand or i am missing something? Can anyone help me?
252362491
What is wrong in this solution of problem F?
Can anyone explain ?
I had the same problem.
See this case:
The answer is
10 2, not14 2.That's because we remove the elements with indexes $$$p_i$$$, like, choosing $$$k = 2$$$ mushrooms, the magic of the element with index 3 will be zero, because $$$p_1 = 3$$$, so the array will be:
It's not the one with index $$$1$$$ or the element with $$$p_i = 1$$$, it's
v[p[1]].This is so confusing, the samples don't have cases like this and the notes don't help.
Honestly, the problem is good, but I don't know why doing these things just to "overcomplicate" a problem. It's not harder, it's just boring.
When will the ratings be out?
Is system testing done?
i think yes
I didn't get B. If both are starting at the same time, then ans should be infinity. Can somebody explain.
That would just be $$$2$$$ simultaneous fireworks. $$$a$$$ and $$$b$$$ are at least $$$1$$$ so two fireworks of the same type would be at least $$$1$$$ minute apart, rendering them unable to stack indefinitely on top of each other i.e. we always have a finite answer.
sorry bro, i didnt get. Could you please explain with an example. for example 1 1 1.
In this case both will fire at 1 min then again 2nd min and it will go on. And they are visible for 1 min. So it should be inifinity.
The problem was about what is the maximal possible amount of fireworks visible at one moment. Also for any a and b, both fireworks will start simultaneously at lcm(a, b).
Imagine getting hacked for not commenting the debug statements.
Codeforces definitely needs an option to redirect stderr to /dev/null.
Системные тесты прошли?
В диве3 нет системных тестов, все решения сразу тестируются на полных тестах
Системные тесты запускаются по окончании фазы открытых взломов.
How long does it usually take for rating changes to come, and why is it taking so long for this contest's rating changes ???
Because of the large number of participants in Div. 3/Div. 4 competitions, system testing takes a lot of time. And these types of contests have a 12-hour phase of open hacks.
Please be patient as the user ratings will not be updated until the system testing is complete, which usually takes 1-2 days.
Nowadays, Codeforces is taking quite long time for rating updation!
I had a solution using binary indexed trees for problem F. But for some reason the case with single value is processing weirdly. https://mirror.codeforces.com/contest/1945/submission/252426399 I have added comments to debug, for the case 1 , 1 ,1 output is coming as 2. can someone help on this ?
Igonre, I found the issue
Can somebody tell me the approx rating of all problems???
https://clist.by/problems/