Good... yes, good afternoon, Codeforces!
We are glad to invite you to take part in Good Bye 2024: 2025 is NEAR, which will start on 28.12.2024 17:35 (Московское время). You will be given 9 problems and 3 hours to solve them. One of the problems will be divided into two subtasks.
All the problems are authored by _istil and me.
In this round, we would like to say goodbye to the past bad memories. However, the point is we won't say goodbye to:
- TheScrasse for his cherrish coordination as always.
- Alexdat2000 for Russian Translation.
- crsfafa for providing a problem proposal that was not used.
- LMydd0225, Error_Yuan, and N_z__ for helping with preparation on Polygon (including testing).
- Tony2_CF for improving a task, and KAN for improving the statement of many tasks.
- StarSilk, and EvenImage for LGM testing.
- nullptr_qwq, cat_of_Nesraychan, and Gabp for red testing.
- Caylex, tzl_Dedicatus545, juan_123, destructive_criticism, jer033, Imdie, fossil823656, SF1yer, anango, and min_inf for orange testing.
- IwannaEATaCUTEcaca-qwq, _TernaryTree_, doujinshi_master, PaciukZvichainyi, Dulustan, Eclipsar, and FFTotoro for purple testing.
- Chancylaser, jonatas57, SopaconK, jager59, and Fesdrer for blue testing.
- SkyWave2022, and mikcf for cyan testing.
- ishaandas1 for green testing.
- (_nikd_, Damdam307, OgradL), and (acoatoitgs, LaMatematica14, Alenygam) for team testing.
- sszcdjr for being invited to test but refuse to check a single problem at an excuse of Chemistry papers; and 251Sec for being invited to test but have no time to do virtual.
- MikeMirzayanov for the great Codeforces and Polygon platform.
UPD: The score distribution is $$$500 - 1000 - 1250 - 1750 - 2000 - 2500 - 4250 - 4500 - (3000 + 2000)$$$.
UPD: as pointed out here, the official solution of 2053I2 - Ласковые массивы (сложная версия) is wrong. We are not sure that the problem is solvable with the current constraints. We will decide how to deal with this issue within tomorrow.
UPD: the problem I2 was removed from the official contest. Its statement has been corrected for future use. The affected participants have been unrated from the contest.
UPD: Congratulations to the winners!
Мы рады сообщить, что компания NEAR поддержала проведение раунда!
NEAR была основана в 2017 году Ильёй Полосухиным, одним из создателей технологии трансформеров, и Александром Скидановым как попытка создать систему, которая бы решала задачи по спортивному программированию. О том, что получилось тогда, можно почитать здесь.
В итоге NEAR сделала большой поворот на 180° и начала работу над протоколом блокчейна, который запустила в 2020 году.
В этом году NEAR сформировала новую лабораторию, NEAR.AI, задача которой — создание будущего, в котором технологии искусственного интеллекта открыты и доступны всем, а не контролируются небольшим количеством мега-корпораций.
Одним из направлений работы является обучение моделей мыслить рационально, и задачи по спортивному программированию — это отличное окружение для этой задачи. В этом контексте NEAR приглашает всех русскоязычных участников Codeforces с рейтингом 1600 и выше помочь нам описать решения задач по спортивному программированию. Мы хотим описать решения большого количества задач разной сложности и платим за это сравнительно большое количество NEAR.
Присоединиться к системе можно по этой ссылке.
Помимо этого, в раунде предусмотрены призы, не связанные с этим приглашением:
- Ⓝ 512 за первое место,
- Ⓝ 256 за каждое из мест 2 и 3,
- Ⓝ 128 за каждое из мест с 4 по 7,
- ...
- Ⓝ 1 за каждое из мест 512-1023.
good luck children
you too
Lots of Testing
Will there be any Hello 2025?
Yes
When you realize majority of the testers are in blue to orange range. Barely any anywhere else. Will that impact anything?
Aren't 2 $$${\color{black}{l}}$$$$$${\color{red}{gm}}$$$, 6 $$${\color{red}{red}}$$$ and 10 $$${\color{orange}{orange}}$$$ good enough, how many do you want.
If you do sliding window on the testers you can get various majority tester ranks.
You can find three more red ones on the line "helping with preparation on Polygon (including testing)" :)
No? If you already have some set of testers and you add like 10 blue testers that would not make round worse.
Quantity of good testers matter, not the percentage.
BROTHER IS THAT YOU?
You're the first one to make me laugh today, seriously!
This is how we show text font in a fontless environment lol
Well, I'm Just a children who has just learnt programming for a year.
Beware: you might end up becoming an actual software engineer in your adulthood.
Upvote me pls i need contribution
Bro ask for upvote but only got downvote :v
Excited to participate!
Can you help me become grandmasteru ?
Actually, you can easily make it with magic
Please don't be like 74TrAkToR
happy new year!
why was good bye 2023 rated?
Oops.My bad.Hope this year will be better.Anyway,happy new year.
where's score distribution?
As a parent, I can confirm that _istil is cute!
and 251Sec for being invited to test but have no time to do virtual. :(
Congratulates!!!!!
No 74TrAkToR 74TrAkToR for Goodbye again!!!!!!!!
As not a tester, I didn't test.
As a tester, Happy New Year, and I hope you can achieve a positive delta in this contest as a New Year gift. :)
wow，you are such a kind nailong！
I like _istil's round.
\bx\bx\bx And wish we all get a positive delta.
As a tester, _istil is cute
As a not-tested tester, I didn't test because of my chemistry homework (actually, my chinese homework helps as well). Anyway, wish you guys positive delta!
As a tester, the problems and the problemsetters are cute and wish you all have fun in this contest!
As a kicked test,I want to cry!
As a tester for the first time, what can I say.
The other testers are very good at expressing, but I can only say that this contest is the best one of the year.
Rated?
As a tester, I went cyan, which is the same color as _istil's, to express my adoration for _istil.
Hope it doesn't end up like good bye 2023
What's wrong with Goodbye 2023?
As the only "LGM" "writer" of this "specialist round" (though I proposed no problems actually), I wish you good luck, positive delta and a happy new year! (I believe an lgm may make the round look better :)
chill guys , This is another masterpiece coordinated round by TheScrasse , (orz).
Happy New Year! and well wishes for the
positive deltafor upcoming year.2024 is meaningful to me.It is a perfect way to end this year to take part in the expecting contest!
As a tester, the problems are worthy of being in Good Bye round. Do not skip this one!
Is this rated?
Yes
is this rated??
Yes
my last chance to get expert this year. I hope I can do it and not bottle it again 😭😭😭
8-12-2024
alzahrawi
Alnafis
alkhwarizmii
-Ananas-
albirunii
Zanaty_8
-Oak-
-DragonFruit-
-Orange-
-Blueberry-
As FruitSalad community, we look forward for participating in this contest ^^
and 251Sec for being invited to test but have no time to do virtual.
As a tester, _istil is cute and problems are more interesting than Goodbye 2023. GL&HF!
Let's Go
As a tester,I've lost a chance to gain rating in the end of 2024.
Bye Bye 2024
will it be rated?
i hope for a very good contest before 2025.
Hope that the round can be much better than Goodbye 2023
So what's wrong with Goodbye 2023?
It was a round which has got nearly 5000 downvotes. It had an OEIS-solvable problem on H.
Is this round rated or unrated? Also, will it be like educational rounds or normal (div1+ div2) rounds?
I hope I no longer need to use magic to change color :)
Happy new year! Hope to gain more rating in the last contest of 2024, good luck and have fun!
is this rated??
hope the contest can be great
Is it rated?If so,the rated range?
I guess it will be rated as Div.1+2, because 3 hours.
Is there not going to be a Hello 2025 this year? So far it isn't in the contest list..
I hope Good bye 2024 will not be the same as Good bye 2023
That ishaandas1 for green testing is more like specialist or expert , visit his profile his ranks are under 3000 and if on this basis if ranks were calculated than our rating can be deducted
what do you mean by featured prizes ?? is this something related to ratings
Who can tell me the score of each question
14，初三
$$$2025=45^2$$$ probably the only perfect square number year throughout my lifetime...
Believe in yourself, you have the probability to live until 2116
Hope Good Bye 2024: 2025 is NEAR != Good Bye 2023
Is it ICPC format (Penalty , etc) or Points format (Points per problem ) :D ??
i can predict that 2024 will be in either question or constraint
I hope to become blue in this round!!
As a tester I can finally write a hint for you guys.
a hint
Time to be a pupil before the end of the year haha
+1
As 2024 is coming to a close, I would like to wish everyone a Happy New Year in advance and good results in the upcoming competitions. I am very passionate about algorithm programming.
I hope this contest is unlike the last two T-T.
I Wish every person in the Competitive Programming Community Belated Merry Christmas & Happy New Year in advance...
What is Ⓝ? I search Bing but not results.
Near
rare round dont have thanks for "MikeMirzayanov for the Codeforces platform" O.O
sorry, I added that (including the score distribution) just now o.O
I don't get why couldn't the author just mention if the round is gonna be rated or not
Are u noob?
score distribution?
Score distribution??
score distribution when ?
What is Ⓝ ? Can someone explain please
It think it's refer to Near Protocol
You can check current price (to usd) here : https://www.binance.com/en/price/near-protocol
Wont participate because i feel like its going to be mathforces cuz of chinese setters.
As some testers' friends, I didn't test.
What is N in this, I mean in the prizes??
(insert Good Bye 2023 trauma joke here)
Just a selfish question.
It is 6 questions to hit Expert.
5 questions to remain cyan and climb a bit
4 questions to de-rank to pupil
3 questions to de-rank to pupil
Am I correct?
No, 6 tasks is usually a GM-level performance, 4 and 5 tasks are somewhere in between CM and M (but a lot depends on the speed), fast 3 tasks is usually expert level and lower results are for specialists, pupils and newbies. Although this may differ -- some rounds are harder, some are easier
This might be true in some div4
Newbie it is.
Hopefully I can gain some of the 100 ELO I lost after getting hacked last round.
2025=45*45 probably the only perfect square number year throughout my lifetime
How can NEAR be received? Can top 1023 participators receive their prizes by.. TON wallet or anything other? I haven't found any wallet about NEAR in
WALLETyet.Is this round rated?
Participating after 7 months,wish me good luck
Time will pass, and we might meet again. Looking back at the past, everybody has lived the life they wanted. From NOI2024Day2T1
Pretests passed, 32 ms under time limit:
And 16 ms under TL for systests.
Never have I been so nervous for a system test. I shall worship the Gods.
Kengan ashura???
And uphacked :) https://codeforces.me/contest/2053/hacks/1106836
I'm sure your solution is $$$\mathcal{O}(n^2)$$$.
Nice. I immediately submitted a better one after the contest, but shitting out a code in 10 min will do that.
That's quite a fail to let an inefficient algorithm with cache-inefficient DFS do anything in systests except fail with a big margin from TL.
Solved D and E in 30 minutes,spent 2 hrs on C and still no idea,i hate my brain.
C killed me.
C was brutal
it is just calculating result of f(mid,n) based on f(1,mid) you have to count how many elements are in them (it is the same for both of them) and for each element x in f(1,mid) element x + mid is in f(mid,n) so if you store the number of the elements you see in first part (lets say c) you can just add c * mid to the answer.
The idea is that the splitting is symmetric about the middle of the array. So, we can just follow one sequence of splitting and multiply the average value (i.e. (n+1)/2) by the number of elements that are "symmetric" to where we are currently (kind of a shit explanation, but try to understand my code).
How to solve C?
Consider the following algorithm:
1) Initialize the subsum as 0.
While observing: 2) Note the length of the array observed. If the length of the array is different from the last array length (this does not trigger on the first observation), output the subsum and reset it to 0. Next, calculate the increase in the lucky value, and add it to the subsum.
What is the value of each outputted subsum?
A naive approach would be to do simple recursion:
This gives the correct result but is very slow. We need to optimise it.
Notice that each time we split the current interval
[l,r]in 2 intervals with equal lengths, the operations done on the 2 intervals will be exactly the same in terms of splitting. The only difference between the 2 intervals we are doing recursion on is the values that we are adding.Let's say we are recursing on two intervals of equal length (after a split). Call them L and R respectively.
First observation: the number of stars that will count to our luck score from L should be exactly the same as that coming from R (why? because both intervals have same lengths).
Second observation: for each star that is counted in from L, there is a star counted from R such that m (or m+1/2) is their midpoint. Call the star that we collect from L m1, and the one collected from R m2, then (m1+m2)/2 = m. To be precise, if the split came from an interval with odd length, the relation would be (m1+m2)/2=m, else it will be (m1+m2+1)/2 = m.
So do we really care what the value of m1 and m2 are? No. Because at the end we collect both, so we should add m1+m2 to our luck score. This is as simple as 2m (or 2m-1).
The solution reduces to only knowing the number of stars that we should consider in only one of the intervals obtained after the split.
The solution will be as follows: If the current interval has odd length, the answer is m + 2mX. If the parent interval has even length, the answer is (2m-1)*X.
Where X is the number of stars that count into our luck in only the left interval obtained after the split.
This gives a complexity of O(logN)
You can check my code for the implementation.
Really great explanation, thanks so much I understand it mainly from you and ChatGPT, it took long time :)
We need to add the yellow numbers here, notice how 6->17 has a distance of 11 (where its subarray split), 3->9 and 14->20 have a distance of 6 (where their subarrays split) and 3->14 and 9->20 have a distance of 11 (where the subarray before them split)
D explanation, please
use greedy answer is always multiply elements of a, b in sorted order.
then answer only change if a[x] == b[x] on the sorted order I mean, so update answer on those incidents
First, the optimal strategy is to always re-arrange b so that the relative sort order is identical to that of a.
In other words, the maximum item of b should be at the same position as the maximum item in a.
This will guarantee the defined product P to be maximised.
Rearranging b initially to fit into this condition can be done using sorting (sort both arrays while keeping track of each item's initial index).
After doing this, calculate the initial value of P.
After that, each time an operation happens, we need to rearrange b to fit the condition. The trick is that we don't need to do sorting again. It will be sufficient to swap at most 2 items to get the new optimal arrangement.
To make things easier, let's first sort both arrays, keep track of the initial index of each item in map (or array), call this index_mapper_a, and index_mapper_b respectively.
In other words
index_mapper_a[i] = the index of the ith item of a in the sorted version of a(same forindex_mapper_b).To give a concrete example: suppose
a = [1,5,3,2], thena_sorted=[1,2,3,5]andindex_mapper_a = [0,3,2,1]index_mapper_a[1] = 3becausea[1]is placed at index 3 in the sorted array.Now if we receive a query to increment the ith item in a. We first need to retrieve the position of this item in the sorted array. We can do this using
index_mapper_a. Let's denotex = index_mapper_a[i]. We need to incrementa_sorted[x]. This might ruin the sort order. We need to fix the position of the incremented item in the sorted array.If
x == len(a)-1ora_sorted[x] <= a_sorted[x+1], thena_sorted[x]is still in the right place (i.e. the sorting is preserved).Else, we need to find the new position for it. We know that
a_sorted[x+1:len(a)]is already sorted. So we can simply do binary search to find the new position of the incremented item. We should binary search for the first item Y ina_sorted[x+1:len(a)]such thatY >= a_sorted[x](after incrementation for sure), we should then placea_sorted[x]just before that item. We can do this simply with a swap.Example, if we had
[1, 2, 2, 3, 3, 3, 5]. Let's say we had to increment the fourth item. We will get[1, 2, 2, 4, 3, 3, 5]. We binary search on[3, 3, 5]for the first Y such thatY>=4. We get 5. So 4 should we swapped with the item just before 5. So we get a sorted array again:[1, 2, 2, 3, 3, 4, 5].When doing these operations, you should pay attention to update the
index_mapper_a.Finally, when we obtain all these information, we can update the value of
Pvery simply:We need to remove some factor from
Pand add some factor to it based on which item we swappeda_sorted[x]with.Some final notes: - The case where no swap is needed should be handled so that we don't remove/add a factor that shouldn't have been added/removed. - Adding a factor is done by multiplying the new factor with P. - Removing a factor is done by dividing P by it. - As we need the answer modulo m, we need to also apply inverse modulo using fermat's theorem and modular exponentation.
Check my implementation for more details.
Hmm interesting problems but understand statements was very challenging for me specially problem E
perform really badly but quality contest imo. probably one of best in 2024
E seems significantly easier than D , especially in a contest ..
how to E? i tried a couple of intuitively decent methods but they were failing that 171 tc.
brute force on every vertex(as q) and count the number of valid combinations . There are 2 cases either it should be leaf or it should be adjacent to a vertex which is parent of a leaf . And you have to ensure that p in first case is not a leaf and in the second case that it is not a leaf or parent of a leaf
Not at all
choked on C for 1hr 20 min and solved D within 25 mins :)
So why can't my code for problem E pass the last test case of the samples? The answer should be 171, but my code output 170.
F killed segment tree successfully!
We intended to let all segment trees pass so we decreased the constraints and increased the TL (std is running for about 0.1s currently)...
My segment tree fell in MLE on test 4... maybe my implementation is really messy lol
omg jiangly accepted G and rose up to the first position in the last minutes
How did problem E get by the readers/testers, being so badly written?
The problem never says that (the definitions of) p and q are updated, which is rather important...
Also, the definition of dominated is really unnecessary; one can just define the caterpillar as the path and then talk about vertices in the path (or not in the path).
I thought my solution to I2 is wrong so I only submitted at the end due to desperation...
In this case
My solution outputs
2because it thinks that the two occurrences of1 1 -2 2 -1 1are different...Is I1 ChatGPT-able?
This contest has made me think my life choices....
A<B<D<E<C
D seemed way more painful than C to me. For C you just need to abuse the fact that each tree of the same size is identical. The only difference is you need to add a constant to the tree if the base is not 0.
For instance if you have (base 0 -> [1, 2, 3]) and (base 3 -> [4, 5, 6]), you don't need to compute the [4, 5, 6] branch of the tree, just take the computation of the base tree and add some constant 'C' * amount of nodes taken from the smaller tree
Man I wasted way too much time on C, couldn't implement D quickly enough afterwards
Finally, I think my performance on this contest was actually representative of my skill (maybe enough to finally reach expert).
Congrats on reaching expert! What was the approach for E?
Thanks :))
E solution: precompute for each node toleaf[i], denoting the shortest distance from i to any leaf (using dfs pretty simply). Then, the idea is that, if toleaf[p] < 2, A wins always. So, we just consider toleaf[p] >= 2. We can consider the cases where q is a leaf and when it is not. When q is a leaf, we have n-leaves other nodes to be p, so the answer is already set initially to (n-leaves)*leaves. Then, we consider the second case, where q is non-leaf and toleaf[p] >= 2. In this case, we iterate over each node in the tree, consider it as being q, then for each adjacent node v, consider cnt[v] (which we also will have computed before) to be the number of nodes in v's subtree that are "good" (i.e. toleaf value >= 2). "good" vertices are ones that p can be assigned to. Using this info, we can compute the number of corresponding p values for the given current q.
UPD: I should have added the key fact: if toleaf[v] >= 2, then q being "dragged" in that direction by p will result in a tie, with A and B just reversing each other's moves.
quite bit surprised on the fact that A, C was not GPT solvable, which is very uncommon in recent contests. problemsetters must put a lot of effort into this.
aaaaaaaaaaa I misread problem D thinking it was
increase ai/bi by xand thus harder than it really was. I didn't realise it was only increase by one until too lateeeABC felt a bit too difficult, even though I enjoyed them. E is alright — maybe a bit more enjoyable if we solve for first player, but then it'd be too easy. Gap E-F is hard, but maybe it's my skill issue :). Overall felt kind of balanced.
What I can't understand is the intended solution for D: whatever you do, you need to keep track of the two sorted sets, and be able to recover an element by index and vice versa. This is either a lot of pain to implement, or a no-brainer pbds. For div1 that's alright either way (I did a pbds), but I feel sorry for less experienced participants: if you don't know pbds, you'll likely have a really hard time debugging the implementation yourself, even though the greedy idea is a good one for this position.
No, because the operations are only $$$+1$$$, you can just add to the last occurrence of $$$A_x$$$ instead of whatever random occurrence you got. This solves the problem in a much cleaner way, and without any heavy structures. You can take a look at mine/jiangly's implementations
Oh, that's smart, we basically never swap elements. Then there exists a clean solution, you are right! Still not sure if it is easily identifiable on the spot — i havent thought enough during the contest because pbds was not that difficult to include.
I feel like your solution doesn't work with arbitrary changes of elements. Let's say, you have
a = [1, 2, 3]andb = [1, 2, 3], and then you changea[0]from1to4. Then the answer changes significantly, because2and3fromashift to lower positions. Therefore, your solution also implicitly uses the fact that the operations are just +1, and the array doesn't change a lot.It probably doesn't, I indeed do use the fact we have the groups of same values. It is just the next (not obvious for me) step — that the array transforms without swapping elements.
My code for D isnt that hard
How to do B? Thought of an algo but it became too complicated to implement
If l==r this means you do not have any choice but to fill that index with L
If l!=r you have r-l+1 choices It is mentioned in the problem that the max value of ai can be upto 2*n
So maintain an array (arr) of size 2*n
if l==r set arr[l]=1
and maintain an frequency array which stores frequency of all l's such that l==r
Now create a prefix sum array which stores the prefix sum of the arr.
Prefix sum array is used here to find how many indices l are present which have l==r
now coming to algo if l==r and frequency of l>1 print 0 if l==1 print 1
if l!=r count prefix[r]-prefix[l-1]. If that value is less than r-l+1 print 1 else print 0
that's it!
Did C in log^3(N) by drawing trees and observing a pattern. Ended up being more difficult than intended.
I feel dumb, but these are great questions. Much to learn.
Yeah
Why is the second player in E named Aron?) Kind of confusing (at least for me)
Bcz @El_ta5_3endi_3adi
I failed to pass G because the stack limit of the problem is too small, like much smaller than the memory limit. Shouldn't the stack size be the same as the memory limit?
link. After comparing my solution with some other accepted ones I'm really sure that it should have been right.
As far as I remember, it should be the same as memory limit — but maybe it was just increased to 256 MB or so.
You have a lot of memory in the global arrays, but those should be statically allocated on data segment and not on stack, though maybe Windows calculates stack overflow differently because it's a stupid OS.
Have you checked how much call stack can grow? Make a test with maximum DFS depth, perhaps check assembly to see how much gets pushed at every call, or measure how much you need to set stack limit so it'd narrowly pass.
Stack size in codeforces is 256 MB (and in problems with lower memory limit, you will sooner get MLE than runtime error from stack overflow). So that answers why you got Runtime Error.
As to why Codeforces does this, no idea, but it has been like this for a long time.
MLE is most likely an OS check. Dynamic (heap) allocation strategies are weird and OS-dependent (like memory overcommit on Linux) and can be configured; automatic (stack) allocation not so much, but I suppose it can involve an OS check too.
Am I the only one who struggled with B for an hour? Is there a way to solve it without Fenwick/segment tree?
use prefix sum
could you elaborate the need of prefix sums, i still dont get it
For a segment [l, r], you need to know whether there are (r — l + 1) distinct segments whose length is 1, and they all fall within [l, r]. While taking the input, whenever l = r, update prefix[l] = 1. After taking input, iterate over the whole prefix array from left to right in order obtain the cumulative sum. Then, if prefix[r] — prefix[l — 1] == r — l + 1 for l not equal to r, then answer for that segment is 0. Otherwise, 1.
Ooh, right, that would've been a lot easier, thanks! I'm not very sharp today, haha
i used prefix sum to solve it (with a typo in my locked submission.. but the logic should still be sound)
There's actually no need of a Fenwick/segment tree. I used prefix sums since l and r can be atmost 2n. You can check my submission.
so ones like 1 1 and 2 2 are "forced". I used a second one called "not forced", where I would put neighbors (that is, +1 and -1) of the forced ones (if they aren't also forced). Then use set operations like lower_bound to see if they exist in not forced (again, sometimes you might still need to check if they exist in forced, because at times entries won't be in not forced because there was no close entry in the forced ones).
Don't think it makes any sense to overcomplicate like this, however.
I used Ordered_set gnu policy data structure .. can look at my submission
Screencast of me writing this round in rust will eventually be available here
After a rather long hiatus, I participated again in a contest. Here is some feedback on the problems:
Overall, the contest felt average—not particularly enjoyable, but not unpleasant either. I enjoyed solving and implementing Problem F, and I think that problem B and C could be nice for contestants less experienced than me. I hated the unnecessarily long statements involving ridiculous stories about pretty weird presents as well as all the headers before the actual statements with links to stuff in Chinese (I would be very supportive of codeforces if it were to decide to ban any kind of stuff in the statements of rated contests that has nothing to do with the problem and is longer than one line).
Thanks to the authors and to all those involved in the organization of the contest.
I also thought problem D was annoying, than I realised that you don't actually need to keep track of the indices.
Simply keep the original array, and process the queries one by one (applying them to the original arrays). When a 3 is updated to a 4 it doesn't matter which 3 was updated in the sorted version, so you just find the last 3 and increment it by one.
Has there been a vote or proposal ever to rid of the fluff before the actual problem statement? I'm curious how many people would support fully abolishing all of it.
Getting rid of the fluff is part of the solution.
Dfails when usingstd::mapandstd::setand cleverly swaping elements with overall time complexity ofO(Q log N), but apparently passes easily when using GNU's Tree structure with very similar constant factors. Come on, test better next time. Absolute bs.Mine passed. But barely, yeah.
Goodbye Master QQ
Implementation of D using only std::vector: 298847993 We only need to update the last element with the value a[x] or b[x], not the exact element at index x
Nice problems!
DE were especially sweet, very neat and not implementation heavy. Sadly, I couldn't finish E in time as I spent too much time on CD.
Any hints for F? Please
I feel I1 is overscored than its difficulty. Normally, the subtask score is given so that it is slightly lower than its difficulty, so I guessed the difficulty of I1 is about 3500pts problem in this contest, but actually F>I1 for me.
Every time I participated goodbye round, my rating is also "goodbyed".
Thanks for the round!
My screencast with mumbling and a 8-minute post-contest recap at the end.
Two points from the video:
And of course I have solved the same wrong version of I2 as the contest authors, where we count not just arrays b, but also the ways to choose a out of b.
I'm curious, is there some way to solve H without stress testing when you get WA? I don't see how anyone could deal with all the $$$a_i=w$$$ cases correctly on the first try.
iirc, StarSilk told me he didn't use any stress test during his vp, and he solved it.
Liked the problems but not the statements. Specially the statements of problem A, B and E were unnecessarily complex.
Problem C.
countOfElementsSelectedFromRightHalf can be calculated using recursion in logN time.
Similar reasoning can be used to find answer if N is even.
https://codeforces.me/blog/entry/137621?#comment-1233118 Is this means that intended solution for I2 is broken? If so, how do we treat about this is it wholey unrated?
Yes, it is broken. It's being discussed here. Personally, I don't think making the contest unrated is a good way to solve this: there are prizes involved, not giving them to anyone would be wrong (especially when the amount of people receiving prizes is much bigger than the amount of people affected by this), so that has to be dealt with, and giving the prizes while also making the contest unrated doesn't really make sense to me.
C was very new to me, E was a very nice problem if I was not stuck on problem C, I could've solved E.
Can someone clarify why my submission to problem B 298887302 was accepted in Java 8 32-bit, but the same solution with submission ID 298901051 is giving a TLE in Java 21 64-bit?
937ms is very close to the time limit. Maybe another submission in Java 8 will give TLE.
The reason is that Scanner is very slow. Look for faster method of input.
nice pic))
Some cf rounds really tell me how mathematically challenged i really am. I was able to solve A,B,D but my mind died solving C. I have respect for everyone who was able to solve C by themselves.
I solved C without any maths. You just need to play with the examples to realize the key observation.
Given a range [l, r] if you know the number and sum of values of the first half of the range (assume it [l, m]) then you can find the sum of values in other half in O(1).
Can you explain in detail pls
Yes I'm that Aquawave in problem F as the leader of RiOI team XD
Can someone explain me problem B? The input and output do not make sense to me. Also the question itself. Thanks
basically you have print 1 if you can give ith query a unique value like between (Li and Ri) while making sure other values in array can be anything but not equal to the value you giving to current i. basically if you are assinging 'X' to current (ith query) , you have to check it will be unique like (other query can be assigned some diffrent value). Only values that can cause concern is when Lj==Rj. I dont know if u understood. you can use line sweep or ordered set to implement it
Thank you. I didn't quite get it through your explanation but understood it from one of the YouTube videos.
Do you think the wording of the question was weird?
wording in question 1 and 2 was weird and tbh it was even tricker to figure out what was required and implement it , for q2 it was hard for sure
Problem B:
Can someone tell me WHY this was TLE'ing, I couldn't figure it out for the life of it and had probably my worst contest ever.
there are t = 10^4 test cases at max, and for each test case you are initializing a vetor of size 400001, which makes overall time complexity to be O(t*400001) which wouldnt run in given time limit of 1 sec
I don't know why I could not realize this and should have just used 2*n. Hopefully next year, I start making actual progress (: . Thanks for your comment
Why did GroupMatrix's rating drop, while the performance is 3114 (way higher than the previous rating)? MikeMirzayanov
My final solution of G passed with a maximum running time of 9874ms(9624ms actually when testing pretests), which has a great risk of getting TLE during system testing. After I found that, I soon told Error_Yuan to rejudge that(yes, FSTs on pretests can be avoided if you told the staff). However, the rating calculation is done before that, and now I'm waiting for the rating rollback.
Update: you can't.
yes, FSTs on pretests can be avoided if you told the staff.
Really? Once I faced that issues and also told the staff, but nothing changed.See my blog...
I guess you need to have some relatioships with the staff...
Haha, sounds reasonable
what's FSTs ?
Anyone who had a bad performance will send that he was affected by I2, and thus, all the people who had negative rating change will be unofficial which will affect the rating of other people, for example, being the 300th on 20000 participants is better than being 300th on only 5000.
Surely this is false; there has to be some level of reasonability to these requests, for example a newbie with no past experience of even solving or attempting to solve D's or E's is highly unlikely to be affected by I2. In fact, it's very likely if you haven't solved everything until F that would would be affected by I2 because why would you be attempting I2 in the first place?
edit: technically it is true, but the extremeity of the jump shouldn't be (it would probably go from 20000->19000 at worst realistically)
Did the Near prizes get sent out?
How will I know when I got it (system notif)?
How much time does it generally take
Also if anyone is in India can they tell the easiest way to cash it
They will be sent once Mike finalizes the results and shares the final table with me.
The delay is usually due to relatively time consuming process of making sure there's no plagiarism and other violations.
Hello. My submission for problem D got skipped for being too similar to another one. I didn't cheat. 1/3 of my code is a template, 1/3 is fast exponentiation (both of those I can find in my past submissions for sure) and the rest is a primitive solution. The other submission's author studied in the same school as I did, but I don't know him personally and never spoke to him ever. TheScrasse
I have no authority on plagiarism check, so let's tag KAN.
KAN MikeMirzayanov