### Hasan0540's blog

By Hasan0540, 3 years ago,

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

• +314

 » 3 years ago, # |   0 rated for div.3 too?
•  » » 3 years ago, # ^ |   0 Yes
•  » » 3 years ago, # ^ |   +4 I think it's rated for all those with rating <2100 (Namely, candidate masters and lower)
•  » » 3 years ago, # ^ |   0 Yes read more in this blog http://codeforces.com/blog/entry/59228
•  » » » 3 years ago, # ^ |   0 thank you. I didn't read this blog carefully.
 » 3 years ago, # | ← Rev. 2 →   -21 ...
•  » » 3 years ago, # ^ |   -11 I hope to cross 1700
 » 3 years ago, # |   +43 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
•  » » 3 years ago, # ^ |   +4 I agree with you ^.^
•  » » » 3 years ago, # ^ |   -14 who are you?
 » 3 years ago, # |   +26 I hope to see a realy nice contest from our Jordanian programmer Hasan0540. ❤
•  » » 3 years ago, # ^ |   -20 who is Hasan?
 » 3 years ago, # |   +130 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.
•  » » 3 years ago, # ^ |   +8 great!
•  » » 3 years ago, # ^ |   +6 could you plz make it open in a new tap when i press on it
 » 3 years ago, # |   +74
 » 3 years ago, # |   0 Am I only noticed that in the russian description only thing in russian is the date :)
 » 3 years ago, # | ← Rev. 2 →   +3 Are these problems in English or Russian?
•  » » 3 years ago, # ^ |   +7 Both
 » 3 years ago, # |   0 Hope will be Short Statements
 » 3 years ago, # |   +280
•  » » 3 years ago, # ^ |   +7 I have final exam too :'(
•  » » 3 years ago, # ^ |   +26 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
 » 3 years ago, # |   +21 WOW!! Three Arab rounds in one month We are invading CF :D
•  » » 3 years ago, # ^ |   +52 if u guys invade codeforces then americans (led by George Bush) will come to cf and look for oil. watch out my dood
•  » » » 3 years ago, # ^ |   -15 Iraq 2003 _ Codeforces 2018 R.I.P Codeforces
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   +13 They can't join div2
 » 3 years ago, # |   +32 you forgot to say thanks for MikeMirzayanov for the great Codeforces and Polygon platforms.
 » 3 years ago, # |   -9 I hope this contest will make me green once again
•  » » 3 years ago, # ^ |   +1 Good Luck u can do it
 » 3 years ago, # |   -46 Time to use my alt account!
 » 3 years ago, # |   +8 All the best Hasan0540 for your first round! May it be interesting and great for everyone! cheers!
 » 3 years ago, # |   +7 It's time to decrease my rating again....
 » 3 years ago, # |   +1 Why B has no spj?
•  » » 3 years ago, # ^ |   +1 What's spj ? I have seen people mentioning spj before too.
•  » » » 3 years ago, # ^ |   0 Special Judge.
•  » » » » 3 years ago, # ^ |   +1 Can you please elaborate on it. Thanks.
•  » » » » » 3 years ago, # ^ | ← Rev. 5 →   0 Such as the test case in problem B, if this problem is SPJ(actually it's not): The input is 7 7, so one of valid answers is: ....... .#####. .#...#. ....... the another one is: ....... .###... .###.#. ....... and the another one is: ....... .###.#. .###... ....... .etc. Your output can be anyone of the above, and the verdict result always is Accepted, instead of Wrong Answer.
•  » » » » » 3 years ago, # ^ |   0 Generally, if the problem is SPJ, the writer will explain it.
•  » » 3 years ago, # ^ | ← Rev. 5 →   0 I think so. Such test case is WA. 7 7 ....... .###... .###.#. ....... 
 » 3 years ago, # |   0 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?
•  » » 3 years ago, # ^ |   0 Check if you weren't logged out.
•  » » » 3 years ago, # ^ |   0 I am quite sure I wasn't. Anyways, bad luck for me. I'll try next time.
 » 3 years ago, # |   +17 Stupid problem selection.This problem set should be for DIV1.Not for typical div2 and div3 people.
