Hello everyone!
I would like to invite you to participate in Codeforces Round 480 (Div. 2), it will take place tomorrow, May/08/2018 18:05 (Moscow time).
The round consists of 6 problems and you will have two hours to solve them.
The problems were prepared by me with great help from linkinu and Reem. I would like to thank KAN for his great efforts in reviewing the problems and for his suggestions, it is really amazing to see the work done behind every round. Also thanks to Tommyr7, Livace and mike_live for testing the problems, and to arsor for translating the statements into Russian.
This is my first round on Codeforces, I hope that you will find some interesting problems for you.
Note that the round is rated for everyone with rating below 2100.
Good luck and have fun!
UPD: Congratulations to the winners:
Div. 2:
Div. 1+2:
UPD1: Editorial
rated for div.3 too?
Yes
I think it's rated for all those with rating <2100 (Namely, candidate masters and lower)
Yes read more in this blog http://mirror.codeforces.com/blog/entry/59228
thank you. I didn't read this blog carefully.
...
I hope to cross 1700
I am expecting some really interesting round, Hasan0540 is one of the best problem setters from the Arab region, I always enjoyed your problems in ACM contests :D
I agree with you ^.^
I hope to see a realy nice contest from our Jordanian programmer Hasan0540. ❤
We've implemented a special tag [contest_time:contestId]. It shows a contest start time in a correct timezone (as a link to timeanddate.com). Please, use it in announcements as Hasan0540 did.
great!
could you plz make it open in a new tap when i press on it
Am I only noticed that in the russian description only thing in russian is the date :)
Are these problems in English or Russian?
Both
любил конкурс много
Hope will be Short Statements
I have final exam too :'(
One Can join the course in the summer course and get grades, But can't join the contest in the virtual participation and get rate .... sorry final :D
WOW!! Three Arab rounds in one month
Codeforces Round 473 (Div. 2)--Codeforces Round 478 (Div. 2) -- Codeforces Round 480 (Div. 2)
We are invading CF :D
if u guys invade codeforces then americans (led by George Bush) will come to cf and look for oil. watch out my dood
Iraq 2003 _ Codeforces 2018
R.I.P Codeforces
Для третьего дивизиона раунд будет рейтинговым?
Да
I have a question: when we'll have a div1 and a div2 contest in the same time, those under 2100 can participate in both rounds or is forbidden for them to join div2?
They can't join div2
Шесть задач, я думаю сегодня будут более интересное соревнование. :-)
you forgot to say thanks for MikeMirzayanov for the great Codeforces and Polygon platforms.
I hope this contest will make me green once again
Good Luck u can do it
Time to use my alt account!
Будет ли теперь всегда div2 рейтинговым для людей с рейтингом, меньшим 2100?
For now yes!
I understood that this round would be rated for people with rating belong 2100, I asked if future contests will have the same rules
All the best Hasan0540 for your first round! May it be interesting and great for everyone! cheers!
It's time to decrease my rating again....
Why B has no spj?
What's spj ? I have seen people mentioning spj before too.
Special Judge.
Can you please elaborate on it. Thanks.
Such as the test case in problem B, if this problem is SPJ(actually it's not):
Your output can be anyone of the above, and the verdict result always is Accepted, instead of Wrong Answer.
Generally, if the problem is SPJ, the writer will explain it.
I think so. Such test case is WA.
I positively registered for this contest but now when I am trying to submit the solution, it says I can't do it because I am not registered. Anyone has any ideas who should I contact?
Check if you weren't logged out.
Stupid problem selection.This problem set should be for DIV1.Not for typical div2 and div3 people.
1) If these problems were chosen for Div.1 it will be so easy for them.
2) Hard problems are the best way to practice.
3) If you were effected by the problems, it is not the end of the world.
Can anyone translate problem D? I really try understand... but fail.
I still cant understand how the sample test work...
Oh my rating!!! They will be in a lot of trouble after this round. A really bad contest for me.
so difficult to understand problem statements...
Really? It seems to me that C easier than B
I can't understand the problem statement properly for problem B and problem C. Either my English skill is not good or the problem statements was poor.
I guess problem statements were alright. Yeah for C i would say maximum part was unnecessary but you could easily decipher it seeing sample cases.
How to solve D?
The real question is: How to read problem D?
Let b[i] be the product of primes with odd exponent in a[i]. Then the minimum number of groups is the number of distinct elements in b
Given a subarray:
1- Every pair of integers that are not 0 will be part of the same group if and only if the set of primes with odd exponent is the same for both numbers (when you write numbers as a product of prime numbers)
2- Every 0 can be part of any group.
Then you can pre-group the numbers and after that you just calculate the answer for every subarray.
My submission
Hasan0540 Next time please make statements easy to understand.
Any idea of test 7 of E?
I forgot to update height values for sons of ancestors.
Something like: 10 5 9 6 8 4 3 4 10 9 4 5 4 10 3 2 1 5 5 7
(sorry for the big test, I was stresstesting). The answer is 1 2 3 5 7, my code(WA7) prints 1 2 3 6 7
Maybe that's your case
yup 12367 it prints for me too.. Ok why would it print 5. 5 is connected to 7 also even after deletion of 1 and 2?
Well, considering you are already aware that you have to remove 7, you can remove 5 instead of 6, because after 7 and 1 removal, 5 is free to go.
Nice problems(though harder version of D was on some round before).
895C - Square Subsets Do you mean this one? I don't think they're similar.
No this one. Just use subidea from the editorial(assigning group values).
You're right, they're similar. I used randomization instead of that though.
I don't understand problem C: 5 2 0 2 1 255 254 For this test case in problem C, wouldn't lexicographically smallest array be 0 1 0 254 254 (0 and 1 are grouped for key 0) instead of what is shown as the test case 0 1 1 254 254?
Thanks for any help
If you group 0 and 1, 2 will belong to other group and say key will be 2 or more. Thus you will get 0 2 0 254 254 which is not desirable!
Oh okay, got it, I completely misunderstood the question. Thanks
No. Because you have assumed 2 drops down to 1. So [1,2] is the maximum set that can be paired to 1. You can't include 0 in it as k==2.
According to you, 0 and 1 are grouped for key 0. But then, 2 can be grouped only to itself, as the maximum size of any group is 2, so 2 cannot be grouped with the group [0, 1].
This will result in the array : 0 2 0 254 254.
Got it, thanks
OMG.
~~~~~
long long b = ...;
long long a = sqrt(b);
if (a * a == b)
{
//b if square
}
~~~~~
This works just fine on Codeforces but fails on my computer, so I failed my hack. Gosh. Now I know more about CF.
Почему В падает на 5 претесте?
По тому, что всегда есть способ разставить #.
На 7 3 какой ответ?
подсказка: симметрия
Точно! А я-то думал что с четным k всегда выйдет, а с нечетным не выйдет, а оказывается можно.
.......
.#...#.
...#...
.......
Такой, например:
YES
.......
..#.#..
...#...
.......
Если лосось ходила бы за жителями 2-ой деревни, тогда легче в голову пришло бы решение.
Скорее всего это связанно с неправильностью твоего алгоритма. Я сам столкнулся с этой проблемой, после корректировки алгоритма всё таки прошёл 5 тест, но пролетел с 8 Проверь этот тест: 7 3 Правильный ответ: YES
.......
..###..
.......
.......
How to solve E?
Am i correct that this is greedy? First we take vertex n, than try to take n — 1. If we can take number of vertex between n and n — 1 we take it else try to take n — 2 and same algorithm next.
Yes, because 2^x=2^(x-1)+2^(x-2)+...+2^0 + 1.
Fine, how to make fast realization?
I solved it like that. I had to optimize lca to O(1) to prevent tle ...
Can you tell me your solution?
You can think of it as "keeping" vertices. So first you keep vertex n, then you try to keep vertex n-1, then n-2 etc. (To keep a vertex i, you need to keep every vertex on the path from n to i)
We realize that we keep at most n vertices. Thus, every time we keep a vertex, we can mark it as kept. Now we want to know the first ancestor of vertex i that is already kept (this tells us how many more vertices we need to keep along the way in order to keep vertex i).
We can use parent doubling to check this in O(lg N), so I don't see why we need O(1) LCA here.
I solved it as follows: given a tree T and a vertex u, we have to find the vertex v in T that maximizes the depth of lca(u,v). Note that a solution for v is one of the leafs that is next to u (left or right) in dfs-order. Mine is also Nlog(N), so I was surprised when I got TLE
meeeep Can u give any link to learn about the "parent doubling" that u used? One more thing why cant we proceed in this way:- remove the smallest weight leaf from the tree and repeat the same on the new tree until we remove k nodes which could be seen as minimizing the number of fans that we lose by removing a node?
Consider this tree:
3 — 1 — 4 — 2
where k = 2. If we do it your way, we'll remove 2 (our leaves are 2 and 3) and then 3 (leaves are 3 and 4). But the correct answer should be removing 3 and 1
fikr Thanks for test case.... I didn't think of that
I don't know a link, but it should be pretty simple to explain (hopefully).
For each node, you store your 2^i-th parent for each integer i. (A convenient initialization for this question is that the parent of the root is itself).
We initialize the 2^0-th (i.e. direct parent) manually. For each i>1, we notice that the 2^i-th parent is just the 2^(i-1)-th parent of the 2^(i-1)-th parent, so we may find this is constant time... assuming we have already computed the parents of its 2^(i-1)-th parent. This means that we want to compute parents in some kind of pre-order DFS, which can be written together with the DFS that roots the tree.
I think that is termed as "finding LCA using sparse table". OK thanks I'll look into that and learn it.
meeeep U used that parent doubling to find the lowest ancestor who has been marked as "kept" right ?
Because
, process the cities from greatest to least and greedily take them. First, root the tree at the largest value (you always take it). Then to see if you can take city $x$, see how many cities you haven't taken that are on the path from x to the root. If you can take all of them, do so, otherwise ignore this city.
hacks for D?
I can only guess that some people (like stupid me) used if instead of while when eliminating square divisors.
Omg that's exactly what I did
We're not alone XD
I lost a time because in problem E k supposed to be less than n. When I added if n == k print(all) it passed.
I'm not sure that's it — my code should definitely fail that case, but I passed pretests
http://mirror.codeforces.com/contest/980/submission/38038173 MEM http://mirror.codeforces.com/contest/980/submission/38035881 WA
You also added line
if(k == 0) break;, which is quite important!I had this line. I removed it. Why it's so important?
Trying to do the C problem...
Please guarantee there are at least one perl on A...
I heard the announce after my first submit, so I lost 50pts...
They shouldn't need to guarantee extra things just because you missed an edge case :/
Do you think the necklace that has no perls is really necklace? And when I noticed the edge, I didn't know the answer for ---- is YES or NO.
To keep up the pettiness, according to Oxford dictionary, the definition of a necklace is "an ornamental chain or string of beads, jewels, or links worn round the neck."
So yes.
Actually, I think it's bad to not write constraints. In our time good manners for problemsetting is one simple rule: if a lot of contestant can misunderstood the statement, it's a bad statement.
A lot of contestants can misunderstand the statement and a lot of contestants can easily overlook an edge case are different things.
Actually the same, when you didn't specify what is the edge case. A lot of people thought it's guaranteed there are at least one perl.
There is a sample case with no links so why would it need to have at least one pearl? I would be much more worried about my necklace having no links to hold it together, rather than no pearls.
You see: it's not about how YOU see the problem. It's about how does others see it. For you it may be obvious that it can be zero pearls. For me too. But it can be not obvious for others, and that's ok, all people are different and have different points of view. What's why you need to specify such things as constraints, so it will be obvious for anyone.
Statement for C is hard to understand, and B is a bit hard for a Div2-B. But overall, today's problemset is nice (especially E).
Problem A pretest is wayyyyy to soft
I realized that in the D is necessary to consider the cases where there is a 0 in the range, but didn't corrected my code correctly, wasted a big chance :(
When you realized you forget to handle 0
Seemed like Problem D's time limit a little bit too strict?
I had that problem too, is the intended time complexity less than Θ(n^2+n*sqrt(10^8))?
Not really sure. My solution has the time complexity you mentioned.
I was trying to reduce the constant factor that might cause the TLE, but guess I didn't have enough time to come up with an elegant one.
I don't really sure, but, I think, any complicate data structure (set, hashset/unordered_set) will get TL and we need to use bool array instead of them (after renumber of all numbers in handled massive, like [16127, 1046527, 16769023, 1046527, 1046527, 16127] -> [1, 2, 3, 2, 2, 1]).
This is exactly what I was thinking. I was trying to implement such, but since I thought about that too late, I couldn't submit my solution.
I didn't lock my solution and I got hacked HOW!!!!! here
Locking grants you the rights to hack others, not protects you from being hacked.
You should be happy for being hacked since you got a second chance. Otherwise you would've just gotten "Wrong answer on test xx" without even knowing that your solution was wrong.
Can you make the number of links between every two adjacent pearls equal? And there is some test for only 1 pearl and even "No" pearl ???
Hasan0540 why you are so strict at dataset for problem F!!!
May be because the intended solution was not a simple BFS?
I could not make out D. Can someone make me understand what the problem statement meant?
any on got WA test 5 in the problem B then got AC ?
any test case ?
5 1
Answer is yes
Do you know test 8. I'm stuck at that :(
rip my rate
oh wait it's already bad
it is rated or yes?)))
I hope it's UR or Semi-Rated,but Unfortunately, here is Codeforces so it's maybe Rated...
How to do B? I thought to create symmetric parts on the innner matrix. Any suggestion?
Yeah symmetric inner matrix.You have 3 cases to consider. Let me assume n=7.
if k is even say 4:
.......
.##....
.##....
.......
if k is odd and <=(n-2) say 3:
.......
..###..
.......
.......
if k is odd and >=(n-2) say 7:
.......
.#####.
.#...#.
.......
How did i come up with this? Well i had made a checker that gives no of ways to reach in shortest path from 1,1 and 4,1 for a given grid and used a bit of symmetry and observations to conclude this.
2nd and 3rd cases can be understood as inversions of each other. Look at antipr000's examples: inner matrix of 2nd case is inverse of inner matrix of the 3rd case. So if we have k ≥ n - 2, then we can assign k to (n - 2) * 2 - k and make inversion after (perl code — 38050716).
My first hack on problem A (38026095)
Seriously I don't know how that passed the pretests...
I think the problems are really nice.But I spent some time hacking ,and have no time to write out problem E.So sad.
can you share idea for E, this is my WA on test 8 solution, http://mirror.codeforces.com/contest/980/submission/38049503
I haven't got aceepted now,sorry.But my idea is almost the same as yours.Add the points from n to 1.
Well,maybe you forget one function you wrote yourself.clca().What a pity!
oh no, i need some rest
I could not make out D. Can someone make me understand what the problem statement meant?
Same question. why is the answer to array [5] is 1???
You separate [5] into the set(5). Now since there are no pairs of numbers in this group, the product of any pair is a perfect square (vacuously true). there is only 1 set, so the ans is 1
Consider the test case [5 2 8]. There are 6 sub arrays. For each, we want to separate it into as few groups such that product any pair of elements in any group is a perfect square. For this example, the groups are
[5 2 8] -> (5) (2 8)
[5 2] -> (5) (2)
[2 8] -> (2 8)
[5] -> (5)
[2] -> (2)
[8] -> (8)
Now, since 4 of them sep into 1 group, and 2 sep into 2 groups, the ans is
4 2 0
thx
How to solve problem C?
I still couldn't understand C. I think I need to improve my English skills first :(
Stupid cases of 0's in D. These puzzling cases aren't fair :/
За 90 секунд я успел:
Думаю codeforces работает достаточно стабильно и быстро (по крайней мере под конец раунда).
Is it just Me who think that problem B became harder than C just because of the statement? XD just want to know everyone's views!
Yes C was ofcourse easy. B was harder than C because there were 3 independent cases to tackle and needed good observation or otherwise tricks like generating no of paths for smaller datasets and observing patterns
I disagree. My thought process was just "you can reverse the ending/start so it's just number of paths between the diagonals. If the grid is symmetric then the answer is the same". For problem C I struggled to understand what it asked until looking at the samples.
3 independent cases? I handled only 2 independent cases
In my approach i had to handle cases of: k=even, k=odd and <=(n-2) and k=odd and >(n-2)
I handled: k = 2 * (n - 2) and k < 2 * (n - 2)
But know i even now how to handle even one case
Can you explain your approach a bit?
If k = 2 * (n - 2) then it is obvious.
Else just put hotels in pairs symmetriсally the middle vertical, and if k is odd, just put the last hotel on it.
Clarification on A was so unfair, for people, who already failed on this case, and got minus points
i also deal with this and the jury said "It is clear from the statements." , i hope it's unrated. this contest is worst
But it was clear from the statements...
D in a nutshell.
tfw when you forgot to handle negative numbers in d.
More people fail because of zero than negative numbers in D.
I think, 2 hours are too few for this contest (a lot of cases, a lot of thinking, a lot of text understanding). It would be better to have 2.5 or 3 hours of solving time.
I agree. I think some participants could solve F if they had another one hour.
I didn't really like this contest
D is really hell. I've spent a lot of time to read and understand it. There is no any example explanation like in other problems.
Can someone translate problem D
A could really use some constraints on perl/links numbers and D's statement was so bad.
Whats test 20 in D?
When writing code for problem A, I know that I have to wait for the statement update to handle the case of 0 pearls. I took me few more minutes. I don't know how 1500 solvers before me manage this case.
Can anyone please give me the proof for problem B's solution?
Observe symmetry. Let me explain in cases:
if k is even:
We put 2 #'s in grid[1] and grid[2] as long as needed. Why this works?
Well see symmetry with respect to (1,1) and (4,1) one can easily tell that no of paths will be same.
.....
.#...
.#...
.....
Now for k odd and <=(n-2):
Here observe symmetry of (1,1) and (1,n-1) ; (4,1) and (4,n-1).
.....
..#..
.....
.....
And for k odd and >(n-2) number of paths is always 2.
So for the last case — odd k and k>(n-2), I can place the hotels anywhere?
No. Place them like this
.......
.#####.
.#...#.
.......
see you blocked all ways and only 2 left.
Yeah, thats what I did but since you said that it would always be 2, I got confused :p
Thanks for the help :)
oh sorry my bad. yeah you have to block such that its 2. xD
Write winners, write winners, I want to see my name :D
For me contest was really nice with cool tasks :) I thought that I will never say this sentence, but maybe texts could be a little longer.
Congrats!
Thank you, we are both now masters :)
Can someone explain the problem statement for D ?
PROBLEM B: for input 9 5 why YES
.........
.##.#....
..#.#....
.........
isn't an answer?
You can understand why it is not correct answer by thinking on simplified but similar case:
(question mark means doesn't matter)
(1,1) -> (4,9) 23patterns
(4,1) -> (1,9) 22patterns
YES ......... ..#####.. ......... ......... is one of the answer
While other paths are symmetric, there's one exception. For the one that starts from the upper side and first goes down,
and
are both possible, while for the opposite side, only
is possible.
edit: Thanks rsFalse!
Use
blockformatting it gives monospace font.Problem B
Based on intuition : easy
Based on Proof : hard
If the matrix is perfectly symmetric you don't need to count the number of paths to know they are they same number. They are literally the same paths, no need for more proof.
ways (1,1) -> (4,n) is equal to ways (4,n) -> (1,1)
If answer table is symmetry, number of ways from (4,n) -> (1,1) equals (4,1) -> (1,n) (because of symmetry)
(symmetry through (n+1)/2 like this
00000!00000
00#00#00#00
0#00#!#00#0
00000!00000 )
proof doesn't look hard
Wow, exactly 50 users became Master according to new rules!
Wow, I've become
so numborange, but now it is not so coolFor me it is cool , orange is orange :D
But someone should investigate is everything fine with rating, for me it looks jumps are a little bigger than expected.
while I had a very bad contest but the problems was so beautiful. thanks for that Hasan0540.
What is case 18 in problem D. I keep getting WA.
I also had WA 18 0 * (ANY NUMBER) = 0 — square also 0%(j*j)==0 (this should help)
Thanks!
It was unclear whether 0 is perfect square or not while I was competing!
Can anyone explain me problem C ? I read at least 10 times, still find hard to understand.
7 3
0.4.1.7.6.11.8 ______________________ 0.1 | 2.3.4 | 5.6.7 | 8 | 9.10.11 | 12.13 ....
^ The answer is: 0 2 0 5 5 9 8.
Thank you so much. Now it's clear :)
Could someone please explain the symmetric approach used to solve B? I can't understand how to think in the correct direction.
Please see my other reply above. The key, for me, was observing that many shortest paths cross in the middle of the grid, and must be symmetrical. For example
To keep or remove the same number of "diagonal" paths from both sources, you have to place hotels with horizontal symmetry, leaving a hole in the middle column if they are even, or putting one in the middle column too, if they are odd.
Hope this makes sense!
(edit: fixed drawing of "diagonal" paths)
It is easier to place hotels with vertical symmetry
Could you please elaborate why?
Because you don't need to handle many cases. Solution with only one 'if': 38060661
We probably mean the same thing! By horizontal symmetry I mean over a vertical axis.
Oh, my bad
Not at all, I should have been clearer!
For those who are curious how the color distributions are changed due to the update of upper bound of the rating on "Div.2 Only" rounds. Please be informed that this describes top 2000 contestants for each round:
Hey good job. Can you brief in 1-2 lines rhat what can we conclude from.this data? Seems to me like it says more about the level of the specific rounds rather than the updated rating system. Please enlighten me :)
If I understand your question, I believe Codeforces #480 was the first "Div. 2 Only Round" that contestants in purple participated. In other words, purple lines described here hadn't appeared in any previous rounds! :)
For your reference, here's 6 rounds version of it :)
Thanks for these pictures.
I came up with a solution for D that is something like this:
We add bidirectional edges between pair of nodes i to j if ai·aj is a perfect square. My first observation was, every connected component is a complete graph. Let, bi be the binary string consisting the parity of powers of primes of ai. Then if i and j are connected and j and k are connected, then i and k are also connected. Because, i and j connected means
— (1), again, j and k connected means 
— (2). Combining (1) and (2), we get 
, means i and k have an edge. This gives us enough material to prove that all connected components are complete graph.
Now, the problem reduces to finding the number of connected component of the sub-graph consisting only edges in a range, i.e. in [l;r] (1 ≤ l ≤ r ≤ n).
To do this, I implemented this using the following way:
We first select sub-array's starting point, let's say i(actually we also iterate this from left to right), then iterate on the ending point from left to right (denote it also with j). When extending one node to the right (means, we are going from j to j + 1) we need to only know if j + 1 connects to any of the node in range [i, j]. If it does, then number of connected component remains same, increases by 1 otherwise. As we don't care about the edges connecting with a node left to i, we may delete them on the go i.e. when we move the left end point one step right, i to i + 1, we delete all the edges that are connecting node i and another node with index greater than i. Another observation is that, when we are trying to find if the new node j + 1 can be connected with any component, we need not to check all the edges as all the edges lead to the same component. Instead of keeping all the edges we will keep the edge which connects j + 1 with the closest node left to j + 1. More formally-
For each i (1 ≤ i ≤ n),
maximum j < i such that there is an edge between i and j, if there is none then it's simply - 1. Again a set for each i, 
.
Now, the pseudo code seems something like this-
Where
is the answer array.
But I got Wrong Answer on test 18. Submission
Can anyone check and tell what's wrong here?
if i and j are connected and j and k are connected, then i and k are also connected.
This doesn't hold when a[j] is equal to 0, like in this case.
3 10 0 7
Thanks. Got AC.