<almost-copy-pasted-part>
Привет! В 30.08.2019 17:35 (Московское время) начнётся Codeforces Round 582 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
UPD: Спасибо Артему Rox Плоткину за тестирование раунда!
UPD2: Разбор опубликован!
[deleted]
I hope I will get some positive rating from the contest.
YOU WILL NOT!!!!!!!!!!!!!!! I AM SURE THAT AFTER 5 CONTESTS YOUR RAITING WILL BE BELOW 750!!!!!!!!!!!!!!!!!!!!!1
Why are you being mean?
You are not even blue yet LMAO
In my real account my raiting is 1700+
No one cares..
Just learn to be nice to people
I am just trolling in all my comments(not in posts).my small contribution can proof this. But this comment is not trolling and is true
First,div3 after becoming expert hope my rating remains constant.
your rating will remain constant because div.3 is unrated to experts and higher like you and me.
Raiting does not matter, matter only nice girls!
Now I can say "I won't lose my rating ANYWAY!" proudly :D
Now I can say "I won't gain any rating ANYWAY" sadly :(
This will be my first contest. I hope I will do well and good luck for everyone for the same....
Hope the ranking of problems be better from the last contest.
After this contest,I think I will be a expert.How excited I am!
Hope you will be an expert
Thanks!
A japanese friend told me that reaching blue in a div3 (and yellow in a div2) is dishonorable.
I thought it was orange :(
to my eyes: yellow = master, orange= international master
Vovuh...master of preparing div3 contests...
I'm still not a master unfortunately :(
How did you write "master" like that?
I'm sure you can see the html-code of my message to understand how I did it :)
master
will be master
It means that CF support html code.
master
My Final exam is going on... But I won't miss div-3.. Div-3 is love..
Vovuh's rounds are always good!
Yours are also good.
Comment from Div3 #579![](/predownloaded/6c/2f/6c2f3354e8686018cea8d6296babdc54ef668cf3.png)
Now tell Codeforces isn't ratist :c
Div 3 rounds are better than "Educational rounds" in teaching the most valuable skill for Codeforces, namely SPEED.
Depending upon what your purpose. If you have high rating is seem not :)) But I like Div3 rounds too :3
Hopefully I will become back to expert soon. I have been very disappointing in myself recently.
First unrated contest for me. XD
Hello,Guys. This is my first contest after a lot of time. I studied Quantic Math in this period. I think that I can beat majority of the Div3 contestants even tough I am at 1361. :)
Letsssssss GOOOOOOOOOOOOOOOOOOOOOOOO
LoOooOoOLoOOooOoLoOOoOoOOooOooOOLoOooOOoOOoOOL. ROFL. LMAO. You think majority of contestants can only solve less than 3 problems?↑that's just bullshit
All the best. The time I solved 5 problems I didn't really expected that. it was pure luck. one lucky contest will be enough to bring you up to specialist or even 1500+. Good luck and have fun! :)
Note that this is vovuh's round. It's likely to have problems with multiple queries. So guys, a notice for you, remember to clear the data of the last query before answering the queries!
Do I have to register to join this contest? (My current rating is under 1600)
Of course. You have to register if you want to take part in a contest. For those rating equal or more than $$$1600$$$, they will be registered "Out of competition" for Div.3 contests. That is, their rating will remain unchanged after the round and they won't be listed in the official standing board.
Alright, thanks for the information
Yep
I have a great idea! Make div3 rated for (blues,) purples and yellows but update ratings only if the delta is negative.
Why don't do the same thing to blues? They are unofficial for div.3 as well :(
sorry, I thought blues are also div3.
Let's escape this division guys! :D
Finally, not a Mathforces Round.
Whoa LGM and all around god Benq is writing this Div 3 contest :O
P.S Here was bad info
I don't think you should write that during the round.
My fault
D2 solution accepted with 1900ms
Me: heavy breathing for 14 hours
Ооочень хороший кантест спасибо!!
Unofficial editorial by me.
A (Chips Moving)
It is easy to see that there is no way for even valued chips to move to odd positions without paying, and vice versa. Let's say there are E even valued chips and O odd valued chips. The answer is min(E, O).
B (Bad Prices)
Since we want to know the minimum price in the future, lets iterate in reverse and keep track of it. When we are considering the i-th price, we already know the minimum price we saw.
C (Book Reading)
We write K = floor(N / M) numbers, the numbers are f(k) = k * M % 10 for k = 1, 2, ..., K. These numbers f(k) must repeat every 10 instances of k, that is f(k) = f(k+10). Let k = 10 * q + r. We write q numbers of f(0), f(1), ..., f(9); plus another r numbers f(1), f(2), ..., f(r).
D (Equalizing by Division)
For each number i in reverse order, lets see if all numbers could equal i. To do this, we maintain at each number, an int[] count[i] of how many numbers reached here by 0, 1, 2, ..., 18 divisions of 2. Then, for a number i with some count, we can calculate if K numbers could equal i in a greedy way: count[0] of them got here in 0 divisions, count[1] of them got here in 1 division, etc. and see how many divisions we need to find K numbers.
Afterwards, we divide the number i by 2, which increases the counts at count[i//2] appropriately.
E (Two Small Strings)
Its always possible. Consider the graph with nodes 'a', 'b', 'c' and all possible directed edges (even self edges). There are three types of edges: forward edges 'ab', 'bc', 'ca'; backward edges 'ba', 'cb', 'ac'; and repeat edges 'aa', 'bb', 'cc'. Our goal is to walk around this graph without touching the banned edges S or T.
Evidently, if we don't ban forward edges, we will answer 'abc' * N. If we don't ban backwards edges, we will say 'cba' * N. So lets say we ban a forward edge and a backwards edge. Without loss of generality, we could say the forward edge banned is 'ab'. Then the backwards edge is 'ba' or 'cb' or 'ac', and we have an answer 'b' * N + 'c' * N + 'a' * N.
F (Unstable String Sort)
We have 2N — 2 inequalities S[P_i] <= S[P_{i+1}] and S[Q_i] <= S[Q_{i+1}]. For each inequality S[u] <= S[v], draw a directed edge from u to v. Notice if a path exists from u to v, it implies S[u] <= S[v] by transitivity. If a path exists from u to v and from v to u (ie., u and v are in the same strongly connected component), then S[u] <= S[v] and S[u] >= S[v], so the letters S[u] and S[v] must be equal.
We can use Kosaraju's algorithm to find the strongly connected components. If there are less than K strongly connected components, the task is impossible. Otherwise, we could greedily fill the answer.
If S[u] <= S[v], draw a directed edge from u to v.
If x occurs before y in P, and x occurs after y in Q, then a path exists from both x to y and y to x, ie. x and y are in the same strongly connected component, so S[x] == S[y].
We can use the above fact to deduce when there may still be P[j] with j > i such that S[P[i]] == S[P[j]].
G (Path Queries)
Sort the queries. Every time q increases, we can only add edges to the graph under consideration. Therefore, we only need to maintain the correct answer every time we add an edge to the graph.
Lets say the graph is a set of disjoint connected components, each component having s_i nodes (s for size). Then, the answer is sum_i (s_i choose 2), which we can write as (1/2)(sum_i (s_i)^2 — sum_i s_i) = (sum_i (s_i)^2 — N)/2. Thus, it is only necessary to maintain S_2 = sum_i (s_i)^2.
Whenever we add an edge, if it connects two disjoint components with sizes sx and sy, then S_2 gets increased by (sx + sy)^2 — sx^2 — sy^2 = 2 * sx * sy.
Is this official editorial? I am confused why its not part of the post.
It’s unofficial
Your implementation of G has failed on a test in which function find makes $$$O(n)$$$ recursive steps. I believe it would be better to use rank heuristics here.
thanks Vovuh, it was cool contest.
Hopefully I go back to blue after open hacking is done!
How does my D2 pass in time ? 59740108.
Isnt the complexity O(2*10^5 * K * log(K) ) while iterating the map since maximum numbers in map can be 2*10^5.
Am I missing something or are the test cases weak ?
Heh. I'm TLEing when I really shouldn't be.
No, your complexity analysis is wrong. The total number of elements across vectors in the map is at max Nlog(a[i]). So, you can say that your amortized time complexity is O(Nloga[i]logN)
Can anyone tell me why this Java solution for D2 is TLEing?: 59748534
Shouldn't my solution be NlogN?
Java Arrays.sort() uses quicksort which is O(n^2) in worst case
Thanks! I was unaware that Arrays.sort() was so bad :(
Yes! I was able to verify that using Arrays.sort was the problem. I implemented mergesort, and it passed in 202 ms.
Arrays.sort in Java has a worst case running time of O(N^2). Converting your nums array to arraylist and using Collections.sort will make your code pass comfortably
https://pastebin.com/7UtCkk9u
TLE before even beginning your algorithm: https://mirror.codeforces.com/contest/1213/submission/59763079
G — кайф, С — не кайф
А в чем проблема С? Почему не кайф?
Потому что я даун
Бывает!
In B i accidently took array smaller than the limits so i tried to hack myself and i can't hack it can anyone help me?
Difficult to hack, only hackable if those memory locations are assigned next to OS memory locations. Keep trying :P
Can anyone tell me why my problem G TLE? I think it is O(N + M) (assuming that dsu operation is constant). Is there any infinite loop possibility?
59762107
return (pr[x] == x ? x : root(pr[x]));
this line needs to be
return (pr[x] == x ? x : pr[x] = root(pr[x]));
omg :( silly me
Im actually used to code it like this
thank you XD, i think im just too tired right now..
Will those hack tests be included in final tests? What if my code fails in one or more of them?
Yes, if you not pass all test, you will be hack. =)))))))))
He is trolling lol. if your code fails in one of them, you get WA!
Ah! makes sense.
Problem E :
36 cases o.0 It's so afraid :<
1st solution is of Ashishgup right??
Solution for F
if d occurs at i position in a and j position in b then it can be said that
s[min(i,j)]=s[min(i,j)+1]=.......s[max(i,j)] make an array of intervals and add every [i,j] in it
sort the array
now merge the intervals which share common index
if length of the interval array is less than k then it is NO
else
if length of the interval is greater than 26 then merge all intervals from 26th index
assign letters from a to each interval
now sort intervals on the basis of their position in A.done AC
Why the following brute force solution for D1 gives WA in test 5. https://mirror.codeforces.com/contest/1213/submission/59764056. Can someone have a look.
русский Я очень люблю раунды vovuh. Спасибо! 1213E - Две маленькие строки удивительно.
Ελληνικά Μου αρέσουν πολύ οι γύροι vovuh. Ευχαριστώ! 1213E - Две маленькие строки είναι εκπληκτικό.
English I really like the rounds vovuh. Thanks! 1213E - Две маленькие строки is amazing.
Español Realmente me gustan las rondas vovuh. ¡Gracias! 1213E - Две маленькие строки es asombroso.
This summer vacation I'v joined lots of cf's contests. before the new term , I wish I could be an 'expert'.
Очередной настоящий, качественный educational раунд для div3. Спасибо!