•  » » 3 years ago, # ^ | ← Rev. 2 →   -21 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.
 » 3 years ago, # |   +19 Can anyone translate problem D? I really try understand... but fail.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +16 I still cant understand how the sample test work...
 » 3 years ago, # | ← Rev. 2 →   +7 Oh my rating!!! They will be in a lot of trouble after this round. A really bad contest for me.
 » 3 years ago, # |   +21 so difficult to understand problem statements...
 » 3 years ago, # |   +38 Really? It seems to me that C easier than B
 » 3 years ago, # | ← Rev. 5 →   +16 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.
•  » » 3 years ago, # ^ |   +7 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.
•  » » » 3 years ago, # ^ |   0 Ok i got the point.
 » 3 years ago, # |   0 How to solve D?
•  » » 3 years ago, # ^ |   +61 The real question is: How to read problem D?
•  » » 3 years ago, # ^ |   +7 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
•  » » 3 years ago, # ^ |   0 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
 » 3 years ago, # |   +66 Hasan0540 Next time please make statements easy to understand.
 » 3 years ago, # |   +10 Any idea of test 7 of E?
•  » » 3 years ago, # ^ |   0 I forgot to update height values for sons of ancestors.
•  » » 3 years ago, # ^ |   +11 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 7Maybe that's your case
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » 3 years ago, # ^ |   0 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.
•  » » » » » 3 years ago, # ^ |   0 Ok maybe that is why it was E :(
 » 3 years ago, # | ← Rev. 2 →   +22 Nice problems(though harder version of D was on some round before).
•  » » 3 years ago, # ^ |   0 895C - Square Subsets Do you mean this one? I don't think they're similar.
•  » » » 3 years ago, # ^ |   +10 No this one. Just use subidea from the editorial(assigning group values).
•  » » » » 3 years ago, # ^ |   +1 You're right, they're similar. I used randomization instead of that though.
 » 3 years ago, # |   +5 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
•  » » 3 years ago, # ^ |   0 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!
•  » » » 3 years ago, # ^ |   0 Oh okay, got it, I completely misunderstood the question. Thanks
•  » » 3 years ago, # ^ |   0 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.
•  » » 3 years ago, # ^ |   0 If 0 and 1 are assigned for group 0. Then it turns out that (2 and 3)_ can be assigned to one group with smallest unique key as 2.So according to this the o/p is ( 0 2 0 254 254) which is lexicographically greater than 0 1 1 254 254
•  » » 3 years ago, # ^ |   0 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.
•  » » » 3 years ago, # ^ |   0 Got it, thanks
 » 3 years ago, # | ← Rev. 3 →   0 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.
 » 3 years ago, # |   0 How to solve E?
•  » » 3 years ago, # ^ |   +5 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.
•  » » » 3 years ago, # ^ |   +5 Yes, because 2^x=2^(x-1)+2^(x-2)+...+2^0 + 1.
•  » » » » 3 years ago, # ^ |   0 Fine, how to make fast realization?
•  » » » 3 years ago, # ^ |   0 I solved it like that. I had to optimize lca to O(1) to prevent tle ...
•  » » » » 3 years ago, # ^ |   0 Can you tell me your solution?
•  » » » » 3 years ago, # ^ |   0 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.
•  » » » » » 3 years ago, # ^ |   0 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
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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?
•  » » » » » » 3 years ago, # ^ |   +3 why cant we proceed in this way Consider this tree:3 — 1 — 4 — 2where 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
•  » » » » » » » 3 years ago, # ^ |   0 fikr Thanks for test case.... I didn't think of that
•  » » » » » » 3 years ago, # ^ |   0 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.
•  » » » » » » » 3 years ago, # ^ |   0 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 ?
•  » » 3 years ago, # ^ |   0 Because 2i > (2(i - 1) + 2(i - 2) + ...), 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.
 » 3 years ago, # |   +5 hacks for D?
