Всем привет!
В это воскресенье, 20-го марта 2022 года в 11:00 по московскому времени начнется Финал Технокубка 2022!
Итоговые результаты финального раунда Технокубка >>>
Для тех, кто хочет посоревноваться на тех же задачах, будет проведен обычный раунд Codeforces, совмещенный для всех дивизионов. Раунды начнутся в 20.03.2022 14:35 (Московское время), не пропустите!
Конечно, если вы участвуете в финальном раунде Технокубка, то вы не можете участвовать в раунде 778. Мы просим участников официального финала воздержаться от обсуждения задач в открытых сообществах до конца раунда.
Этот раунд подготовлен при участии следующих людей:
- TheScrasse и я подготавливали задачи.
- dario2994 координировал раунд (Um_nik помогал ему в оценке комплекта задач, а KAN помогал ему с первой координацией).
- cry, US3RN4M3, angeredgecko, franfill, lorenzoferrari, NemanjaSo2005, TeaTime, manish.17, Logic_zys, kpw29, generic_placeholder_name, irkstepanov, KAN and gamegame тестировали раунд.
- MikeMirzayanov создал Codeforces и Polygon.
Разбалловка (для раунда 778): $$$500 - 750 - 1250 - 1750 - 2250 - 2500 - 3500 - 4000$$$.
I hope I can get to blue, although that's impossible for me.
I wish you get green.
Please no boring&standart segment tree problems, dont repeat mistakes of the previous 2 years... Please...
Are interesting and original segment tree problems ok?
2D segment tree beats
For people who don't know the meme: at RMI I thought I had to implement a merge sort tree beats (only chmin), and I didn't realize that merge sort tree already contains all the necessary information to process chmin.
For sure :)
Clashing with ABC 244 :(
Bruh NOOOOOO. This is bad :(
I will lose blue in this round
Why? :(
I will win CM probably :)
gl gaining 208 rating lol
That was really so
Next contest pupil hahaha
as a tester, the problems are pretty neato burrito!!
I didn't know envy was a tester lol
Is this the remorphed version of "Go Study Round 1"?
This is the problem set that was originally intended for Go Study Round 1. It's possible that the Go Study round could still happen in the future with a different problemset, but I don't know anything about it.
Both the UTC and Moscow time are incorrect. Please rectify.
As a tester, I don't remember having so many positive feelings about a problemset. I had a lot of fun testing, and I am sure you'll enjoy the contest, too!
If there is no particular reason for the unusual time then I would like to request to authors and coordinators of this round to please shift it to the usual time so it doesn't clash with AtCoder Beginner Contest 244 and we can have a nice 35 minutes break.
It clashes with ABC 244 not ARC 137
Timings of CF round will most probably not be changed as it is based on Technocup finals.
At 11 o'clock Moscow time, as it was written in the announcement, the Russian Olympiad for schoolchildren Technocup starts. Obviously, the round based on this Olympiad should not start much later, because otherwise the participants will have time to tell all the tasks and their solutions
Expected to get cyan after this round.
Unusual time again :(
Why 8 problems in 2:15 and not in 3 hours?
yes, 8 problems, time should be 3 hours!
Because it's SpeedForces XD
hello sir, may i knwo how to be a tester, for the april fools round 2022 ?
Thnks
I am looking forward to this round, but emorgan, did you write 2022 as 2021 in the first sentence?
upd : I'm glad to see that this problem has been fixed.
I'm glad to see that you're glad to see this problem has been fixed.
I was really looking forward to giving both Atcoder ABC and this round but looks like I am gonna have to choose.
Lemme guess, you're gonna choose this round.
Guess my future plox.
What fuck?! It's time is as same as ABC244!
Orz USA Round!
such orzness
:)
Can someone please explain what does it mean by Div 1 + Div 2 ?? Is it a combination of two rounds?
It means it will be rated for both div1 and div2 and questions could be expected to have difficulty accordingly. Like generally, these 2 are held separately. To get a better idea go through other div1+div2 rounds' questions. All the best btw.. :)
It clashes with AtCoder Beginner Contest 244 :(
I hope I will become CM tonight
firs time on rated. lets go green :'v
plant trees
Good luck to everybody and myself. hoping to get green :)
plant trees
Score(A+B) == Score(C)
Thank you kind sir
Score(B+C) == Score(D)
Round will it not be rated?
rated.
It doesn 't say whether the competition will be rated or not ?
You guys can solve C????
Get the sum of the numbers and try to create the array!
Bye ! expert
How to do C?
Store all the values in the array in a map. Find the sum and use recursion to see if you can construct the number backwards.
How didn't you get tle? The recursion can visit 2*sum nodes no?
But we should stop it as soon as the resulting array's size exceed n , since if you observe the number of nodes we get in resulting array always increases by atleast 1 at every step of recursion.
But if you stop how do you check if the current elements in the resulting array can reach the elements from the original array that you are trying to get?
With the map he mentioned, each time you get to an element of the array it increases total by 1. If total is equal to n at the end, the answer is yes.
As a matter of fact, what you should do is to store the values together. It means that if you have k numbers of i, you can divide them into k numbers of i/2 and (i/2+i&1), which speeds up the whole process.
No, because of short circuiting. You can take a look at my submission here (Ignore the sort beforehand, it doesn't do anything I just forgot to take it out) : https://codeforces.me/contest/1654/submission/150261342
Interesting. I did the exact same thing though and TLEed. Is it something i am missing or is it jus that i am using a multiset? 150259740
You are missing the short circuiting part. The way your code is written now, it will continue to try to look for possibilities even when found that the number cannot be constructed. I made a couple of changes to your code here and got AC
Ok I see. Thank you very much!
Keep dividing the biggest piece of the cake if it exists delete it if not then it should be bigger than the biggest number in array a because if the biggest piece you have right now is smaller than the biggest piece in array a then you can't achieve that number
Can someone explain why does this code gives wrong answer on Problem D 150270389
...
Is F 2^27?
It should be $$$O(n2^n)$$$, but I'm still debugging my code due to some annoying border cases.
It can be solved with classic suffix array construction. If you sort prefixes of length $$$2^k$$$ for every $$$j$$$, then
Thus, you can compare prefixes of length $$$2^{k+1}$$$ by comparing pairs of prefixes of length $$$2^k$$$.
How to solve E?
I want to know this too
My approach is as follow:
Let $$$b_i=a_{i+1}-a_{i}$$$ for $$$1\le i<n$$$
If final $$$|b_i|> \sqrt n$$$,there will be less than $$$\sqrt n$$$ elements not being operated. Calculate for every $$$i$$$ with brute force is okay.
Otherwise we have $$$|b_i|\le \sqrt n$$$ we can calculate the most remaining element for every $$$b\in[-\sqrt n,\sqrt n]$$$. We can classify every $$$a_i$$$ with $$$a_i-(i-1)b$$$.
Either $$$|\text{difference of AP}| \lt \sqrt{a_{max}}$$$ or $$$len(AP) \lt \sqrt{a_{max}}$$$.
We can check for all possible differences in the first case in $$$O(n \sqrt {n})$$$
In the second case realize that for a difference $$$d$$$, the difference between two terms at positions $$$i \lt j$$$ must be $$$(j - i) \cdot d$$$. Since $$$|d| \gt \sqrt{a_{max}}$$$, this will exceed $$$a_max$$$ in at most $$$\sqrt{a_{max}}$$$ steps.
Unfortunately I didn't realize that the initial statement directly gives you the way to solve the second part during contest T_T.
You need to find maximum sub-sequence $$$i_1, \dots, i_m$$$ such that for each $$$k$$$ in the sub-sequence
where $$$b$$$ and $$$c$$$ are some constants. If $$$i$$$ and $$$j$$$ both belong to the sub-sequence, then
But $$$|a_i - a_j| \leq 10^5$$$, so either $$$|b|$$$ or $$$|i-j|$$$ is less than $$$\sqrt{10^5}$$$.
So, you check all $$$b$$$ that are smaller than $$$\sqrt{10^5}$$$ and also all sub-sequences that their width is at most $$$\sqrt{10^5}$$$.
why the memory limit of D is 256MB. My program can't pass only because of this limit. I think this problem would be better if it's memory limit is 1GB
I think we both tried prime factorisation. Apparently it isn't the intended solution
i didn't do prime factorisation. and i think my program's memory is not so big.code[submission:150269946]
Nevermind. The editorial's solution is doing exactly what i did in my solution (using maps to maintain prime factorisation). Now I am curious to know how the people who got AC implemented the same.
Great problemset, thanks to authors!
How do you say this is a great problemset when you haven't even participated in it? Do you have an alt account?!
I participated in Technocup, you can see it here
How difficult...TAT
What is the reason for higher time constraints on the problem 1654B - Prefix Removals?
This N^2 150248852 submission passes because of that.
And I also have a failed hacking attempt on it :-/
This is actually $$$O(26 * n)$$$ — it traverses the string only once for each letter of the alphabet
Yes, I understand that but the string is passed by value which is O(N), and also the erase function should give O(N) complexity for every operation.
Also, you can see that the code takes 1000+ ms for execution, which an N*26 solution won't give.
The time constraints should be accordingly so these types of solutions don't pass.
Yeah, I guess the compiler optimizes it and the time limit allows it to pass the pretests Not sure whether it will pass systest though
It will pass. Two seconds of time allocation for this question is really too much.
I don't know about compiler optimization, but strings take lesser memory than integer arrays of the same size, so maybe lesser complexity for operations.
Surprised to see multisets works. I thought we must use maps.
The same complexity finding elements is log(n) erasing element is log(n)
If
s
is a multiset, isif(s.count(x))
$$$O(\log n)$$$ or $$$O(c\log{n})$$$ ($$$c$$$ is count of $$$x$$$ ins
)?I used to think it's $$$O(\log n)$$$ cause the compiler will optimize it. Until today I found this will keep fucking TLE unless I change it to
s.find(x) != s.end()
or add Ofast optimization manually.$$$O(c + log(n))$$$, see complexity section of these docs.
With the grace of cpp20 now we get a new function known as
contains(x)
, which can be used likes.contains(x)
, as the name suggests it checks if the data-structure contains the value x or not. The great fact about this is that its just log(n) and plus is more good suiting nameFor C this was my approach. Can someone explain why this is wrong.
example: 7 1 1 1 3 1 3 3 2 3. Sort the array in descending. 7 3 3 3 3 2 1 1 1 1.
Divide the array in equal sum halves. Meaning this array will be divided into 7 3 3 (sum1 = 13) and 3 3 2 1 1 1 1 (sum2= 12). If abs(sum1 — sum2) <= 1. I will recursively apply this on half1 and half2 until either only one element is left (which return true) or this (abs(sum1 — sum2) <= 1) condition is not met in which case false is returned. if both halves return true then only the answer is yes otherwise no.
My submission: https://codeforces.me/contest/1654/submission/150266681
It's not quite clear what's going on, but I'm going to guess that given a '1 1 2' you do not know if it combines to 2 2 or to 1 3.
it will be combined to 1 1 and 2 because the total sum is 4 and halves will be 2 and 2. My code returns YES in this case btw.
This is how i select the numbers. To be able to select them greedily i sorted the array initially. SUM is the sum of entire array.
What happens if you have 2 2 1 1 ? You can't divide it to 2 equal sums but this can be achieved 6= 3 3 = 2 1 2 1
why tho? My code will separate it into exactly this, 2 1 and 2 1. I ran this test case and my program is return YES.
But you're sorting the array descending right? if you do then what's the point of sorting if you can separate the halfs without being adjacent
https://codeforces.me/contest/1654/submission/150251750
can anyone please tell why this code is getting TLE on test#7, it seems correct to me
Imagine when you have 200000 numbers each 10^9, and you have to break everything into 1 before returning NO
I don't think so because i have written the condition if (*s.begin() > x)return; inside recursive function that way it will break much before.
Have a globally declared flag value, and use it to stop the unnecessary calls if you already got the answer, before solve(a) and solve(b). I also got tle at tc7, but after adding flag got AC.
As mindFlayer said, you will be making some additional calls to
solve
. You will be returning from that function call but all the other calls tosolve
will not end. this worksCan anyone tell me why this code is getting TLE(on pretest 9) for problem 1654C - Alice and the Cake, I think My code complexity is O(logn*log(sum)) My code
Complexity is O(2 * sum * logn)
Solve function goes like that
Sum + Sum / 2 + Sum / 4 + .... + Sum / Sum = Sum * (1 + 1/2 + 1/4 + ...) = 2 * Sum
Why not test problem A first?
The questions are nice, but time limits/constraints are not (For problem E).
My solution for problem E runs in $$$O(n\sqrt n)$$$ and I believe it is already the optimal time complexity (correct me if I'm wrong). However, I still had to do like 40 minutes of constant optimisation and get a few penalties for the TLE verdicts.
I have also seen that many other submissions are only just under the time limit, in fact, 1/3 of solutions that passed pretests used more than 4s. There are also around 2.3 times more TLE submissions than AC submissions to add to the fact.
This also caused bottlenecks for other languages, with only 4 languages (C++, D, Java, Rust) having AC solutions on this task.
I believe these kinds of constant optimisation are absolutely unnecessary to competitive programming and does not bring anything extra except benefitting those with templates optimised for constant optimisation, which is irrelevant to one's actual algorithmic skills which competitive programming is supposed to test.
For me, $$$O(n \sqrt n)$$$ with
unordered_map
got TL, but just sorting and solving in $$$O(n \sqrt n \log n)$$$ somehow passes...arrays is also doable :p
well.. I just failed system tests.. I should have done more constant optimization xD
upd: my solution got rejudged and got accepted. Is that a new feature?
I think they always rejudge TLE submissions a few times during system tests to avoid subtle differences in runtimes between different executions bringing in a "luck" factor
Dear contestant,
Please don't worry if you had to make some formulas shorter in order to pass a time limit that was set as a triple of our solution's running time. In a programming competition, the way you express your ideas in code actually matters. Apologies if this does not fit your view.
Thanks for the feedback,
A mere alt account.
I agree with your perspective that requiring constant factor optimization does not make the contest any more interesting. We did not want any solution with correct complexity to get TLE (at least I didn't, I cannot speak for the other preparers). In this case, we made the constraints of E more lenient several times during testing, until the official solution (which uses hashmaps) ran in 1700ms -- at that point we thought the time constraints were reasonable.
In the majority of cases where contestants complain about problems requiring constant factor optimization, it's not because the authors intentionally wanted to require it, but rather because there was a known brute force solution that could easily pass if the constraints were more lenient, or because changing the constraints would give away the intended complexity, or because increasing the TL would lead to queuing during the round.
In this case, in hindsight, I would say we perhaps should have lowered the constraint on $$$n$$$, but I'm not 100% sure about it. Such a change would have likely allowed a few highly optimized $$$O(n^2)$$$ solutions to pass, and it's not clear whether that's a "lesser evil" than causing some solutions with poor constant factor to get TLE.
This is a good thing for people to learn that sort + two pointers is often faster than map/unordered_map.
My approach for C:
-> The sum of array is the starting weight.
-> We can store the count of array elements in a map.
-> We start the simulation using a priority queue, with starting weight inserted in PQ:
->We take the top most element from PQ and check if it exist in the map:(2 possibilities)
If it does not exist, it means probably it was divided into 2 pieces later, so we will divide this piece into 2 parts and push them into PQ, to get divided later.
If it exists, it means this will be part of the final array, so we will consider that this particular element has been obtained correctly and thus won't be divided further, and we will update the count of this element in map by decreasing by 1;
-> We do this simulation n-1 times.
-> Now, in the ideal case, all the keys in map should have a value 0 as its count.
-> if above statement is true -> return YES; else return NO;
P.S.: Queue would also work fine in this case, as processing the elements in any order will give the same end result. 150248249
Instead of Priority Queue I was wondering why not normal queue would work. I took some test cases and dry run it, luckily I found that normal queue would work. Anyways thanks for your intuition, it helped me a lot.
How to solve problem D? I have a basic idea but couldn't figure out how to deal with node with n-1 degrees. It would easily overflow.
What is your original idea?
I fell shocked when refreshing the status page and found lots of my friends fst on problem E
panic
Me after submitting D in the last 5 seconds with a correct solution but then realized I'm printing the value at the root and not the sum.
It's a pity that I've only got 15 minutes to participate in the contest :( Luckily, I solved 2 problems within 12 minutes, so this contest is almost unrated for me XD
Due to AtCoder ABC today?
Exactly :)
I registered Rated for ABC but chose CF. I forgot to cancel the registration and got -100 delta in Atcoder...
problems A and B were actually pretty easy but then C was very hard compared to A and B
I got TLE on problem E in the system test. https://codeforces.me/contest/1654/submission/150264452 After the system test, I resubmit the same code. Then, I can get AC! https://codeforces.me/contest/1654/submission/150275130
This happens to someone every contest. The CF grading servers have some variance in time measurements, and there is nothing we can do about it.
Thanks. I had a rare experience. I feel the ordinary judge is a little bit faster than in the system test (though I have no evidence).
[Deleted] I put the discussion under the editorial blog.
Why was my first AC submission for C was canceled ?
If you submit a new solution after passing all the pretests, the earlier ones will be skipped.
Can anyone help me explain why this code get tle on test 3 :(( https://codeforces.me/contest/1654/submission/150283548
you can limit the times of split operation, the times can't be greater than N.
Orz orzdevinwang
In problem E, why use 50 as constant can solve the problem but bigger number cannot.
The right constant should be $$$\sqrt n$$$ ,isn't it?
I don't understand why?
My code https://codeforces.me/contest/1654/submission/150288568
The pieces in your piecewise algorithm have different constant factors.
I use 100 to pass it...
I tried explaining my solutions for problem A,B and C . Link to the video
Hope this can be of any help.
The editorial is amazing! I hope all the editorial have "Hints".
nice problems.
Wait!Could you get into the editorial?
I can't, it says "you are not allowed to view the req page"
Nope, I think they are editing it. It worked yesterday.
Can anyone tell me why my code got TLE please :/ It's only O(nlogn)
In case answer is "NO" loop can run long before it breaks. If origi.begin() is 1 and x is 1e9 it can create near 2^30 elements for split multiset when the x is invalid.
Split size cant be bigger than origi size. If you change while (!origi.empty()) to while (!origi.empty() && split.size() <= origi.size()) it will not tle.
oh, I see, thank u
Does it seem strange to anyone else that F from this contest is rated 2800 while G is rated 2900? F was solved by 107 competitors in-contest, while G was solved by 10, which intuitively suggests that G is vastly harder than F; Carrot tells me the performance corresponding to 107th place is 2670, while 10th place corresponds to a performance of 3296. It seems to me that F is perhaps slightly overrated, but G is definitely highly underrated. (Admittedly, part of the reason G had so few solves is probably that it appeared late in the problem set, but even so, it's hard for me to imagine that the problem deserves a rating lower than 3100 or 3200.)