Добрый день!
В воскресенье, 25-го сентября в 14:05 по московскому времени состоится Отборочный Раунд 1 олимпиады для школьников Технокубок 2021. Раунд будет длиться два часа, участникам будут предложены 6 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап в Москву. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация (с 14:15 до 16:05).
Зарегистрироваться на Отборочный Раунд 1 →
Соревнование открыто для всех в виде отдельных раундов для первого и второго дивизионов.
Для всех участников всех трех редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будут проведены открытые рейтинговые раунды для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если Вы школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
Авторы отборочного раунда — AndreySergunin, Endagorion, amethyst0 и я, Golovanov399. Спасибо KAN и 300iq за координацию. Кроме того, хочу выразить благодарность тестерам, без помощи которых этот раунд не состоялся бы: kalki411, 300iq, arjunsanjeev7, brunomont, Chocobar, iankury, low_, psevdoinsaf, JinhaiChen и teapotd!
Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:
| Группа языков | Языки программирования / компиляторы | Примеры |
|---|---|---|
| C | GNU C, GNU C11 | 10903473, 17029870 |
| C++ | GNU C++, GNU C++11, GNU C++14, GNU C++17, MS C++, etc. | 23794425, 5456501 |
| C# | Mono C#, MS C# | 3195513, 3794163 |
| D | D | 5482410, 2060057 |
| Go | Go | 7114082, 21366098 |
| Haskell | Haskell | 455333, 1668418 |
| Java | Java 8 | 25491359, 23678167 |
| JavaScript | V8 | 35963909, 35681818 |
| Kotlin | Kotlin | 25779271, 25204556 |
| OCaml | OCaml | 6157159, 1281252 |
| Pascal | Delphi, FPC, Pascal.NET | 1275798, 1259434 |
| Perl | Perl | 2519448, 1277556 |
| PHP | PHP | 413942, 35875300 |
| Python | Python 2, Python 3, PyPy2, PyPy3 | 35883730 (Py2), 36179112 (Py3) |
| Ruby | Ruby | 1837970, 1289551 |
| Rust | Rust | 25180002, 35652442 |
| Scala | Scala | 35847980, 2456025 |
Удачи!
Обратите внимание, в Отборочном Раунде Технокубка будет 6 задач, предварительные стоимости:
500 — 1000 — 1500 — 2000 — 2250 — 3000.
В div. 1 будет 5 задач, предварительные стоимости: 500 — 1000 — 1250 — 2000 — 2500.
В div. 2 будет 5 задач, предварительные стоимости: 500 — 1000 — 1500 — 2000 — 2250.
Поздравляем победителей!
Технокубок:
Div. 1:
Div. 2:
Также опубликован разбор.
UPD: Участники, кто набрал 1800 и более баллов будут приглашены на финальный этап олимпиады.
As the author of two problems I'd like to ask you guys to read all the problems and not to rage quit if you dislike a problem too much
Don't say that you authored either of problem A, B or C of this contest
As the author of all other problems, I agree with this comment:D
i am getting my version of "peter tingle!" :'(
Dont know why but after seeing all author names I have a feeling round's gonna be hard :/
Is it rated?
No, Its not.
As a tester, Problems are really good and interesting. Good luck!!
I see low_ as a tester. Congrats!!
+1 ^^
As a tester, I approve this contest.
In before
If you don't want failed system testing, submit correct code
Very useful. Thanks!
I'm always glad to be of help!
I am able to register for official contest too is it ok .
Which One should I register for uprating? (rating ability about 1900) Could anyone give me some suggestion
Actually, you don't have much choice
You should be able to register only for one as far as I understand
Take care of the unusual time.
Just noticed that russian comments are visible in russian transcripted mode with english comments .
HALA Madrid!!!
Why did you steal my avatar?
bruh.
Notice the unusual starting time,Golovanov399,I think this should be mentioned
Notice the Unusual time. GOOD LUCK :)
Oh my
Notice that it is based on the olympiad (kind of) for Russian students of 8-11 grades.
For some reason it is not written so explicitly in the English page. But better be prepared
Judging from the announcement, the official round is not rated, and the div1 and div2 versions are rated. Is my understanding correct?
As a tester, I just wanted to say I love this community :D and thank you KAN for reaching out and giving me this opportunity
I'm still seeing a lot of upcoming future contest :3
As a non-tester, I just want to orz low_ and thank you for your contributions to the CP community :D
I hate problems
As a tester, I highly recommend writing this round.
An interesting thing happened. Yesterday，my rating was still 1900 + and I was able to sign up for div1. After the end of yesterday's contest, I dropped to 1800 +, which should not be able to fight div1, but I was still in the div1 queue. So do you think I should quit div1. :) (https://mirror.codeforces.com/contestRegistrants/1434)
Actually this(including the opposite situations) happens quite many times.
And it can lead to this: standings — see the forth place.
As a tester , problems are balanced+Cf-Level and great effort by setters . ATB.
Who can tell me if the problems in the 3 contests with same preliminary costs are a same problem? Thanks a lot! By the way, I tried to register for the Div.2 contest as usual, but I failed and got the information "Rating should be between 0 and 1,899 in order to register for the contest". I remembered that the Div.2 contests were for users whose ratings were between 0 and 1,999 (or 2,100) usually. Was it common for this situation?
For parallel Div.1 and Div.2 contests, purples can only participate in Div.1, while purples can participate officially in Div.2 only contests.
I see. Thank you again!
rated？？？
Today there seems to be a very long queue. I hope it is fixed before the round.
I know this is not the right place to ask but I'm facing problem with codeforces. My codeforces from last night is loading in russian and every time it takes few seconds to translate the page into english but its happening every single time for every page of codeforces.
Also i'm seeing few keywords change in codeforces like "Accepted" to "Complete Solution" and "Submission" to "Attempts". Can anyone help me out? Apologies for posting it in this blog but this blog is active so I asked here.
Are you sure you're not using something like Chrome's built-in Google Translate? (that would explain the delay and the system message changes) You can switch the language by clicking the UK flag in the upper right corner of any page.
It's great to see a lot of upcoming contests in the contests calendar.
Good Luck EveryOne!
am I the only one who reads all the comments and vote them ? codeforces comments section is really fun to me! :v
upvote or downvote xD
both! it depends! :v look at ur comment what u see? :p
Could anybody tell me why the registration for Div. 2 is already closed? Is it because of some participant limit? You can still register for Div. 1...
I didn't expect such problems. Typing it in the middle of contest can show you my frustration level..
Anyone else suspicious of D being "well known" problem in China?
https://mirror.codeforces.com/problemset/problem/1192/B Almost the same problem for example, except that here you just needed to find the maximum diameter with weights on edges. So it was quite standard.
contest has made me wonder if i'm way dumber than I though I was ;-;
After 1396C - Monster Invaders, I decided to not read tasks with monsters/enemies and more than 3 parameters in input. It is not good for my mental health.
1B/2D is easier than 1A/2C.
Imo 2C was easier. I didn't prove that sorting both and then choosing would be optimal, but other than that it was a straightforward DP. I was getting WA on pretest 10 on 2D.
I don't know why, but it seems that the contest is too friendly to Chinese OIers.
Almost half of the first 50s are Chinese OIers...
Well, Div1 D was a standard ugly tree data structure problem, so nothing too unexpected happened.
I solved it without ugly data structures, unless a segment tree with range updates counts, and with quite a lot of ideas going into it.
Well, did you use Centroid or HLD decomposition?
There exists optimal path whose one end is end of (arbitrary) diameter
Well, that was unexpected... ;) Still, I believe that it was possible to squeeze straightforward solutions using HLD or Centroid decompositions. My centroid solution used too much memory, but it's basically the intended solution which solves the problem for all possible roots ;(
Yeah, I can definitely understand somebody didn't notice that, because at first I thought about HLD, after a bit more thought I solved this using centroids and was coding this for a long time and it was unexpected need to take a dump that pulled my hands away from keyboard when I realized this observation and after it I threw almost all of my code to trash and rewritten it from almost a scratch :P
Nope. See below.
Yeah, I can agree now that the idea mentioned by Swistakk is pretty cool, but the overall implementation is still messy IMHO.
Unfortunately, some of them got FST...
Even I got 4851 ms to pass, under the condition of using fast IO (which the previous submission didn't). That was too close, is the time constraint too tight?
How to solve 2C?
You can get the possible ways to play (6 * N). Then you can do a sweep with a sliding window.
https://mirror.codeforces.com/contest/1435/submission/96698717
what's pretest 9 in div2 C?
God knows
try this
1 1 1 1 1 10
3
15 20 27
5?
if answer is 3 then this still works for my code
5 is the answer genius
chill out man everyone makes mistakes
why my solution is getting tle https://mirror.codeforces.com/contest/1435/submission/96683823
What's the hack point of Div.1B?
Div 2C, What was I missing, anyone please help?
If it helps https://mirror.codeforces.com/blog/entry/84026?#comment-714881
What was pretest 9 on D2C? I noticed most solutions that failed 2C got WA on test 9. (so did I T.T)
How to solve Div2C/1A?
I did two pointers .. Concept of minimum sliding window .. dont know if it is the intended solution
I tried to do the same but got WA on 9 testcase
Man atleast I passed .. wish that it passes the systest also sinnce I got fst yesterday on C :(
Div 2 D was pretty easy ! just hope that it has strong pretest.
Bruh you didn't even submit.
this is my alt i use it to shitpost :P
why my sol for div2 D getting tle https://mirror.codeforces.com/contest/1435/submission/96683823
For lower_bound on std::set, use s.lower_bound(x) rather than lower_bound(s.begin(), s.end(), x);
The latter will give TLE since std::set. See this
this is second time i am doing this fu****ng mistake ,so any idea how to avoid same mistake in future.
Holy shit this is the first time I solved all problems in a div2 contest DAYUM.
GOD of codeforces, please make it so I don't fail any system tests, please!!!
update: All tests passed :)
Congrats on mp reaching the purple side bruh :)
how to approach C?
How to approach C?
was ternary search going to help in any way?
Sorry, first I wrote the full idea and you only wanted approach, so it's spoilered now.
Anyway, when I solved it, it kind of reminded me of the standard problem taught in DSA "merge k sorted lists".
There are only 6 possible strings so the first thing I thought was — from each note generate all 6 options for the fret, which are the differences from each string.
Then I said, for the hell of it, let's sort each of them (because of the median-of-medians selection algorithm).
Now try to continue from here by yourself, you have n sorted arrays of size 6. If you want the rest, look below.
Sort the lists from max to min.
Now what you want to do, is to start by looking only at the n values which represent the maximum difference in each array (that's why we sorted). The current option for answer is max(maximums) — min(maximums). How can we improve this solution by lower one of the values? We have to lower max(maximums). i.e., max(maximums) corresponds to some a[i][0]. We need to go to a[i][1] (the next element in his array, which is sorted from big to small).
If we lower any other value other than max(maximums).
So we keep looking at the maximum of all current options, suppose it corresponds to a[j][2], we should change it to a[j][3].
We stop iterating when the last maximum was at index 5 of his array (there's no index 6, so we can't lower the maximum, so we are done).
oh great implementation thankyou.
my dumb ass was thinking that the answer's graph would be something like \/ in shape and i could apply ternary search on it. i later found out that it was stricly decreasing and then strictly increasing but it also had some portion parallel to x-axis. that where it fucked up... i was clue less after that. :(
I have doubt you didn't changed minimum at all ?
why did you worked on maximum only?
If the best solution has a smaller minimum, then eventually by lowering the maximum the minimum will be smaller.
For example, if you have [8,4], [6,3] you start with the option 8,6 which gives difference of 2. Then you change 8 to 4 (minimum is now changed from 6 to 4). Now you are at option 4,6, which again is diff of 2, so you change 6 to 3 (again minimum changed from 4 to 3), and you get the best option with diff 1: 3,4.
i am having a implementation problem what if there are more than one maximum equal to maximum(maximums)?
i think this is why my new code according to you failed on test 9
You are erasing the minimum element from val. You should be erasing the maximum element from val.
vals is sorted in descending order.
the the set with the bigger (maximum value) comes first in set. so i am erasing the begin because begin has the current maximum. :(
Finally did it, i am sorry i didn't understand your logic at first go. now when i anaylyzed properly i found out it how it is working it a great implementation. and i surely learned something out of it.
thankyou for being so helpful. keep up the spirit.
submission.
I was just going to say that you don't update the minimum answer — good job!
Thank you guys for the Div2 C really enjoyed doing it :)
C is damn shit. NlogN gets TL
I passed though .. had around 200 ms
link I dont know whats problem with my code. I could have got a big delta.
passed for me
https://mirror.codeforces.com/blog/entry/84026?#comment-714881
[EDIT] Hope don't FST
How to solve div2 B?
All elements were unique you just have to find a row and column with same first element and now you know that is the first row and column...
elements for first row are going to be first element of columns and same for the elements of columns.
Note that all the elements are different, so take first element of all the rows. All these elements must make up the first column. Search for this column in the given columns, once you find it, you know the order rows need to be placed in. Then just print the rows in the required order.
Can you please help me what I did wrong? (WA on test 2)
Your answer is sometimes repeating rows.
Can you give me an example please?
Oh! I got it. I missed some part of the problem. Sorry for disturbing you.
Why TL in C is too strict. My O(NlogN) gives TL on test 9. Why? Why?
link
Seemes to me that
is O(logn) search at each iteration.
I'd say that you there have O(nlogn) with huuuuge constant.
Yeah, that's it but I don't have any better way to go. It's bad to see an intended solution gets rejected due to strict TL
It's you who's doing too much extra job.
For example you can do smth like
I pretty sure, that intended solution is a way less and O(nlogn).
Most likely it is not $$$O(NlogN)$$$
I am not sure but I think you do on each '+' linear search for next element...which makes it basically $$$(N^2logN)$$$
Assume input like n times '+', then 1,2,3,4...
In the vector $$$val$$$ I am taking each reachable elements once and in the map $$$mp$$$ I am taking from where a certain value is reachable. Which gives us total of $$$6n$$$ and map gives us $$$logn$$$. Isn't it?
You iterate the lists in mp[], these lists can be huge.
But, in the whole iteration, isn't it that I am counting $$$6n$$$ things? I might be wrong, I am not really good in time analysis. But, I am not getting your point
Today's div2 C was very similar to this: https://www.geeksforgeeks.org/find-smallest-range-containing-elements-from-k-lists/
Can someone give some hints for Div1 D?
1149C - Tree Generator™
The editorial for that problem has basically everything you need to know to solve this D.
Thank you very much .
Man I thank authors for problem D2C .. really felt a super satisfied after solving that problem
Div1 ABC were selected while high on something, huh? A is a good problem but seems way harder than a typical A, B is just a basic idea and implementation (I'd swap them) and C is just some weird ugly adhoc. Call it personal preference, but that is a ragequit problemset.
At least D is very interesting. My solution is based on proving that we don't miss the best path if we pick a diameter and use one of its vertices as one end of our path. Next, we can assign a state $$$X_v$$$ to each vertex $$$v$$$ where for a stone edge $$$(u, v)$$$, $$$X_u \oplus X_v = 1$$$. That means we're dealing with 2 fixed rooted trees and queries "invert all $$$X$$$ in a subtree" and "find the deepest vertex with $$$X=0$$$", which can be done with a segment tree in $$$O(N+Q\log{N})$$$.
How to prove "we don't miss the best path if we pick a diameter and use one of its vertices as one end of our path"?
Prove that when the diameter has an odd number of stone paths and our best path doesn't visit this diameter, we can extend our path to the appropriate endpoint of the diameter. Then prove that when it visits the diameter, we can also improve it.
Nice observation. I thought you have to use centroids and solve in O(Qlog^2N).
What was pretest 11 on div2 D?
It was a good test case!
Was C precomputation with a small dp of prefix and suffix?
.Can anyone tell that my solution will pass or not . Solution link. Code Link
Pre-thanks to the reader of the comment!
Why is Div1C a routine maxima finding problem?
Can someone please help me in 2C/1A? I formed an array of all possible ferrets I can chose by also storing the index for which I get that ferret. After that I just iterate over all possible values of ferret using two pointer. Whenever I get a condition that the current indices have all notes atleast one, I consider it and increase the lower indice by one. ANd whenever I dont comeup with such a situation, I increase the upper indice by one. Can someone please tell where did I go wrong?
You can copy-paste problem Div.1D from either here or here, and then add 5 new lines to adjust it to this problem. Too sad I read Div.1E first. =/
Seems that m2.codeforces.com had periodically been unstable during contest. Why is that?
(Had it been accessible, I would perhaps have one more problem Pretest Passed... sad story)
In div.2,why C C and why E E?:/
Problem D was way easier than C, I wasted 60-75 min on C and then started D and it took only 10 min. Even no of ac submissions say it. If D and C were interchanged D would have had 1000+ and C would have 400 and would have been reasonable.
I feel it is psychologically difficult to move to the next problem skipping the current one, especially if it is WA as it may just be a corner case.
How to solve A?
First solve for these two cases:
1. When $$$n == 2$$$.
2. When $$$n == 3$$$.
Then extrapolate your solution for any $$$n$$$.
Learnt 2 lessons
1)If you see a problem which even IM's are struggling to get AC, skip that and move to the next problem (Iam looking at you 2C/1A)
2)If you keep on getting WA on a particular test case, instead of debugging do
ctrl + A + delstart from scratchKeep your lessons to yourself, you aren't helping anyone by sharing them here.
Bad ordering of questions. Why is D 500 points more than C?
Is there a DP solution for 2C, two pointer approach worked for me but I wasted too much time thinking about a dp solution.
I have shared my DP + Greedy solution here.
Golovanov399 reporting cheating cases this and this
Even their handles are similar lol.
MikeMirzayanov please take care of this, he is ranked 4 in div2.
wow nice catch. I hope it will be taken care of.
Waiting eagerly to see ecnerwala solving 2C/1A in his stream .
Sort the 6 strings by value. Put all nodes on lowest string. Then, while possible, take the note from the biggest fret and move it one string up (which moves it some frets down). Check diff biggest fret — smallest fret for ans. Repeat.
Is this exponential in the worst case?
No, it is n*6, in worst case, since every note can be moved only 5 times (+1 initial run thhroug the array. So $$$O(n)$$$
But you're moving one note at a time, right?
EDIT: Got it. Thanks
Yes, using a priority_queue to find the biggest fret. 96675514
There seems to be some issue with java platform. Problem B is giving TLE for a simple O(n*m) solution.
why my sol for div2 D getting tle https://mirror.codeforces.com/contest/1435/submission/96683823 please help..
haha )) :
Is this D? Me too (on test 56), time to go to cyanide.
Yes :<
Tired of weak pretests now. 4 FST in last 3 contests. -_-
If you struggle with C for 1.5 hour, maybe you should read D... The more you know
From now on I won't ever trust any tester saying than he approves the contest/loves the problems/finds them interesting. The same goes for "don't rage quit the contest" — today it was the best possible tactical move.
I wonder why tourist's submissions got
skippedexcept the first one(which took part in the systest).... __ Just be curious, shouldn't the last submission count into the systest(instead of the first one)? Or I missed something?→https://mirror.codeforces.com/blog/entry/84056?#comment-714979
first submission count other skipped :if you are tourist else : last submission count all other skipped
https://codeforces.ml/blog/entry/84056?#comment-714979
Get it, thanks
emmm, all except the last can't pass pretests at that time.
And I don't know the reason.
I guess the data is wrong?
I have solved only two problems in today's contest. One of them got tle in main tests. Please god let me know is it a dream?:()
no it is codeforces..
submissions 96704396 and 96676432 are exactly the same code, but one of them passed while the other got TLE on test 17.
May you rejudge submissions of D? Many of them are very close to the time limit(but we don't know that during the contest since their performance are good on pretest), and those submissions're hopefully to pass with fread or rejudging. I think it's not the intention of problem to distinguish the codes with fread and the codes without.
I: Nice! I finally passed Div1.D!
System Test: No, you didn't.
please anyone check to it
my solution is O(n) for div2B and it still shows TLE what i am doing wrong how can i further decrease time complexity people have submitted in O(n) and they are accepted ?? Help
https://mirror.codeforces.com/contest/1435/submission/96705858
You are creating array of size 100001 for every tc i.e: 100001*100000 operations. The statements said that "Sum of nm over all test cases does not exceed 250000" reduce the unnecessary space to avoid TLE.
How to create a large number of [TLE failed system test] :
Set a tough time limit.
Don't put into pretests the test on which most solutions run slowest.
Enjoy FSTs.
:)
what are you saying this is very bad even solving in O(N) in pypy and python it is impossible to solve B div2 in O(logN) when submitting in c++ it is getting accepted this is unfaire for python coders !!
Nah Jiangly and you are discussing totally different things. Python is already a very slow language and there is no reason to set additional time constraints for python users.
They shouldn't have given the option to submit in python then. Just like Kotlin heroes.
The author solution works 1.4s, and we added tests with highest time for our solution into pretests. Time limit is 5s, because we wanted to prevent $$$O(nlog^2(n))$$$ solutions.
Well, most of the time this is OK, but here's the reminder that you'd better check if other solutions have the same complexity but larger constants. (As well for me to come up with a solution with smaller constant)
What the hell is this!! why so strong time constraints, is it even possible to pass Div2B in python? My Code
I think it's just up to Python knowledge for buffered IO operations
https://mirror.codeforces.com/contest/1435/submission/96708855
Like same problems with cin/cout vs scanf/printf in C++
Or Scanner vs BufferedReader in Java
A good round! But,in fact,I don't think the order of problem A and B is correct.The statistical data also showed that problem B is easier than A.And of course,I tried to solve A for 1h,then give up to solve B,and solved it after just 7min.I'm very angry for I solve B so quickly but still got lots of penalties for B.
By the way,I'm talking about the div1 round.
Why cin is THAT slow?
It took cin about 800ms to read just $$$4\times 10^5$$$ integers that $$$\leq 10^6$$$?
https://mirror.codeforces.com/contest/1434/submission/96673580
https://mirror.codeforces.com/contest/1434/submission/96703647
Have you tried
ios_base::sync_with_stdio(false); cin.tie(nullptr);?its funny, you are a red coder. and you are asking us about cin and scanf?
Maybe because cin is very fast in some other online judge like zhengruioi .
It can even read $$$10^6$$$ integers in less than 200ms.
cin is tied to cout by default, meaning that it'll flush the output stream everytime it's called, unless you turn that off by adding
ios::sync_with_stdio(0); cin.tie(0);. It may be the case that the judge you've mentioned uses some kind of modified compiler.I see, thank you.
what is wrong with this approach for problem D we will fill the value in increasing order for example if we have queries like + + 2 + 1 + 3 + 4 bla bla bla so for (first 2 pluses ) we will assign 2 and 4 next we will assign 1 and so on but this gives wrong answer can anyone explain.
When will rating be updated?
Ratings changed!
Any issue with this contest ? Can't find the problems in problemset
They are on the second page
Подозреваю, что у меня задача е была протестирована неправильно. Претесты прошло. Выдало idleness limit на системном тестировании, на тесте 6 (и это странно). При повторной посылке того же кода (в дорешку) выдаёт "полное решение".
Разберемся и все исправим!
Can someone tell me why I am getting TLE in problem D2B? If I am not wrong, I think it is O(nm.log(nm)) solution.
https://mirror.codeforces.com/contest/1435/submission/96684311
I don't know the exact reason but your code is working fine after adding "return 0" at the end of your code. You can see it from my submissions.
When will ratings update ?
Edit : Updated
Codeforces got TLE on problem F. Rating changes.
More like the FSTed on it ..
You can see his submissions not hacked they just skipped. Probably he cheated in contest and submit close codes with someone so he got dedected and all of his submissions skipped because of this.
For div2 c, I thought about an algorithm to check whether all values of 1-n appear in the interval. I thought of a hash algorithm, specifically like this, for each i of 1-n, generate a 40-bit random number x, and then use an array of 128-bit numbers to store the hash value. For 6*n numbers, if each number is generated by the i-th number, the upper 40 bits will XOR a random number x no matter what, if i is the odd number of times (you can use map to count), the middle 40 bits The upper 20 bits of the XOR of the upper 20 bits of x, if i is the even number of occurrences. The lower 20 bits of the middle 40 bits are exclusive OR of the lower 20 bits of x. Divide x into four segments, each 10 digits, marked as 0-3, set y as the number of occurrences of i%4, if y=0, XOR the lowest 10 bits of the lower 40 bits to the segment 0 of x, and so on . Then the XOR sum of the interval (l,r) can be calculated like this: XOR hash[r] into hash[l-1]. For each i, if it appears an odd number of times, there must be x in the upper 40 bits, if it appears 2, 6 times, there must be x in the middle 40 bits, and if it appears 4 times, there must be x in the lower 40 bits x, then just take out the high 40 bits, the middle 40 bits, and the low 40 bits and then XOR, the value obtained is XOR with the random number x of 1-n, and check whether it is the same.upd: I found that I was wrong, sorry.
Sad, why is the first digit of my ID not a number
I think that reason is time of last submit. Not handle)
Will we get editorials for this round? coz I am waiting for it.
https://mirror.codeforces.com/blog/entry/84056