•  » » 3 years ago, # ^ |   +8 I can only guess that some people (like stupid me) used if instead of while when eliminating square divisors.
•  » » » 3 years ago, # ^ |   0 Omg that's exactly what I did We're not alone XD
 » 3 years ago, # |   0 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.
•  » » 3 years ago, # ^ |   0 I'm not sure that's it — my code should definitely fail that case, but I passed pretests
•  » » » 3 years ago, # ^ | ← Rev. 4 →   0
•  » » » » 3 years ago, # ^ |   +5 You also added line if(k == 0) break;, which is quite important!
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I had this line. I removed it. Why it's so important?
 » 3 years ago, # |   +8 Trying to do the C problem...
 » 3 years ago, # |   -14 Please guarantee there are at least one perl on A...I heard the announce after my first submit, so I lost 50pts...
•  » » 3 years ago, # ^ |   +18 They shouldn't need to guarantee extra things just because you missed an edge case :/
•  » » » 3 years ago, # ^ |   -10 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.
•  » » » » 3 years ago, # ^ |   +26 Do you think the necklace that has no perls is really necklace? 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.
•  » » » 3 years ago, # ^ |   0 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.
•  » » » » 3 years ago, # ^ |   +1 A lot of contestants can misunderstand the statement and a lot of contestants can easily overlook an edge case are different things.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » » » » 3 years ago, # ^ |   +6 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.
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   -15 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.
 » 3 years ago, # |   +8 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).
 » 3 years ago, # |   0 Problem A pretest is wayyyyy to soft
 » 3 years ago, # |   +8 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 :(
•  » » 3 years ago, # ^ |   +29
 » 3 years ago, # |   +50 Seemed like Problem D's time limit a little bit too strict?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +8 I had that problem too, is the intended time complexity less than Θ(n^2+n*sqrt(10^8))?
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +8 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]).
•  » » » » 3 years ago, # ^ |   0 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.
 » 3 years ago, # | ← Rev. 2 →   0 I didn't lock my solution and I got hacked HOW!!!!! here
•  » » 3 years ago, # ^ |   +14 Locking grants you the rights to hack others, not protects you from being hacked.
•  » » 3 years ago, # ^ |   +1 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.
 » 3 years ago, # |   +3 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 ???
 » 3 years ago, # | ← Rev. 3 →   -39 Hasan0540 why you are so strict at dataset for problem F!!!
•  » » 3 years ago, # ^ |   +70 May be because the intended solution was not a simple BFS?
 » 3 years ago, # |   +1 I could not make out D. Can someone make me understand what the problem statement meant?
 » 3 years ago, # |   0 any on got WA test 5 in the problem B then got AC ? any test case ?
•  » » 3 years ago, # ^ |   0 5 1Answer is yes ..... ..#.. ..... ..... 
•  » » » 3 years ago, # ^ |   0 Do you know test 8. I'm stuck at that :(
•  » » » » 3 years ago, # ^ | ← Rev. 4 →   0 7 7  YES ....... .#####. .#...#. ....... 
•  » » » 3 years ago, # ^ |   0 my answer :  YES ..... .#... ..... ..... 
 » 3 years ago, # |   +1 rip my rate oh wait it's already bad
 » 3 years ago, # |   +2 it is rated or yes?)))
•  » » 3 years ago, # ^ |   -11 I hope it's UR or Semi-Rated,but Unfortunately, here is Codeforces so it's maybe Rated...
•  » » 3 years ago, # ^ |   -16 Mike, please, do it unrated, you ruined my rating
 » 3 years ago, # |   0 How to do B? I thought to create symmetric parts on the innner matrix. Any suggestion?
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » » 3 years ago, # ^ |   0 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).
•  » » » » 3 years ago, # ^ |   0 So bad I also thought about that solution but cannot prove it.Now that I implemented that successfully. So pity.
 » 3 years ago, # |   +12 My first hack on problem A (38026095)Seriously I don't know how that passed the pretests...
 » 3 years ago, # |   0 I think the problems are really nice.But I spent some time hacking ,and have no time to write out problem E.So sad.
