Добрый день!
В 14.11.2021 09:05 (Московское время) состоится Технокубок 2022 - Отборочный Раунд 2 олимпиады для школьников Технокубок 2022. Раунд будет длиться два часа 15 минут, участникам будут предложены 7 задач. По его результатам лучшие участники (но не более 45% от общего числа участников раунда) будут приглашены на финальный этап. Для регистрации на раунд и участия перейдите по ссылке. Не забудьте заранее зарегистрироваться на раунд! Для опоздавших будет открыта дополнительная регистрация.
Зарегистрироваться на Отборочный Раунд 2 →
Соревнование открыто для всех в виде отдельного раунда.
Для всех участников обеих редакций этого соревнования будет пересчитан рейтинг.
Параллельно с Отборочным Раундом будет проведен открытый рейтинговый раунд для обоих дивизионов, в них могут принять участие все желающие.
Напомним, что согласно правилам раундов Codeforces во время соревнования ваши решения будут тестироваться только на претестах (предварительном и неполном наборе тестов), а системное тестирование состоится после окончания раунда. Обратите внимание, что претесты не покрывают все возможные случаи входных данных, поэтому тщательно тестируйте свои программы! После прохождения претестов у вас будет возможность заблокировать решение, тем самым получив привилегию искать ошибки и взламывать чужие решения, но отказавшись от возможности перепослать ваше решение при каких-либо обстоятельствах (например, даже если вы найдете ошибку или вас взломают). Со временем задачи падают в стоимости. После системного тестирования учитываются только полные решения. Подробнее про правила соревнований можно прочитать по ссылкам:
Регистрация на олимпиаду Технокубок еще открыта. Победителей и призеров олимпиады ждут значительные квоты при поступлении в престижные технические вузы России и ценные призы! Если вы — школьник 8-11 классов и пока не зарегистрировались на Технокубок, то самое время сделать это:
Зарегистрироваться на олимпиаду →
После регистрации на олимпиаду не забудьте зарегистрироваться на Отборочный Раунд!
В финал соревнования будут приглашены лучшие участники каждого из отборочных раундов (но не более 45% от общего числа участников раунда).
- Авторы отборочного раунда: Denisson, antonis.white, dimatimoshin23, __JustMe__, 4qqqq, Aleks5d
- Координатор: isaf27
- Спасибо KAN за помощь в подготовке раунда, а также MikeMirzayanov за замечательные системы Codeforces и Polygon.
- Спасибо ptd, Makcum888, Lyde, Monogon, manish.17, gjaiswal108, mathusalen за тестирование.
Удачи!
Разбалловка:
- Технокубок: 500 — 500 — 1000 — 1500 — 2000 — 2500 — 3250
- Div1: 500 — 1000 — 1500 — 2000 — 2750 — 3750
- Div2: 500 — 500 — 1000 — 1500 — 2000 — 2500
Раунд завершился. Поздравляем победителей:
Технокубок
Div1
Div2
Для тех, кто впервые на Codeforces: в таблице ниже вы можете найти примеры решений на всех поддерживаемых языках:
| Группа языков | Языки программирования / компиляторы | Примеры |
|---|---|---|
| C | GNU C11 | 10903473, 17029870 |
| C++ | GNU C++14, GNU C++17, GNU C++20, MS VC++, 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, Java 11 | 25491359, 23678167 |
| JavaScript | V8 | 35963909, 35681818 |
| Kotlin | Kotlin 1.4, Kotlin 1.5 | 25779271, 25204556 |
| OCaml | OCaml | 6157159, 1281252 |
| Pascal | Delphi, FPC, PascalABC.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 |
Note the unusual timings
My first contest with green color , I hope I will do well, good luck every one .
My 60th contest with orange color , I hope I will do well, good luck every one .
Ratism...
Do you seriously believe that it is that, or are you just going along with the meme?
And you didnt Participate :_:
11.35 am I would love to give the round if I woke up by thenಥ_ಥ who keeps round so early in morning that too on Sunday ಥ_ಥ ಥ_ಥ
"who keeps round so early in morning that too on Sunday"
A lot of people around the world usually have to wake up wayyyy earlier than 11:35am for a contest. It is what it is.
I do understand that its just my pov not meant to offend anyone.(^◡^ )
We have to postpone contest a bit. No way I can wake up that early
Which approach is better for practicing problems in problemset: topic-wise or difficulty-wise?
Difficuty wise , because when you are filtering questions according to a topic then you would already have an idea before even looking at the problem that this question can be solved using this perticular logic and this is not good, why i am saying that because when you are giving a contest you are unaware of the approach which is being used thats why it is better to sort according to difficlty then solve.
Sleep vs contest. Ape choose sleep.
It overlaps with Grand Prix of EDG :'(
The contest is right after Google kick start, look forward to it. (Finally a good time for NA competitors
Wish I had read your comment sooner. I didn't realize the time was in 24 hr format :_(
google kick start (or) codeforces div2
both
legends
Dare to join this contest just after Google Kickstart Round-H;)
Google kick stat round H plus codeforces round 755 makes me 5 hours of marathon coding competition.
UPD: It's the third time I become candidate master.
Overlaps with AHC006. If you fully participate CFR755, only 2h40m will remained for AHC006.
Scoring distribution still not announced.
Too lazy!!!!
Maybe we need more concrete description to replace "closer".
very few registrations this time.
Автокомментарий: текст был обновлен пользователем isaf27 (предыдущая версия, новая версия, сравнить).
How can someone hack a problem even after I locked it ?
After locking, you cannot submit again and can hack other participant's solutions. If not locked, you can submit again but cannot hack other participant's solutions.
Thanks to this comment I hacked 7 people.
Sorry for asking this, but I accidentally submitted a WA after an AC. So the AC solution done before will be counted for results right? Or is last submission for that problem considered regardless?
Your AC solution counts, check standings :)
What is the hack for C?
1
1
1
0
I used this
Multiple solutions passed which weren't intended. So basically it wasn't just one particular hack or idea, but it was just weak pretests.
input:
This will hack the code that only judges the case of no solution is $$$b_i-a_i>1$$$.
But sadly I found this after I locked my solution :(
I noticed two.
Div1B/2D is a really nice problem, bricked for a really long time trying to figure out how to solve the problem in just 1 pass of binary search, but the observation needed to solve it is cool af.
How do you solve it in one pass?
Difference between $$$query(1, k) - query(1, k-1)$$$ is equal to the $$$k-j+1$$$.
Thanks :) Couldn't figure out during contest but the idea is actually very beautiful nonetheless.
Binary search on ranges of the form $$$[1, x]$$$ to find $$$k$$$ (smallest index with same number of inversions as range [1, n]).
Now lets realize that since all elements in $$$[i, j - 1]$$$ are smaller than those in $$$[j, k]$$$, the number of inversions is exactly $$$\frac{y \cdot (y - 1)}{2} + \frac{z \cdot (z - 1)}{2}$$$ where $$$y = (j - i)$$$ and $$$z = k - j + 1$$$.
Now if we query the range $$$[1, k - 1]$$$, the number of inversions is $$$\frac{y \cdot (y - 1)}{2} + \frac{(z - 1) \cdot (z - 2)}{2}$$$, or exactly $$$z - 1$$$ less than the previous value.
So we now have $$$z$$$ and can get $$$j$$$ from it.
We also have the total, so we can just binary search to find $$$y$$$ that satisfies $$$\frac{y \cdot (y - 1)}{2} = total - \frac{z \cdot (z - 1)}{2}$$$. So we can also get $$$i$$$.
Also the part of binary searching y can be eliminated using the main observation by querying [1, j-1] and [1, j-2] and subtracting the second from the first to know length of [i, j-1].
Oops, seems like I overkilled that part lol.
If you binary search two times then won't the total number of queries be $$$2 \log_2(N) \approx 60$$$ ?
The second binary search in his comment is to solve an equation not to query.
True, didn't realize that.Thanks!
The second binary search is finding the largest $$$y$$$ such that $$$y \cdot (y - 1) \leq total - \frac{z \cdot (z - 1)}{2}$$$. Just a local calculation, no queries or anything.
You can just do $$$\sqrt{total - \frac{z \cdot (z - 1)}$$$ and check close by values if you aren't paranoid that will somehow make you FST lol.
That makes sense, thanks!
Fragile pretests on C lol. Hacked 8 submissions
ape hack . ape happy
I hacked 3 using following test:
1
3
4 4 4
3 3 3
Anc I jumped from rk~150 to rk~50 lol
Is that weakppforces?
The pretests in C were reasonably weak. I hacked my way from ~1000 rank to ~350 (And so did a lot of other people).
hackfor C es!
Is div-2 D some sort of ternary search?
I used binary search.
ko_osaga did it again!
Where is E from?
Hi, it's NEERC 2015 Northern Subregional K. It is not very equivalent, but the main observation for that problem can be applied directly. Shoutout to ainta for recommending me this problem.
You have to see if the cylindric-shaped curve encloses all points.
The area enclosed by such curve can be represented as an intersection of an area within distance d from the ray shoot from point $$$i$$$ to $$$j$$$ and $$$j$$$ to $$$i$$$. You have to determine if such area encloses all points, and that is a significantly easier problem (compute the intersection of cyclic interval)
Also, at least one problem in CF and a recent WF problem related to "distance to line", the only difference is to handle case when distance to segment is to one of two ends, it is easy by sweeping and two pointers.
Hi,
Even though I probably didn't have the right algorithm on the E, the statement was a bit ambiguous on the issue of size 1 segments and other details (e.g. can we increase the ends without increasing the only values adjacent in the subsegment). I rather liked this exercise even if my performance on this competition does not exemplify me :)
Problem C and D are easy to come up with . But really hard to implement and debug ...
Agreed, on problem C it took me:
The basic idea of parity sums and prefix not becoming negative is fairly standard. I'm pretty sure there was Div2 problem a while ago that required exactly those two observations.
Edit: Apparently Div1C is extremely easy to code if you use k-th order statistics. See this submission — 135379742.
Thanks , I know few about pd_ds. I think I need to learn more about it .
Could you please share any hints about problem div1 C, thank you very much.
Hint: you can perform the operations from left to right , and find out when the array is possible to clear . Use some data structure to maintain it !
I'm interested in what happened to antontrygubO_o
sad, he is already red now
here's new avatar for Anton
I remember that his avatar was yellow long long ago?
I think this is really ...
I just wonder what happened do Anton,too.
Nothing special, waking up at 7AM and lack of practice lately :(
Today I did my first hack on Codeforces. Felt a little too good to be evil, lol.
Can you please explain the logic behind solution of problem B??
First thing to figure out is that when you make rectangles of dimension 3*1 you need minimum possible colourings. So, we divide the base rectangle into as any 3*1 rectangles possible and we will be left with (n%3)*(m%3) sized rectangle, now, the possible rectangles will be 2*2, 2*1 and 1*1 . First 2 cases will have half tiles coloured and the last case is prohibited so what we do here is we spare 4 tiles in one line and divide the rest all in rectangles of size 3. The remaining 4 will have 2 tiles coloured.
If I was difficult to understand. Here is my solution- 135359905
Thank you brother got it!
Cries to death
Ready to get FSTd Solution to C cannot be so simple
SAme here
I didn't manage to remove cheaters in previous rounds yet. I will do it soon, but as a result, it is likely outcome that someone will change their division of participation in round 755. Regardless of the new division (after removing the cheaters), your participation will be rated in the exact division that you actually participated in round 755. That is, even if after removing the cheaters you change the division, then round 755 will remain rated for you.
I am not upset that pretests of C were weak ,I am upset that I didn't attempt to hack
I have the same feeling, I found the hack very soon but I was so scared to try because it was my first time trying to hack, by the time by I gathered the courage 3 hackable solutions were hacked in my room so I had only 1 solution to hack.
Yeah I also would have felt little nervous as I never hacked before ( It always feels nervy in an unknown territory )
I wonder if Div2.C(Div1.A)'spretest is SO WEAK Because I add abs() and go through pretest as well
am disappointed because weak test cases in problem C
Hello All, just needed your attention here. I submitted C once and it showed me an accepted verdict again after a few minutes I again submitted with a slight different approach and it showed a passed verdict.Just when the contest got over I saw a skipped Verdict and queued verdict. May I know why it is happening so.
Only the last accepted is checked against systests
Is fact what solve with complexity O(n**2) getting AC in Div1C OK? 135376136
Hacked. It seems that the test cases are too weak.
weakpretest :(
I never wanted be hacked more than now
div2C WA on 73 test. I hate my life
Video Editorial for A
Did anyone else feel this round was easier or it was me who did 3 problems on my own without wa for the first time?
This kind of contests should extinct from Codeforces.
There's no reason for these boring&too difficult&Weak pretests problems&contests to appear on cf.
The participation rate has dropped rapidly and too difficult A will make the ranklist unfair.
A is difficult only if you failed your algebra class in school
My point is not on A.I decided to solve it after D.
now found it the worst decision ever.
More,only 5000/9000 participants submitted A.It's not a good thing for cf.
A. Math, Was quite tough to me
B. It could just as well be A
C. It can be solved with one-liner, why is it C and why there are so many hacks and fst?
D. Nice problem, enjoyed solving it
A. I still enjoy solving problems related to algebra, interesting for me.
B. Problem was meh, div 3 type.
C. Really bad C. This problem is meant for div 3A. How did this even...
D. This problem looks interesting
For problem B, I realized we need to take as much as 1*3 as possible so my solution was based on that. I see some solutions like
cout << (n*m+2)/3 << '\n';how the solution got reduced to that !?Hi ! In fact the answer is ceil(n*m/3), and with few attempts, you can realise that this is equal to floor(n*m + 2/3).
In total we have $$$n * m$$$ little squares. You mentioned right, that we need to take as much $$$1 * 3$$$ rectangle pieces as we can. Now $$$(n * m + 2) / 3$$$ is a way to find how much $$$1 * 3$$$ pieces we will have plus check if there is something left, so basically it is [ $$$(n * m) / 3$$$ + remainder ], where remainder is one if $$$n * m$$$ is not divisible by 3. That means that we are left with $$$1*2$$$ or $$$1*1$$$ rectangle and in both cases we will need to paint exactly $$$1$$$ more sell with blue
Thank this contest let me become a candidate master.
I think problems are good.
But the pretest of C was terrible and there were so many hacks.
So weak pretests on problem C!
I think D1D is just this problem with much harder implementation.
So weak pretests on problem C !!!
Huge difference between no of accepted solution div2 C and D. There should have another problem in middle difficulty.
Here are the video Solutions to the first 4 problems of Div-2 in Case you are interested.
Finally turned green..WohooooOOo
Finally turned green after being specialist and expert. Wooohoooo
Why such a huge gap in the difficulties of (ABC) and D in div2..A newbie could also solve upto C and D was very tough for a specialist(maybe for an expert too)
D was pretty much as always
The gap is because C was easier than it should have been. In general C is intended for cyans
how come no editorials?
This has to be the most unbalanced div 2 round till date
Weak pretests for problem C :(
waiting for editorial.
trash round bad pretests C + no balance
My solution
Can anyone please tell me why this is wrong ?
It passed the pretest but now it is showing WA
I cannot even understand the test case it failed
like why it is failing why its o/p is NO it should be YES isn't? Am i missing anything or my understanding of the problem is flawed?
you lack of consideration of b[i] < a[i]
Could anyone tell me what's wrong with my C code? I can not find out and I am wondering whether it is necessary to sort. 135383484
try this TC and you'll realize why is it not working
1
2
1 2
2 1
Since editorial is late and for some reason no one is discussing solutions, could someone tell me what is the idea on how to optimize D2E(D1C) from O(n^2)?
I’ve always thought that rounds based on technocup are difficult and need a good knowledge of advanced algorithms, but i think this contest is a bit different , problems A,B,C are the same as a div3
Any hints on how to solve B of div 2 :)
Think of rectangles of rectangles of area 3
anyone can tell me intuition behind B problem: ans=((n*m+2))/3; why is it working?
as a Python user, this contest was pretty disappointing. The tutorial Div1D and E solutions have essentially no hope of running in the given time limits in Python because of the absurdly large constraint allotments.
Pretty good contest, I like this type of style, only on suggestion, the gap between some problems might be a little too big.
hello every body my picture is beauty full