<almost-copy-pasted-part>
Привет! В 22.01.2020 17:35 (Московское время) начнётся Codeforces Round 615 (Div. 3) — очередной Codeforces раунд для третьего дивизиона. В этом раунде будет 6 или 7 задач (или 8), которые подобраны по сложности так, чтобы составить интересное соревнование для участников с рейтингами до 1600. Однако все желающие, чей рейтинг 1600 и выше могут зарегистрироваться на раунд вне конкурса.
Раунд пройдет по правилам образовательных раундов. Таким образом, во время раунда задачи будут тестироваться на предварительных тестах, а после раунда будет 12-ти часовая фаза открытых взломов. Я постарался сделать приличные тесты — так же как и вы буду расстроен, если у многих попадают решения после окончания контеста.
Вам будет предложено 6 или 7 (или 8) задач и 2 часа на их решение.
Штраф за неверную попытку в этом раунде (и последующих Div. 3 раундах) будет равняться 10 минутам.
Напоминаем, что в таблицу официальных результатов попадут только достоверные участники третьего дивизиона. Как написано по ссылке — это вынужденная мера для борьбы с неспортивным поведением. Для квалификации в качестве достоверного участника третьего дивизиона надо:
- принять участие не менее чем в двух рейтинговых раундах (и решить в каждом из них хотя бы одну задачу),
- не иметь в рейтинге точку 1900 или выше.
Независимо от того являетесь вы достоверными участниками третьего дивизиона или нет, если ваш рейтинг менее 1600, то раунд для вас будет рейтинговым.
Спасибо MikeMirzayanov за платформы, помощь с идеями для задач и координацию моей работы. Спасибо моим очень хорошим друзьям Дарье nooinenoojno Степановой, Михаилу awoo Пикляеву, Максиму Neon Мещерякову и Ивану BledDest Андросову за помощь в подготовке и тестирование раунда.
Удачи!
Также хочу сказать, что участники, намеренно отправляющие неверные решения и взламывающие их после окончания соревнования (пример), не будут показаны в таблице лидеров по взломам.
</almost-copy-pasted-part>
А еще у нас есть необычная, но приятная новость! Слово нашим друзьям и партнёрам из Harbour.Space:
![Hello Muscat](/predownloaded/c0/b9/c0b9295197c8367bcb2bf767b9177e28a2a44c17.jpg)
Привет Codeforces!
В качестве специального приза за Codeforces Round #615 мы разыграем три бесплатных участия в Hello Muscat ICPC Programming Bootcamp, который состоится 19-25 марта (Оман) — полное покрытие оргвзноса, проживания и питания по системе «полупансион» на весь период учебного лагеря (но без перелёта). Путевки будут предложены топ-3 участникам, кто заполнил форму и соответствует условиям.
Условия:
- Участие не менее чем в 10 рейтинговых раундах на Codeforces.
- Максимальный рейтинг меньше 1900.
- Еще имеете право принимать участие в ICPC и/или IOI.
Таким образом, некоторые неофициальные участники раунда тоже участвуют в розыгрыше этого приза (если удовлетворяют ограничениям).
Всем удачи!
UPD: Хочу поблагодарить Артема Rox Плоткина и Дмитрия _overrated_ Умнова за неоценимую помощь в подготовке этого раунда!
UPD2: Разбор опубликован!
First comment!!
First dislike!![](/predownloaded/15/95/1595e083fd79e6c54251ac2473b222123c80dba2.png)
Actually, you are not right. The first comment was 10 years ago when codeforces was just opened. The comment was created by VitalyPavlenko![](/predownloaded/f2/48/f248475c4b6840c5f527ead668dd1c2f22a6b685.png)
who got First WA on test Case 5?
As far as I can tell, it was user Haleh with this submission 213![](/predownloaded/9a/34/9a342166c9bcdfb373b5cf0ac411c56212dd68ba.png)
Could you also find out who got first WA on test case 100?
**hope i will be cyan after contest **
Not bad!!
thanks bro --oldaccount--
Queueeeeeeeeeeeee.
I can relate.
indeed
codeforces: Div.3 contest
me: Let's get a speed performance check.
Why is vovuh always in the makers of div3 rounds(This does not happen in div 2 rounds).
No complains, just curiosity.
I think that is so because vovuh started Div. 3 competitions. Not sure though....
Why someone sumbit a wrong solution on purpose then hack his solution ?
Maybe they wanted to be at the top of the hackers during the hacking phase.
if so, what they will gain ?
What will they lose either? (Don't say rating as its probably their fake ID)
Again into the ashes
I think smarter requirements are needed for prizes in order to get rid of smurfing.
15000 participants but 100 upvotes?
Hope to become cyan. Hey rising_from_the_ashes! I felt in love with your handle!
Thank you
I hope to become blue idk how the scoring works
hey, you can install its browser extension so that u will get an estimate that ur rating is going to change by how much
I think I will just wait to see what happens. Though the site is very unstable currently (last round only took 2 hours for ratings to change)
The site's not unstable, this round has a hacking phase that goes on for 12 hours after the contest. As successful hacks can change the results, standings are subject to change during the phase, and thus rating is not updated because rankings can change. Rating will update (relatively) shortly after the phase ends.
Want to become cyan after this round.
Guys! please answer me. How to tag someone by its handle in codeforces?
Thanks! But I'm not a noob, I swear!
Why i can't register now?
Why i can't register now?
there is many a times constraint in CF contest that you have to register atleast 5 min before the contest start
Long Queue!
3 minute of queueueueue
I was stuck for around 12-15 minutes.
Please do something about the long queue time. Thank you!
Queueforces!!!
I got 9 penalty.
{Deleted}
There is no reason to kill yourself right now because of some computer not working properly, you will die somewhen anyway
anybody know how to solve E ?
solve each column seperately. calculate how many steps of move 1 if you do k steps of move 2
But is That solution O(N^2*M) ?
Solve for each column independently. For each shift $$$0 \le s \lt n$$$, count how many numbers will match their intended positions after shifting (let it be $$$f_i$$$ for a shift by $$$i$$$).
You can efficiently count that by iterating over every number in the column and determining, which shift will put it in the intended position, if it exists at all (some easy math here).
Then, for a fixed column, the answer is the minimum over all $$$n - f_i + i$$$, and the total answer is the sum of those.
How to solve C ?
Get all prime divisors of the given number. To calculate first number Fix the first number as the very first prime number.
To calculate second number: Start multiplying from next prime number onwards until the product becomes greater than first number.
To calculate third number: Product of all the remaining prime numbers.
Find all divisors of n.
Than brute over all pairs of divisors and let that number be a, b.
Than c = n/(a*b); if c is not divisible by that multiplication than don't select this pair. else you have found your answer.
My Submission
How your brute force pass?
what is the maximum number of divisors a number has?
I think it will be sqrt(n). Then how your solution pass.?
no, it is cube_sqrt(n)
see this: https://mirror.codeforces.com/blog/entry/651
Any number less than $$$10^9$$$ has not more than $$$1344$$$ divisors, with $$$735134400$$$ having exactly that many. Actually, it is reasonable to estimate the number of divisors as $$$\sqrt[3]n$$$ for small numbers (even though it asymptotically grows slower than any polynomial).
Simple and clear solution in 3 steps :
1. find all divisors of n greater than or equal to 2.
2. brute force the divisors using 3 loops and check whether you can get those 3 numbers say a,b,c such that a*b*c ==n and a!=b && b!=c && a!=c .If you got these 3 numbers then flag = true and break from all three loops.
3.If flag is true then print yes and a,b,c else print no . for further reference see my code by clicking on C.cpp : C.cpp
Yeah!
Greedy approach; let sq = sqrt(n) iterate i from 2 to sq, if n is divisible by i, store i in vector then divide n by i. Outside loop,if the vector size is 2 while looping, instantly break. if vector size < 2, print false. Else check if n(after loop) is not equal to numbers we push to vector and not equal to 1. If false then no, or else the answer is 2 numbers in vector and n that we get after looped.69322228
How do you lock your submission? I could not see the lock icon anywhere on the dashboard for the problems I solved.
Submissions ran on system tests directly, so there are not pretests and options related to, like hacks and locking problem
So for this contest there was no hacking phase? Sorry to ask stupid questions but I am new to this.
Just like me boy!
Why does it say "and after the round it will be a 12-hour phase of open hacks" in the blog?
how many number of divisors number has in problem c. In worst case.
Try number 734033887
It works for 30. which has 3 distint divisors 2,3,5
You have missed the case where there are only two primes and both of their power is 2. For example : 36. Your code returns NO. But there is an answer : 2, 3, 6
Haven't completely checked your code but you over-complicated the problem while the constraints aren't that big.
Try 1 36
Answer exists 2, 3 and 6
А кому в голову пришла замечательная идея запихнуть воостановление ответа в последнюю задачу?)
My approach for E: Process each column separately .For every column calculate cost for every possible rotation. For calculating the cost of every rotation loop through every value and find out for which rotation this element is at its correct position,and decrement the required no. of operation for that particular rotation by 1 .Choose rotation which require minimum operations .
Thanks for the contest!
Many people failed on test 25 because of it
Can someone help me understand where I went wrong in Problem C. My Solution Thanks in advance
Your code is too long,I think you should learn to write concise code
How to solve D?
I use std::set to matain the answer, and the code is pretty short and clear, here's my submission:69350130.
even shorter code by maintaining the count of remainders
I have absolutely the same code, and, this solution looks amazing...
cheers mate
Isn't this TLE?
it's O(qlogx).
Maintain array $$$B$$$, indexed from $$$[0, x)$$$. Initially, $$$B[i] = i$$$.
For each query, do $$$B[y_j \text{ mod } x] \text{ += } x$$$. The answer after each query is the minimum value of $$$B$$$; however finding the minimum naively would be too slow ($$$O(qx)$$$ over all queries). We could use a segment tree, or even just an ordered set (for each query, remove $$$B[i]$$$ from the set, update $$$B[i]$$$, then add it back to the set. $$$B$$$'s values would always be distinct), to reduce it to $$$O((x + q) \log x)$$$, which should pass. Do be careful about overflow; either use 64-bit integers or stop updating an index if it exceeds a threshold $$$> q$$$.
This works because it is always optimal to change each $$$y_j$$$ to the minimum possible non-negative value not already in $$$A$$$ (the array in the problem description), and $$$B[i]$$$ represents the minimum non-negative value $$$b$$$ where $$$b \text{ mod } x = i$$$ and $$$b \notin A$$$.
How to solve D?
The question becomes easy when you observe that a number when added to x or subtracted to x, it's modulo w.r.t 'x' remains the same.
Now, you just need to maintain precomputed of first % 'x' numbers, i.e from 0 to x — 1.Let's say this array as 'a'. Now, whenever a number comes. Find its modulo w.r.t 'x', and maintain a map or set, to check whether that number has come before.
if you use this number, let's say y. then increase that number in your precomputed array i.e a[y] += x.
Why? Because whenever a number will come, it will be holding place for next place of that modulo multiplicity.
I tried my best to explain to you. Take a look at my submission, you will get more idea.
My Submission
How to try on the hack? Its showing Illegal contest ID on clicking on 'Hack it!'
I think there's no hacking phase. 'cause the solutions ran on system tests directly, and not pretests
On div3 there is always a 12-hour hacking phase
Oh, so you do not need to LOCK your solution in Div3.
Locks are available in div1/div2 contests, not in div3 contests. You can read the rules of div3 to get more information
to hack in div 3 open the solution of whom you want to hack and on the top right by clicking on "hack it" you will be directed to test case window where you can put the hack test case.
when will editorial come
Presumably sometime after the 12 hour hacking phase ends
Who can explain to me why in my solution to Problem D I have to use long long.
the code:https://mirror.codeforces.com/contest/1294/submission/69352519
Where it is mentioned in problem D that we can increase or decrease one element in an operation more than once?? I mean a[i]-m*x or a[i]+m*x is possible for m>1 also in one single operation????
In the notes describing the example
You mean in the explanation??
They didn't say you have to do only one operation. You can do operation as many times as you want.
Very similar to Problem F ?
Yes and the author is my teammate sonu628. Unfortunately I couldn't solve it. ;_;
Never mind, I could not solve it either, even after solving it in the contest. I assumed the diameter of a linear tree = n (thus WA 39) :(
Didn't expect someone will remember :)
P.S:- feeling happy ;)
In problem F, what is wrong with this approach?. First, I find a diameter and take a and b as the ends of that diameter. Then I ban every edge that appears between a and b creating a new graph, and then I run DFS from every vertex between a and b. Finally I take c as the one whose depth is higher (depth 0 is also considered, in that case c is between a and b). This was my submission.
Hacks for C?
In problem F, what is wrong with this approach? First, I find a diameter and choose a and b as the ends of that diameter. Then, I banned every edge between a and b and create the new graph. After that, I run DFS from every vertex between a and b. Finally, I choose c as the vertex whose depth is higher (depth 0 is also considered, in that case c is between a and b). This was my submission.
I didnt read your code but your approach is O(n^2) you can simply do a multisource bfs.
Once I have erased the edges between the nodes in the diameter, I have a forest in which I have a tree rooted on each node and running DFS from them is O(V + E)
Can you please explain your Multi-Source BFS Approach ?
Its also basically the bfs, but initially in queue you have to put all the nodes whose distance is initially 0, also make their distance 0 initially. Now in the while loop instead of queue having a single node it will have many nodes with distances 0. The time complexity is same since it traverses whole graph, maintaining correct distances i.e O(V+E) .
Now in this particular question after finding the diameter ends,for all the nodes in their path make their distance 0, and run multi-sources bfs to get the third node which is farthest from the path.
TRY this case:
12 11
1 2
2 3
3 4
1 5
5 6
6 7
1 8
8 9
9 10
8 11
8 12
I think the answer is 9 but your approach will give 10.
please ignore. my bad. your approach will also give 9
Don't worry, thanks. I got AC. The approach was right, I had a bug of using the name of the variable temp instead of diameter in my loop.
69357392 I know my code is not that clean, but please check it for my bug on B!
anyone!? ;_;
BanazadehAria please help your compatriot!!!
sorry I didn't read the B, btw what is compatriot?
In problem D, what does "in one move" mean? It means increase or decrease any element of the array only one time or any? I asked my friend after contest, he said any. Did i forgot something?
One move means increase/decrease one element once, but since they give you unlimited moves, you in effect can do unlimited increases/decreases.
I mean why unlimitedly moving not declared in detail?
Approach for D?
simplest way I can think to explain D
Exactly same as mine :)
I really liked this Div 3 round. Especially how Mathematical C and D were. And that there were only 6 distinct problems.
Agreed, I come from Project Euler background so it is familiar
Great. How many problems did you solve on Project Euler ?
Is there anyone else with E failing on Test 8 ?
how to solve E? I heard that it is greedy, but i can't understand. Why greedy works? :(
while traversing in each column(say j), if any element(x) is found which belong to column j in the final matrix. Then find no of moves required in the cyclic shift of this column so that x reaches to its correct position.
Maintain a map[mv,fre]
mv: no of moves required so that x reaches to its correct position in the cyclic shift.
fre: frequency of such elements which reaches to its correct position after mv moves in the cyclic shift.
Now, for each column min no of moves required(say min_col) is the n-max(difference between freq and mv). So the ans is sum of all min_col
For better understanding have a look
can somebody help me with the testcase on which my soln is failing
hello all. My code for problem C gives the wrong answer on test case #2. Here is what I am doing: a) Find the "first" divisor of n greater than equal to 2. b) Find the "second" divisor which is not equal to the first divisor if possible. c) If possible then check if n/(first*second) is >= 2. d) If not possible then there is only one divisor >= 2 of n except itself. Then choose "second" = (first*first) and check if triplet is possible.
Please Help!![submission:69361400]
Sure, try $$$100$$$ as test case. According to your code, your first divisor is $$$2$$$ and the second one is $$$4$$$, so you check if $$$4$$$ divides $$$50$$$ and that gives you NO, you should choose a divisor after extracting the previous one. Also, your code is $$$O(t*n)$$$ and $$$n \leq 10^9$$$ and $$$t \leq 100$$$, so it will give you TLE.
what is the hack for C ?
Idk, but maybe it's due to the timeout since most of the hacked code got over 1900ms...
How to solve F with dp?
Let $$$dp(v, i)$$$ be the maximum number of edges between chosen vertexes in the subtree of vertex $$$v$$$ if we took $$$i$$$ vertexes in this subtree($$$0 \le i \le 3$$$). To calculate it use another dp — $$$f(i, j)$$$ means we are currently on the $$$i$$$-th child of current vertex and took $$$j$$$ vertexes. Then iterate over childs of current vertex $$$v$$$, suppose we are on $$$i$$$-th child, iterate on how many vertexes we took from the previous childs, let it be $$$prev$$$, iterate on how many vertexes we take from the current child $$$u$$$, let it be $$$cur$$$, and let $$$cost$$$ be $$$1$$$ if $$$cur = 1$$$ or $$$cur = 2$$$ (in this case we will count edge from $$$v$$$ to $$$u$$$) otherwise $$$0$$$. Then update $$$f(i, prev + cur)$$$ with $$$f(i - 1, prev) + dp(u, cur) + cost$$$. In the end update $$$dp(v)$$$ with the help of $$$f$$$ and don't forget the possibilty to take vertex $$$v$$$.
I think there is something wrong with calculating cost because why should we always pick vertex v? Our dp state was that the maximum number of edges if we pick j vertex from the vertex I subtree(not necessarily including i) what I am missing?
We shouldn't always pick vertex v. But in any case if we took one or two vertexes in subtree of u we will count edge from v to u because it will lie on the path from some pair of chosen vertexes(because we will take at least one vertex out of subtree of u).
What is test case 8 in E??
hi guys can anyone tall me how to solve C? I don't understand why it always is optimal to try first divisor of n
find all prime factors with their respective powers in sqrt(n) time then check three cases case 1. no. of prime factors are more than3 answer always exist and it is any combination you can pick up then
case 2 only 2 prime factors but their total power is greater than or equal to 4 then answer exist else no. (a,b,a^x*b^y)
case 3 only 1 prime factor available then check if its power>=6 (a,a^2 a^3) then answer always exist else no.
I also wrote my solution based on same logic, except that I was considering for case 2 that the sum of powers should be greater than equal to 3
We just need to find 2 different divisors such that one of them is a composite one with again 2 different divisors and also you need to check that they are greater 1.
hmmmm you can list all of divisors of N, the max numbers of divisor of N is 100 (if N == 1e9) so you can use O(N^3), right? Use 3 loops and check every divisor by conditions of problem
Not exactly n³ because no. Of divisors are way to less for numbers <= 1e9.Its not 100 but around 1700-1900 i guess
you can check it! numbers of divisors of 1e9 is 100, I tried it before I wrote my solution
Any number less than 1e9 has not more than 1344 divisors, with 735134400 having exactly that many. Actually, it is reasonable to estimate the number of divisors as cbroot n for small numbers (even though it asymptotically grows slower than any polynomial).
Maybe you don't understand what I say :(
Maybe that's the reason but this logic works right XD
Guys, I am confused about the Problem D. In the example it states that: "After the fourth query, the array is a=[0,1,2,2]: you don't need to perform any operations, maximum possible MEX is 3 (you can't make it greater with operations)." __ However, if we add one to the last element will get a=[0,1,2,3] which I think has a MEX of 4. Can someone explain me why adding one to the last element does not improve the MEX?
You can add only number x. In this testcase x equals to 3, so u cant add 1, u can add only 3 as many times as you want
Whats testcase 3 of problem F?
This testcase worked for me:
No hacking in this Round? I am getting Illegal contest ID.
any idea to solve problm D please ?
When the ratings will be updated?-
Whoops, looks like I submitted a solution for 1294E - Obtain a Permutation that has an error in it not covered by the testing suite, but it's too late to hack it: 69397747
a <= n * m
should bea < n * m
. It breaks on the following test case:I have hacked it now with the sample you provided
I think I am the only one who solved C via Miller-Rabin.
It proves that it is no use to think the problems as too difficulty in div3 rounds
I have created the video solution for the first four problems, explaining my understanding and approach for the same. Codeforces 615 DIv3 Video editorials
Do like comment, share, subscribe if you like the video. Do subscribe for more such content
Happy Coding
I think your test cases for 1294E - Obtain a Permutation is too weak. 69353056 Shows: Output: 0 For Input: 4 4 5 2 3 4 Where the actual result is: 1
Huge gap between next contest....... Please decrease the gap
For problem E, I misread that each element of given matrix was an integer between 1 and "n * m". Today, I figured out that "n * m" transforms into some digits numbers. TT
Hi dear,
I participated in Codeforces Round #615 (Div. 3) with my 2 personal handle (7ouda,7ooda) and submitted same solutions so my submissions was skipped, and I didn't know that it's a rules violation, so please can you help me.
Thanks, Mahmoud.
Write it here.