•  » » 3 years ago, # ^ |   0 can you share idea for E, this is my WA on test 8 solution, http://codeforces.com/contest/980/submission/38049503
•  » » » 3 years ago, # ^ |   0 I haven't got aceepted now,sorry.But my idea is almost the same as yours.Add the points from n to 1.
•  » » » 3 years ago, # ^ |   +2 Well,maybe you forget one function you wrote yourself.clca().What a pity!
•  » » » » 3 years ago, # ^ |   0 oh no, i need some rest
 » 3 years ago, # |   +2 I could not make out D. Can someone make me understand what the problem statement meant?
•  » » 3 years ago, # ^ |   0 Same question. why is the answer to array [5] is 1???
•  » » » 3 years ago, # ^ |   +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
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 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 is4 2 0
•  » » » 3 years ago, # ^ |   0 thx
 » 3 years ago, # |   0 How to solve problem C?
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 I still couldn't understand C. I think I need to improve my English skills first :(
 » 3 years ago, # |   +1 Stupid cases of 0's in D. These puzzling cases aren't fair :/
 » 3 years ago, # |   +2 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!
•  » » 3 years ago, # ^ |   0 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
•  » » » 3 years ago, # ^ |   +3 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 years ago, # ^ |   0 3 independent cases? I handled only 2 independent cases
•  » » » » 3 years ago, # ^ |   0 In my approach i had to handle cases of: k=even, k=odd and <=(n-2) and k=odd and >(n-2)
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 I handled: k = 2 * (n - 2) and k < 2 * (n - 2) But know i even now how to handle even one case
•  » » » » » » 3 years ago, # ^ |   0 Can you explain your approach a bit?
•  » » » » » » » 3 years ago, # ^ | ← Rev. 2 →   +3 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.
 » 3 years ago, # |   +30 Clarification on A was so unfair, for people, who already failed on this case, and got minus points
•  » » 3 years ago, # ^ |   -6 i also deal with this and the jury said "It is clear from the statements." , i hope it's unrated. this contest is worst
•  » » » 3 years ago, # ^ |   +10 But it was clear from the statements...
 » 3 years ago, # |   +9 D in a nutshell.
 » 3 years ago, # |   +13 tfw when you forgot to handle negative numbers in d.
•  » » 3 years ago, # ^ |   +34 More people fail because of zero than negative numbers in D.
 » 3 years ago, # |   +53 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.
•  » » 3 years ago, # ^ |   0 I agree. I think some participants could solve F if they had another one hour.
 » 3 years ago, # | ← Rev. 2 →   -92 I didn't really like this contest
 » 3 years ago, # |   +10 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.
•  » » 3 years ago, # ^ |   +4 Can someone translate problem D
 » 3 years ago, # |   0 A could really use some constraints on perl/links numbers and D's statement was so bad.
 » 3 years ago, # |   0 Whats test 20 in D?
 » 3 years ago, # |   0 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.
 » 3 years ago, # |   +13 Can anyone please give me the proof for problem B's solution?
•  » » 3 years ago, # ^ |   +3 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.
•  » » » 3 years ago, # ^ |   +3 So for the last case — odd k and k>(n-2), I can place the hotels anywhere?
•  » » » » 3 years ago, # ^ |   +3 No. Place them like this ....... .#####. .#...#. ....... see you blocked all ways and only 2 left.
•  » » » » » 3 years ago, # ^ |   +3 Yeah, thats what I did but since you said that it would always be 2, I got confused :pThanks for the help :)
•  » » » » » » 3 years ago, # ^ |   +3 oh sorry my bad. yeah you have to block such that its 2. xD
 » 3 years ago, # |   +9 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.
•  » » 3 years ago, # ^ |   0 Congrats!
•  » » » 3 years ago, # ^ |   0 Thank you, we are both now masters :)
 » 3 years ago, # |   +5 Can someone explain the problem statement for D ?
 » 3 years ago, # |   0 Problem B Can you help the mayor place the hotels in a way such that there are equal number of shortest paths from each village to its preferred pond? But they are counting all paths.Please,be more clear about the problem statement. Thank you
