Привет! Во 08.03.2022 17:35 (Московское время) начнётся Codeforces Round 776 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 7-8 задач, которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Мы постарались сделать приличные тесты — так же как и вы, мы будем расстроены, если у многих будут падать решения после окончания контеста.
Вам будет предложено 6-7 задач и 2 часа 15 минут на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в пяти рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацией нашей работы. Задачи были придуманы и написаны командой Университета ИТМО: MikeMirzayanov, MisterGu, myav, Gol_D, Aris, senjougaharin, мной Vladosiya.
Также большое спасибо mango_lassi, espr1t, karemo, starboy_jb, Fly_37, omikad, Katya_Goryachkina, Omja, teraqqq, oversolver, Jostic11, yorky, _4dr_ и doreshnikov за тестирование раунда и весьма полезные замечания.
Всем удачи!
UPD: Поздравляем девушек с Международным женским днем <3.
UPD 2: Разбор
finally a div3 contest after a 2 month break
mango_lassi tested so good he got mentioned twice.
Good luck to everyone !
This will be an important contest for me, the wait has been long, let's hope to turn blue.
Me too.
So glad I finally got blue
Congrats!
This will be an important contest for me, the wait has been long, let's hope to turn Green!
You have solved so many problems, I will add you to my friend.
rahul_rax You became expert without participating in this round..!
Yes, I just saw, after plage check, I got a +1 rating, and reached expert. All the best for today's round.
This round is not rated for you now
Yes, This will be my 1st unrated round. Yaya!!
For me too. Congrats
Bro plz tell me why my ratings not increased I have given the contest and have ratings under 1600
Ratings are not updated for anyone till now
Only expert for whom the round is rated.
First unrated div3 for me, yay :)
I might become pupil after this round. I am excited :)
Sure you can get what you want!
1
Guess who is skipping school tomorrow hahaha
First div 3 contest for me yay!! thanks to all the testers and it will be challenging as we have to solve more problems in less time!!
Is this challenge suitable for beginners?
Yes, significantly easier than Div2s and Div1s I would say
Div3 contest, long time no see
I am happy to participate in a contest on by birthday. I wish to be pupil after this contest. Wishing everyone positive delta. GL&HF!!
Happy Birthday
Oh its your b'day? Here's an integer array as a gift. [1,2,3]
Thanks, @nyet and @happy_new_year_2022
As a first time tester for a Codeforces round. Please give me some upvote :).
Good Luck and High Rating.
Good to see a contest after every one two days. Well done codeforces!!
The contest is vital for me,I want to be blue.
Hope I can solve today's problems and get my handle colored.
Nice gift for March 8)
Very excited for div3 after a long time. All the best everyone.
Dear contest, make me > 1700 rated pls. thx in adv, wil pay the <> by tomorrow evening
Vladosiya's Div 3 rounds are really good. Looking forward to some great problems in the contest.
Nice gift for 8th of march , and here's my best wishes to you on International Women's Day 2022 ! Wishing a very happy Woman's Day to strong, intelligent, talented and simply wonderful women of this world! Don't ever forget that you are loved and appreciated. And also good luck on Div 3 !
Good luck also for mediocre and normal women (not only talented and strong ones) which also deserve respect
Can anyone help me understand why untrusted people will not be included in the rankings? The round is rated for anyone having a rating less than 1600 anyway so how is the decision having any effect on rating changes?
Наверное всё-таки 1600?
нужно быть < 1600 на данный момент, и < 1900 за всю историю участия в контестах
HahahaHaIluminatiHa11-2023
I hope to be the best myself
Good luck at International Women's Round #1!
Plz, no number theory in problems
Finally my first participation as unrated one.
implementation forces
It took me 20 minutes to understand the statement output 2 numbers in next n lines of the problem C
I think C was written so bad
Really cool round. Thanks to creators
Logic for C please?? is it implementation based problem
Take 2 * n minimums and after sort them by coordinate
how can we sort the array in a way that we would know the index of every element before sorting with O(n log n) solution ?
Just store indexes somewhere, for example make a tuple (x, w, index)
I used map, where key is w and value is index in not sorted vector
when i read E I thought it's too easy but then i realized there are things i didn't count in my solution and it was too late
i thought too what ever i was thinking should work but it didn't. then i changed my perspective and did some implementation with
multisetto check what would be answer if i change $$$i^{th}$$$ exam date.I think you should only change the smallest value but I didn't check that maybe if i delete a1 for example and put it somewhere else then maybe a2-a0 is the new smallest value
yes you are right only difference can be made by removing minimum gaps. also need to make sure there are two ways to remove each gap that is not the left most. and also the way i implemented it didn't hurt to check every index, so to keep code a bit simple i didn't think of optimizing on that
Problem G: Counting Shortcuts is a great extension of ABC211: Number of Shortest Paths
In fact, you only need 5 to 6 lines of code changes in the Atcoder version to get it working.
I've summarized my approach for ABC211: D in this comment
How to extend it to this version?
First, break it into 3 parts. If the shortest path is of length $$$\delta$$$, we need to compute paths of length $$$\delta - 1$$$, $$$\delta$$$ and $$$\delta + 1$$$. Computing $$$\delta - 1$$$ is a trick question, you should figure that out yourself. Computing $$$\delta$$$ is same as ABC211:D. So, we just need to compute paths of length $$$\delta + 1$$$.
As mentioned in the previous comment, edges in a BFS tree can only exist between nodes of same level (horizontal edges) or consecutive level (vertical edges). If we observe a shortest path, it needs to descend the tree at each stage, i,e, it can only contain vertical edges. A path length of $$$\delta + 1$$$ implies that we added one extra edge in our shortest path. Notice that this extra edge cannot be a vertical edge, as we will miss the target vertex by 1 height. So, we are allowed to add one edge between nodes on the same level. This simplifies it to,
Let's rename the DP of the previous problem to $$$dp\_tight$$$, and the DP array of the new problem to $$$dp\_loose$$$.
$$$dp\_tight[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are not allowed to use unnecessary edges.
$$$dp\_loose[node]$$$ is the number of ways to reach $$$node$$$ from $$$source$$$ when you are allowed to use exactly one extra edge.
To compute $$$dp\_loose[node]$$$, we need to consider every edge on the same level (horizontal edges), and increment the $$$dp\_loose$$$ of one vertex by $$$dp\_tight$$$ of the other vertex. Since we should precompute the DP values of all nodes on the same level before populating DP values of next level, we can use a temporary queue for each level (Although I think we can do it in one pass too).
Time Complexity: $$$O(N)$$$
I think you mean Problem G.
Feel like output for C could have been simplified without taking away from problem difficulty. But pretty fun contest anyways.
Anyone else ? Who wasted 10 minutes thinking about output in C because of poor language
I will reach expert if not hacked.
Can you explain your approach for E?
take the better one of the above 2 cases and compare it with the smallest key and update answer. During step 2, remember to update your map accordingly: first remove deleted gaps and add newly generated gaps. After processing a[i], restore the map for the next element.
I had this idea but forgot to take care of the special case where if we put a[i] at the end on d, it is just d — a[n] — 1 instead of (maxGap — 1) / 2. Feels bad :(
I've added some comments in my submission, the idea is fairly straightforward: 148911439
i tried using map in C++.... my last brain cell is trying to figure out why my code mutates the map in each iteration, tried using delete when key's value is 0, but when i add some value to it, keys are not appearing back.........
edit: i mistakenly deleted the value of the map not the key T_T, still got WA tho
I ran into a similar key not found error during contest. I think it is because the way I updated the sorted map.
but would'nt the complexity become more O(n*n) or O(n*nlogn)? That should give tle. You are doing this O(n) computation for every a[i].
it is O(N * logN), each iteration we uses 6 map operations (3 insert, 3 removal). Building the maps takes O(N * logN) then for each iteration, it takes 6 * log(N) time.
I binary searched the answer (maximum μ possible by shifting the element with minimum rest days before it). You can see that for some μ: all smaller values are possible to achieve, this forms an array of True and False: T T T T T F F F F ...
So now you can apply binary search to find the last T (Last T is maximum possible μ). Now, to find if the current candidate for μ is T or F. You can write a function F(M) which will return True/False if rest days before A[i] <= M for all i. You can try to achieve this by removing the element E with smallest rest days before it and placing it in between any two elements with maximum rest days.
My implementation for F() is very bad and I believe you will find much better code for understanding in top standings. Please ask if there is anything you didn't understand.
C is the one of the worst questions I have seen in a while. The last paragraph of the problem is so confusing, even looking at samples didn't help. I had the idea in 5 minutes, but took 4 WA's on test 1 just because the output formatting is wrong. Also, what does this line have anything to do with anything?
This just makes the problem even more confusing. And lastly, would it kill you guys to give the initial points as sorted? So much extra implementation just to print the indices of the points in original order after god knows how many times I used sort().
On the other hand, the problem itself and the idea behind it is nice. I just don't like the fact that I have to spend 10 minutes on thinking about the solution + implementations and then 30 minutes to properly format the output just so that it passes samples.
Question C was worded so poorly!
too heavy implementations
ImplementationForces
Open hacking means if I fail in hacking a solution it would not negatively affect me?
Yes, by hacking you can only win.
Can we get -1 in D?
No. It is always possible to sort the array. Think of it as bubble sort, but use rotates instead of swaps. Every time we move the greatest element to the right, and repeat the same process on the remaining elements until the array is sorted.
Can you elaborate on what do you mean by Every time we move the greatest element to the right ?
no, it is always possible to sort an array by rotating its prefix. actually what i have observed, this fact is used in quite some problems. For instance, this problem
Thanks for sharing. I wrote a -1 condition in the contest without thinking much
It's better to have it and don't need it than need it and don't have it.
Is it necessary for the answer of Problem G to module 1000000007?
Yes
It is easy to construct a test case for which answer is $$$2^k$$$ if $$$n=3k+1$$$.
is there a solution for E that does not involve too many caseworking? my solution had to consider like 6 cases to pass.
Also, props to the very strong sample case that actually helped a lot
Binary search, to check if x is okay find first gap with length < x and try to remove one of endpoints of the gap. Try to place the removed exam in midpoint of gaps, or at the end of session.
you don't really need binary search tho
you can check out my solution, I made it pretty similar to yours. solution
Problem G is very similar to this problem, with the subject of weighted directed graph;
Additionally, more sophisticate version is NOIP2017-S P3953, with the restrict of weighted directed graph($$$w_i \ge 0$$$), to calculate the number of ways of path length no more than minimum_path + k.
It is the exact same as the problem [here](https://github.com/T1duS/CompetitiveProgramming/blob/master/Olympiad/IOITC/2020/AlmostShortestPaths%20(EN).pdf ). The same link contains the intended solution as well.
It's funny that there is no pretest with answer >=998244353 in G:)
Yes, ridiculous
Is there an O(n) time complexity solution for D?
misread D's constraints, for almost 1.5 hrs was trying to find O(n) for D but couldn't:(
Dunno, but you can do it in O(nlogn) with implicit treap.
How to solve G? any hints?
dp on Bfs tree
Video Editorial for A-E for anyone looking
There is an issue with the problem G: the variable $$$t$$$ has been reused. Please fix immediately. Highest priority.
Hints for problem E ?
I think the way I solve wasnt the expected solution but try this:
Which exam should you remove for the optimal solution (there are one edge case but we'll discuss it later)
Where should you place it?
That's pretty much the problem, you should look the one that have less rest before it and remove from the array, then let's look for the biggest gap between two exam and divide it by two (you'll split this into two with rest of equal size) or the last gap (last exam to the end) and place the exam you removed in the middle of the biggest gap (or at the day d).
Sometimes (like in the sample test) it is optimal to do this process with the exam before the one with less rest, so we'll also try with it and keep the greatest value.
Here is my code: 148929577
can we do d in o(n)?
As we think it can't be solved faster than O(n * log(n))
hope to be Specialist
Oh, I submitted B for three times. I might not be Specialist
Yesterday,I used 998244353 as the modulo and passed the pretests of G,but today my submission was hacked.
The pretests of G were so weak that I used 998244353 as the modulo in this problem and passed them!
But today I was hacked!
fun fact:the answers to pretests after 12 are all 1 :)
My rating is 1200. Why was this round unrated for me?
Is there any indication that the match has been unrated? My friends and I have found that this match is
Unratedfor us. A lot of thanks if you could reply to me. :(after system testing it will be
ratedWhat is system testing?
That is testing your code with all successful-hacking datas.
thanks. how long does this usually takes?
In this contest, I found an act of unfair means where the user D_K_307 hacked his solution from a fake account to increase his score. Is there a way to report such things ? Proof here
In div.3 contest you can't increase your score with hacking
Cool, but still it's a wrong practice and will be effective for some contests. I have seen some users in past too doing this.
I did not have any Idea about hacking So I just tried it in div.3 contest Beacause I don't know this. Sorry For that.
After the system testing. Still didn't change the rating...
Waiting for the same. Expecting increase in rating but not scared if it goes unrated or something :(
ya same bro :(
Man I was about to go expert, why this rating haven't changed yet
I would be close too. :(
The rating predictors ain't couting out the not-trusted participants.
So, I think +10 extra will be definitely there.
Hope we both get the DARk BLUE.
<3 <3
It's there in the unrated graph ;(
Mr. Vladosiya I think it is your best contest.Make more contests
Waiting for rating changes with 29138 others :)__ Edit: Released yaay
The system told me that I cheated because of my Problem G solution coinciding with others. However, this problem had a same version on http://poj.org/problem?id=3463 ,and I had finished the problem with the help of a blog https://www.cnblogs.com/xingxing1024/p/5224363.html .So I use the code to finish problem G.Is it illegal?
The blog was posted in 2016,I cant understand why i am cancelled in this round...
my problem d is coinciding with others but i did it on my own what can i do in that case !?
The system told me to cheat because my g question is highly similar to others, but this question is written with reference to a board written before. The link is: https://www.acwing.com/problem/content/385/ , I did this question six months ago. I hope I can get a reply. Thank you.
[deleted]
Nice contest, I really liked it! I went from newbie all the way up to specialist :D!
is there an Editorial?
There's a piece of news floating around on Reddit that Russia is gonna cut off the global internet from 11th March. Is it correct? And is it gonna affect codeforces?