•  » » 3 years ago, # ^ |   0 shortest paths is the keyword.
•  » » » 3 years ago, # ^ |   0 wrong answer The number of paths between opposite corners doesn't match: 2 and 3 They are counting all paths so shortest paths is the wrong keyword which caused a lot of problems I believe.
•  » » » » 3 years ago, # ^ |   0 The problem is correctly asking for shortest paths. Remember this is distance in taxicab geometry, so in a 4*n grid, going from (1,1) to (4,n) takes 3+n-1 steps regardless you take the "inverted-L-shaped" path or some intermediate "staircase-shaped" path. This is true for any path that does not go back to the starting point. This is the same for (4,1) to (1,n).For my reasoning, the key was observing how the two "diagonal" paths (that are shortest paths too!) crossed => place hotels with horizontal symmetry.
•  » » » » » 3 years ago, # ^ |   0 Understood,thanks a lot
 » 3 years ago, # | ← Rev. 2 →   0 PROBLEM B: for input 9 5 why YES..........##.#......#.#.............isn't an answer?
•  » » 3 years ago, # ^ |   0 You can understand why it is not correct answer by thinking on simplified but similar case: 5 5 ..... .#?#. ..##. ..... (question mark means doesn't matter)
•  » » » 3 years ago, # ^ |   0 thanks. I misunderstood the problem.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 (1,1) -> (4,9) 23patterns(4,1) -> (1,9) 22patternsYES ......... ..#####.. ......... ......... is one of the answer
•  » » 3 years ago, # ^ | ← Rev. 4 →   +1 While other paths are symmetric, there's one exception. For the one that starts from the upper side and first goes down, A........ A##.#.... AA#.#.... .AAAAAAAA and A........ A##.#.... A.#.#.... AAAAAAAAA are both possible, while for the opposite side, only AAAAAAAAA A##.#.... A.#.#.... A........ is possible.edit: Thanks rsFalse!
•  » » » 3 years ago, # ^ |   +6 Use block formatting it gives monospace font.
 » 3 years ago, # |   +9 Problem BBased on intuition : easyBased on Proof : hard
•  » » 3 years ago, # ^ |   +7 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.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 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 this00000!0000000#00#00#000#00#!#00#000000!00000 )proof doesn't look hard
 » 3 years ago, # |   +3 Wow, exactly 50 users became Master according to new rules!
 » 3 years ago, # | ← Rev. 2 →   +25 Wow, I've become so numb orange, but now it is not so cool
•  » » 3 years ago, # ^ |   +8 For 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.
 » 3 years ago, # |   +4 while I had a very bad contest but the problems was so beautiful. thanks for that Hasan0540.
 » 3 years ago, # |   +5 What is case 18 in problem D. I keep getting WA.
•  » » 3 years ago, # ^ |   +3 I also had WA 18 0 * (ANY NUMBER) = 0 — square also 0%(j*j)==0 (this should help)
•  » » » 3 years ago, # ^ |   0 Thanks!It was unclear whether 0 is perfect square or not while I was competing!
 » 3 years ago, # |   +4 Can anyone explain me problem C ? I read at least 10 times, still find hard to understand.
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 7 30.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.
•  » » » 3 years ago, # ^ |   0 Thank you so much. Now it's clear :)
 » 3 years ago, # |   +1 Could someone please explain the symmetric approach used to solve B? I can't understand how to think in the correct direction.
•  » » 3 years ago, # ^ | ← Rev. 6 →   0 Well it's easy to see that if you set hotels symmetrically equal to each other, the tourists will always have the same number of paths. The worst case is to set hotels is such a way like ....... .#####. .#..... ....... at this point, there will be no equal number of paths because you block the shortest way to upper guys and lower ones have no problem to pass. But it doesn't give the "NO" answer, because you can just set that one hotel in the middle of second line since they made us sure, number of columns will always be odd.So there is no option to get wrong answer, you can just do:fullfill lines if number of hotels is bigger than n — 2 and for modulo number of hotels left from k / (n — 2) (the rest of them) set simmetrically like 1st column -> last column -> 1st column -> last column.. with one condition, if your modulo equals 1 (so there is only 1 hotel to be set) just place it in the middle of the lineIn other words always go like -> middle -> left -> right -> left -> right... 7 3 ....... .#.#.#. ....... ....... 7 1 ....... ...#... ....... ....... 7 7 ....... .#####. .#...#. ....... Submission -> 38056037That's my approach to this problem and i hope i explained it clearly with not much language mistakes :)
•  » » » 3 years ago, # ^ |   0 Aah, now they make sense to me. Your first example made it pretty clear and the middle->left->right... seems to be the way to go. Thanks a lot! I coded it in a similar fashion and got an AC. Great explanation! Here is my code: 38055986
•  » » 3 years ago, # ^ | ← Rev. 2 →   +5 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 ....X XX... ....X XXXXX ...XX .XX.. ....X ....X .XXX. ..XXX or ....X ....X XX... ....X XXXXX ....X 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)
•  » » » 3 years ago, # ^ |   0 It is easier to place hotels with vertical symmetry
•  » » » » 3 years ago, # ^ |   0 Could you please elaborate why?
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 Because you don't need to handle many cases. Solution with only one 'if': 38060661
•  » » » » 3 years ago, # ^ |   0 We probably mean the same thing! By horizontal symmetry I mean over a vertical axis.
•  » » » » » 3 years ago, # ^ |   0 Oh, my bad
•  » » » » » » 3 years ago, # ^ |   +8 Not at all, I should have been clearer!
•  » » » 3 years ago, # ^ |   0 I don't quite understand how you implied crossing of the diagonal path leads to placing hotels with horizontal symmetry..I think horizontal symmetry works well with even k. Could you explain how you approached odd k using the same logic?
•  » » » » 3 years ago, # ^ |   0 See for example the (now fixed) drawing in my comment above. The crossing diagonal paths form a shape resembling an X, while path on the borders are L-shaped. Imagine to morph between the two to find other possible paths.If there are no hotels, for any path from top-left to bottom-right you can find a mirrored path from bottom-left to top-right. For any top-left path you remove, you want to remove the corresponding bottom-left path.For example, to remove the two diagonal like paths you can place two hotels like this: ....X XX... ....X XX... ...XX .XXX. .#.#X .#X#. .XXX. ...XX => .XXX. ...XX XX... ....X XX... ....X As you say, this works well with even number of hotels. For odd number of hotels it just works: you have an odd number of columns, so place one more hotel in the middle column. See my solution at http://codeforces.com/contest/980/submission/38049226They grow roughly like this: ....... ...#... ..#.#.. ..###.. .##.##. .#####. .#####. .#####. ....... ....... ....... ....... ....... ....... ...#... ..#.#.. 
•  » » » » » 3 years ago, # ^ |   0 Yes, now it makes sense. Amazing work! Thank you for explaining your approach. Really helpful!
 » 3 years ago, # |   +59 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:
•  » » 3 years ago, # ^ |   0 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 :)
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 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! :)
•  » » » » 3 years ago, # ^ |   +2 For your reference, here's 6 rounds version of it :)
•  » » » » » 3 years ago, # ^ |   +3 Thanks for these pictures.
 » 3 years ago, # | ← Rev. 3 →   0 Pretest passed on D at 01:47 Immediately locked all problems and started hacking 3 minutes later found silly mistake in my submission of D (before looking at other people's solutions) Shouted "fxxk" Turned out that SO MANY people FSTed on D that I still got +17 rating (should have got about +60 if I made D right)
 » 3 years ago, # |   0 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- for i in range 1 to n : c := 0 for j in range i to n : if back[j] = -1 then : c := c + 1 cnt[c] := cnt[c] + 1 for j in to(i) : back[j] := -1 Where is the answer array.But I got Wrong Answer on test 18. SubmissionCan anyone check and tell what's wrong here?
•  » » 3 years ago, # ^ |   +11 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
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thanks. Got AC.