### arsijo's blog

By arsijo, 3 months ago, translation, ,

Hi everybody!

Summer... It is a wonderful time for traveling, walking with friends, new discoveries and, of course, writing new exciting contests at Codeforces. Thus, I bring to your attention my new Codeforces Round #495 (Div. 2) with interesting tasks that will take place on Jul/05/2018 19:35 (Moscow time). If your rating is less than 2100, this round will be rated for you; otherwise, you can participate out of competition.

I would like to thank Mike MikeMirzayanov Mirzayanov for his help with problems preparing and for Codeforces and Polygon platforms. Also, Ildar 300iq Gainullin, Dmitry _kun_ Sayutin, Daniil danya.smelskiy Smelskiy, Chin-Chia eddy1021 Hsu, and Kevin ksun48 Sun for the problems testing.

You will be given 6 problems and 2 hours to solve them. Scoring distribution will be announced later.

In this round, you will have to help Sonya with her daily problems. Good luck!

UPD. Scoring 500-1000-1500-2000-2500-3000.

UPD. Congratulations to winners!!!!

Rank Nickname Score
1 EZ_fwtt08 7892
2 milisav 5550
3 VisJiao 5294
4 Jatana 4832
5 wasyl 4762

•
• +379
•

 » 3 months ago, # |   0 June 5?? Please correct the date, it's JULY 5.
 » 3 months ago, # | ← Rev. 2 →   -75 i hope good statement and many hacks
 » 3 months ago, # |   -38 I think this is the shortest, precise and most exciting round announcement I have ever read.I hope the problem statements are along the same lines.
•  » » 3 months ago, # ^ |   -41 So do I. A brief, simple, concise announcement.
 » 3 months ago, # |   +46 Hope that we wouldn't see number 502 with label "Bad gateway" again)
•  » » 3 months ago, # ^ |   -12 ^v^, Sure.
•  » » 3 months ago, # ^ | ← Rev. 2 →   -6 CF servers, please, be OK during the contest.
•  » » 3 months ago, # ^ |   +37
•  » » » 3 months ago, # ^ |   -28 maybe best joke ever
•  » » » » 3 months ago, # ^ |   +10 maybe best editing ever. Did you use Microsoft Paint?
•  » » » » » 3 months ago, # ^ |   -15 true story ..i want just funny way to do so ..
 » 3 months ago, # |   -112 Is it rated??????
•  » » 3 months ago, # ^ | ← Rev. 4 →   -44 deleted
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -56 Just kidding
•  » » » » 3 months ago, # ^ |   +2 i m _S1MPLE_ :\
•  » » 3 months ago, # ^ |   0 yes, but YOU are not
 » 3 months ago, # |   -58 I hope problem statement will be as short as the announcement. By the way best of luck to all the contestant. :)
 » 3 months ago, # |   +144 Rating is like life . Full of up and down down down down down down down .
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 I agree with you
•  » » 3 months ago, # ^ | ← Rev. 2 →   +14 are you saying this !!! hardly your rating had a downfall man ....but still i agree with you
•  » » 3 months ago, # ^ |   +3 I think what I have said may come true. :(
•  » » » 3 months ago, # ^ | ← Rev. 2 →   -9 yes with me too .. today Up
•  » » » 3 months ago, # ^ |   -9 yes with me too
•  » » » 3 months ago, # ^ |   -12 get -6
 » 3 months ago, # |   +27 Thank you for this announcement on the glorious Fourth of July. I hope my rating goes to 1776 after contest. For America, her allies, and my constitutional right to shitpost. #AMERICANUMBERONE
 » 3 months ago, # |   -9 Unimaginably, they've mentioned Mike.
 » 3 months ago, # |   -10 One more task and this would have been a beautiful regular round with two divisions.
• »
»
3 months ago, # ^ |
-27

I think that is bad!!

# lessdiv1rounds

 » 3 months ago, # |   -66 +1 if you want problems to be short and concise instead of long confusing stories...
•  » » 3 months ago, # ^ | ← Rev. 4 →   -41 How about +2 ?UPD: By the way, what is so wrong with wanting the problems to be short and precise?
•  » » » 3 months ago, # ^ |   -30 unfortunately it canot stop...
•  » » » 3 months ago, # ^ |   -13 The same thing that's wrong with "is it rated"
 » 3 months ago, # | ← Rev. 2 →   -38 Seeing so many grey comments under the announcement... Summing the number of downvotes and upvotes of the comments. Getting -10 per comment in average. Trying to find out what's wrong with comments. Understanding that killer_god said the genius thing: http://codeforces.com/blog/entry/59942?#comment-436969.
 » 3 months ago, # |   -20 It is shortest and best announcements according to that contest will be better.....
 » 3 months ago, # | ← Rev. 2 →   -20 Hope to the problem statement will be too much interesting. Best of luck for all.
 » 3 months ago, # |   -21 I hope we will get some flavor of Football. It will be more interesting not in just watching the game but also solving some problem related to them. Who knows, we may score better :p
 » 3 months ago, # |   +14 kun? Another Mathforces round?
•  » » 3 months ago, # ^ |   +71 How are testers related to the inner contents of the round?
•  » » » 3 months ago, # ^ |   +9 However, it happened...
 » 3 months ago, # |   -19 I hope codeforces work properly today.
 » 3 months ago, # |   -24 Where is KAN for help to prepare the round.
 » 3 months ago, # | ← Rev. 2 →   -12 I smell math for this round either
 » 3 months ago, # |   -28 who is sonya??
 » 3 months ago, # | ← Rev. 2 →   +4
•  » » 3 months ago, # ^ |   +3 Be careful — you've got 3 of 5 the most popular jokes in one picture. It will be very difficult not to be hidden.
 » 3 months ago, # |   -22 What to do if you don't meet Wael.Al.Jamal in comments and can't downvote all his comments for reaching the new record (-200 contribution)? EXACTLY! You must help Codeforces community to reach another record — the greatest total number of downvotes under the announcement in the history.
•  » » 3 months ago, # ^ | ← Rev. 2 →   -17 so .. i am famous now :) but in the bad way //comment meaningless (do not even matter)
•  » » 3 months ago, # ^ |   -14 i added some comments go and down-vote all of them
 » 3 months ago, # |   0 Down voting contest is going on. :v
 » 3 months ago, # | ← Rev. 2 →   0 Most of the comments are hidden!! I feel something is 'not usual' gonna happen today
•  » » 3 months ago, # ^ |   -18 earth is flat boy
 » 3 months ago, # |   0 After looking so many disappeared comment.Now i realised Thanos did right.Half of earther don't deserve to live on this earth
 » 3 months ago, # |   +14 arsijo, Is she the same Sonya from Codeforces Round #371 ..??
 » 3 months ago, # |   0 Again my rating will decrease.........Why there is no rank name under newbie....?
•  » » 3 months ago, # ^ |   +12 you have chosen wrong handle maybe :)
•  » » 3 months ago, # ^ |   0 -ve infinity is still king of the negatives.
 » 3 months ago, # |   0 I've noticed in the previous two Div 3 only rounds the registrations exceeded 8000 at both times and Div 2 contests don't often get that many participants. I wonder why
•  » » 3 months ago, # ^ | ← Rev. 2 →   -15 they prefer easy ones, :/ thinking they will be tourists one day and they wont :/
 » 3 months ago, # | ← Rev. 2 →   -13 Rating is like life . Full of up and down down down down down down down .see my graph
•  » » 3 months ago, # ^ |   +15 you are everywhere
•  » » » 3 months ago, # ^ |   0 I'll be in your nightmares see this
 » 3 months ago, # |   +2 Problems are loading very slow. Is it just me?
 » 3 months ago, # | ← Rev. 3 →   +23 #define int long longAre you serious?
•  » » 3 months ago, # ^ |   +25 Welcome to CF
 » 3 months ago, # |   +51 Congratulations to Codeforces with 40,000,000 sent solutions!
 » 3 months ago, # |   0 Am I the only one who is not able to submit the solution for problem C
•  » » 3 months ago, # ^ |   0 But you LGM! We believe in you!
 » 3 months ago, # |   +49 A very uneven contest. Problem C has 2k+ solutions, and problem D has less than 100. Codeforces needs to work on the aspect of balancing the problems evenly.
 » 3 months ago, # |   +45 A easy B easy C easy then suddenly D hard? Nice diff spread
 » 3 months ago, # |   +14 very confusing statement
•  » » 3 months ago, # ^ |   +4 Strongly agree. I had hard time understanding pA statement. Also forgot to set array value 0 in pC, cost me around half hour and 2 WA :(
 » 3 months ago, # | ← Rev. 2 →   +101 Attempting Problem D after successfully submitting Problem C:
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Well, I had no idea for D but I solved E(hopefully)(edit: RE 12) :P
 » 3 months ago, # |   +1 Was it just a bad day for me or there was seriously something weird with problem A? -_-
•  » » 3 months ago, # ^ |   +1 No, you are not alone
•  » » 3 months ago, # ^ |   0 The way problem was framed: For the given test case 2: 5 2 4 8 11 18 19 The answer should have been: 7 i.e. 2, 6, 13, 14, 15, 16 and 21
•  » » » 3 months ago, # ^ |   +1 If you're gonna count 14 and 15 why not count 22,23,24... as well?
•  » » » 3 months ago, # ^ |   0 "She wants to make the minimum distance from this hotel to all others to be equal to d".14 and 15 are not valid cities, because the minimum distance to an hotel is 3 for both of them, and in that test d = 2.
•  » » » » 3 months ago, # ^ |   +9 When a hotel is located at 13, how is the distance equal to d for all the other hotels apart from hotel at 11
•  » » » » » 3 months ago, # ^ |   0 "The minimum distance from this hotel to all the others" = "The minimum of all the distances to the others hotels" = "The distance between this hotel and the nearest".
•  » » » » » » 3 months ago, # ^ |   +5 Actually, if you want to "make the minimum distance from this hotel to all others to be equal to d", then you are saying that for each hotel different from the yet-to-add hotel, you want the distance to be equal to d.It's obvious in this problem that this wasn't the intended meaning (actually, it wasn't obvious to me, I had to look at the sample tests), but if the problem involved a graph, for example, then I would never have thought that:"The minimum distance from this hotel to all the others" = "The minimum of all the distances to the others hotels"is true.
•  » » » » » 3 months ago, # ^ |   0 "the minimum distance from this hotel to all others".The minimum distance to an hotel if you are in city 13 is 2 (hotel 11). Please notice that the problem ask for the minimum distance to any other hotel, not all the distances.
 » 3 months ago, # |   +7 Wow, D was pretty tough for me...Can anyone provide a solution? My only thought was to simulate different possibilities with BFS and use heuristics to lower the search space, but I still timed out.
 » 3 months ago, # |   +3 How to solve B? I didn't get any idea
•  » » 3 months ago, # ^ |   +17 Just print an alternating 01 array. (Convince yourself why this is true)
•  » » » 3 months ago, # ^ |   +13 Kill me :')
•  » » » » 3 months ago, # ^ |   +13 We all have felt the same in some contest or the other.
•  » » » 3 months ago, # ^ |   0 I had thought of this solution but instead of proving it correct I thought it is too stupid solution which will not pass even the pretest.
•  » » » » 3 months ago, # ^ |   0 I also thought it can't be right, but since I didn't have any other ideas, I figured the risk of WA will be worth it on the off chance that it's correct.
•  » » » » » 3 months ago, # ^ |   0 Why not? Let x be no. of roses then we have to maximize x(n-x) = nx — x^2. Differentiate and get x = n/2. For segment of even length if we place alternating 01 we will get equal no. Of both the flowers. For odd length segment we will get (n+1)/2 and (n-1)/2 which will maximize the product.
•  » » » » » » 3 months ago, # ^ |   0 i thought the same way
•  » » » » » » 3 months ago, # ^ |   0 I thought it can't be right because that solution is too easy for Div2B.
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 I just printed a n length alternate string and it passed the pretest (01010101010...till n). I hope it passes the system tests.
•  » » 3 months ago, # ^ |   0 You need print "01" alternativey. Now why this is the right way. Supposefor some person has start l and end at r. Now what's the max possible answer. suppose you have R roses and L lily. Now R+L=(r-l+1) And we wish to maximise R*L. Standard. Very Standard. It will be maximum when R is as closed to L as possible. Which will be always satisfied by our answer of printing "01". As in every segment abs(R-L)<=1. So this answer is correct.
 » 3 months ago, # |   +24 What was Pretest 4 in D?
•  » » 3 months ago, # ^ | ← Rev. 2 →   -8 I think it will be either for n=1 or m=1 type of test case. Or where no of occurrence of each digit always produce -1.
 » 3 months ago, # |   0 How could so many people solve B? Is there anything I didn't keep in mind?Also, F seems to based on sqrt-decomposition approach, doesn't it?
•  » » 3 months ago, # ^ |   +6 answer B:"01010101010101..."
•  » » » 3 months ago, # ^ | ← Rev. 3 →   +1 Nooooo
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 But what ifInput2 11 2
•  » » » » 3 months ago, # ^ |   0 The maximum beauty will be 1 with 01 or 10. If two flowers are of the same type, you'll get the beauty of 0 (since one type got no flowers).
•  » » » » » 3 months ago, # ^ |   0 I want to die :(I thought in "010101..." but did not notice what you said so I discarded that solution >_< .
•  » » » » » » 3 months ago, # ^ |   +1 Chill bro I couldn't even think of it for entire two hours :DGoodbye ratings anyway :D
•  » » » » » » » 3 months ago, # ^ |   0 Same here :(
•  » » » » 3 months ago, # ^ |   0 01 is still optimal as it gives 1 as ans. others give 0.
•  » » » » 3 months ago, # ^ |   +3 Approach and Proof For B a/c to me. You need print "01" alternativey. Now why this is the right way. Supposefor some person has start l and end at r. Now what's the max possible answer. suppose you have R roses and L lily. Now R+L=(r-l+1) And we wish to maximise R*L. Standard. Very Standard. It will be maximum when R is as closed to L as possible. Which will be always satisfied by our answer of printing "01". As in every segment abs(R-L)<=1. So this answer is correct.
•  » » 3 months ago, # ^ |   0 the answer is 01010101.... I hope this clears main tests.
•  » » 3 months ago, # ^ |   +3 B=1010101
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 F: Nope segtree on bits I think
•  » » » 3 months ago, # ^ |   0 Can you express your ideas?I tried with sqrt but got completely stuck in the 1st query.
•  » » 3 months ago, # ^ |   +3 for B, you just have to print alternative 0 and 1.
•  » » 3 months ago, # ^ |   +3 In B it is always optimal to print alternating ones and zeroes
•  » » 3 months ago, # ^ |   +3 Its solution is constructive. You just need to output alternate 1s and 0s as they will maximize the product for all segments given a fixed sum.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +21 What????????Why didn't I even think of that in B? :
•  » » » 3 months ago, # ^ |   0 It happened with me too :(
•  » » 3 months ago, # ^ |   0 I think greedy solution works, alternate one's and zero's are the best way to split, irrespective of every thing.For any given number n,product is max when the numbers are equal(n is even) or n/2 and n/2 +1
•  » » 3 months ago, # ^ |   0 I spend all my life to implement a f**king super algorithm ...
•  » » » 3 months ago, # ^ |   0 Lol. I actually got no idea and decided to try F instead. Worst decision I've ever made :D
 » 3 months ago, # |   0 What an awesome contest. Thanks!
 » 3 months ago, # |   +3 how to solve C
•  » » 3 months ago, # ^ |   +1 For every unique element from left to right, add the number of unique elements to the right of it to the ans.
•  » » » 3 months ago, # ^ |   0 this will be O(n^2). That is why didn't even try this approach
•  » » » » 3 months ago, # ^ |   +1 You can do this in O(nlogn)... Initially traverse from right to left keeping track of unique elements using set. And then traverse from left to right, (using a new set) for every unique element just add the value of the number of unique elements to right of it.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 I passed using binary search, for every unvisited element start from left say index 'i', find the number of elements on the right(>i) such that their first occurrence(considering from right) is not equal to or before current our index i, i.e their first occurrences should always come after current index 'i'.
•  » » » » 3 months ago, # ^ |   +4 can be done in O(n) http://codeforces.com/contest/1004/submission/40006342
•  » » 3 months ago, # ^ |   +3 I believe you can keep two vectors, one for the positions of the leftmost occurence of a number, and one for the right. You can iterate over the first vector and sum up all the ones in the second vector that are bigger than it (meaning no intersection) using binary search or c++ upper bound.
•  » » 3 months ago, # ^ |   0 for each position find the number of distinct numbers in the range [position+1, end of arr]
•  » » » 3 months ago, # ^ | ← Rev. 2 →   0 31 1 2According to you answer would be 3 but it will be 2, right?
•  » » 3 months ago, # ^ |   0 It is quite easy with sets in c++.
 » 3 months ago, # |   +2 For this contest will have to say don't think too much.
 » 3 months ago, # |   +6 What could be testcase 4 of D ?
 » 3 months ago, # |   +5 Does the solution to E involve finding the Centroid of the tree? (Centroid in terms of the distance, not in terms of the number of nodes)
•  » » 3 months ago, # ^ |   +3 You mean center of the tree? Yes.
•  » » » 3 months ago, # ^ |   +21 Take a diameter. And check each k consecutive on it?
•  » » » » 3 months ago, # ^ |   +3 I placed the center on the path, then binary searched on the answer. For each such value I accounted for the nodes which needed to be in the path, and tested whether the path was valid (one segment of length at most k). I'm pretty sure that binary search was unnecessary, however.
•  » » » » 3 months ago, # ^ | ← Rev. 2 →   0 could you please tell me proof or how you came up with your idea of E .. that is sliding a window of size k on the longest path of tree..thanks
•  » » » » » 3 months ago, # ^ |   +9 For me,it seemed we can always move towards a global maxima taking suboptimal path and greedily making it better (But no guarantees of it being true.Will be happy if someone can confirm it.)Then I proved that answer will exist on diameter by exchange argument.Then sliding window is kind of searching complete space.
•  » » » 3 months ago, # ^ |   0 Yes, the center. Thanks.So, after finding the center, do we maintain a priority queue with ascending order of sums of distances the children of a node have to travel to the parent of the node(the parent will have an ice cream store for sure)?In the PQ, we first insert the neighbours of the center, then take one node out of the PQ, set an ice cream store there, then insert it's neighbours, and keep doing this until we don't have any stores left to set up?
•  » » » » 3 months ago, # ^ |   0 I believe that should work, as long as you are checking that the stores form a valid segment at every point in time.
•  » » » » » 3 months ago, # ^ |   0 Got it, thanks! :)
 » 3 months ago, # |   +10 Too long statements. Surprised with the problem B.
 » 3 months ago, # |   0 I had one interesting idea for E which I want to share, I am really curious will it pass all testcases. I think I have a little strange background of my solution, so it possible I have bug. Anyway here is idea with randomisation:In case we know one node in the result path, we will always go in subtree which contains furthest node from that node ( if we have two ends, we will choose node with 'better; subtree...)Now if k < const and diametaroftree < const we can explore paths from each node and calculate best result. Otherwise we can choose const random nodes, investigate them in O(k) and choose best result. For const near 1000 , probability for mistake should be really small.
 » 3 months ago, # |   0 What was the solution for F?
 » 3 months ago, # |   +18 How did you solve Div 2 D ?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 Hint: Given n and m, if you know the maximum element in the list and the smallest element x whose frequency is not 4*x, you can determine the position of zero in the matrix(if solution exists for given n and m).
•  » » » 3 months ago, # ^ |   0 I have an interesting idea. let mx=highest value of the elements. if it is odd than 0 will be in (mx/2+1,mx/2+2) position if it is even than 0 will be in (mx/2,mx/2) position now try to build the matrix with 0 in that position for all divisors of n. example: 18 2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1 mx=4 0 will be in (2,2) divisors of 18 are 1,2,3,6,9,18 so we will try to build the matrix where m*n= (1*18) /(2*9)/ (3*6)/(18*1)/(9*2)/(6*3) and position of 0 is (2,2) (I think this solution will work but not sure. just sharing my idea with you. :D Let me know if you find anything wrong in this idea)
•  » » » » 3 months ago, # ^ |   0 if frequency of maximum element is 3 it will fail 0 1 1 1 2 2 3 3 3
•  » » » » » 3 months ago, # ^ |   +1 It can't be 3. There is no solution for your test case.
•  » » » » » » 3 months ago, # ^ |   0 yes but his algorithm doesn't check for impossible test cases
•  » » » 3 months ago, # ^ |   0 how ?
•  » » » » 3 months ago, # ^ |   0 Assume zero appears on the bottom right quadrant, maximum element appears on the top-left corner and element x-1 lies to the extreme right of zero. (You can flip any other solution to get this configuration).
 » 3 months ago, # |   +21 Is there a reasonably short way to solve D? My idea was to watch the growth of the sequence of counts of different numbers, predicting what the next number should be assuming that the corresponding rhombus does not hit the edge of the matrix. Then, if the prediction turns out to be wrong (the actual count is lower than the expected one), consider the different cases of edge positions. But those predictions and subsequent pattern matching have tons of corner cases and are ridiculously tedious to implement.
•  » » 3 months ago, # ^ |   0 I actually used the same thing. Yes it was hard to implement. But not as many edge cases as you might think. n and m can be interchange. if i,j is center then m-i,n-j being center is also a solution etc. So quite a few cases get handled together.
•  » » » 3 months ago, # ^ |   0 In problem D,if matrix of i x j gives me correct ans,then,I think j x i will give me correct ans too.Correct me if I am wrong?
•  » » » » 3 months ago, # ^ |   0 Ya that was actually what I meant when I said n and m can be interchanged.
•  » » 3 months ago, # ^ |   0 I could not solve the question but thought something.One(or all) of corner/s will have the maximum element, hence the maximum element can occur either 1,2 or 4 times only.if it's frequency is 1 then it will occur at corner and we can get the coordinates of (0,0)if it's frequency is 4 then (0,0) will in the center of the matrixif it's frequency is 2 then we have some possible combination where i got stuck.If anyone thinks this can be , it would very helpful
•  » » 3 months ago, # ^ |   0 I have an interesting idea. let mx=highest value of the elements. if it is odd than 0 will be in (mx/2+1,mx/2+2) position if it is even than 0 will be in (mx/2,mx/2) position now try to build the matrix with 0 in that position for all divisors of n. example: 18 2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1 mx=4 0 will be in (2,2) divisors of 18 are 1,2,3,6,9,18 so we will try to build the matrix where m*n= (1*18) /(2*9)/ (3*6)/(18*1)/(9*2)/(6*3) and position of 0 is (2,2) (I think this solution will work but not sure. just sharing my idea with you. :D Let me know if you find anything wrong in this idea)
•  » » 3 months ago, # ^ |   0 I wasn't sure about TL but it passed. My solution was to stop once you hit first edge, let's call that distance s.Now let's look at the biggest number m and iterate over all possible splits m = a + b. Then one edge of rectangle is a+s+1, and if that divides n there's only one possible position for 0. Now let's check that it's correct with bruteforce approach.
 » 3 months ago, # |   +8 For those who passed D with >1000ms. Try test n = 840, m = 858, cx = random(1, n), cy = random(1, m).
 » 3 months ago, # |   +54
 » 3 months ago, # |   0 what the hell is testcase 4 in D..!!Can't debug..
 » 3 months ago, # |   +1 My ratings to me after not solving B. :(
•  » » 3 months ago, # ^ |   -14 t takes me 1 min , so easy
 » 3 months ago, # |   0 Can we solve E by choosing K consecutive segment of nodes in the largest path of tree? Like sliding a window of size K
•  » » 3 months ago, # ^ |   0 I think so. Though I used binary search after finding the longest path, not sliding a window.
•  » » » 3 months ago, # ^ |   +3 how did you write check function of bs?
•  » » 3 months ago, # ^ |   0
•  » » 3 months ago, # ^ |   0 could you please tell me the proof for this idea?
•  » » » 3 months ago, # ^ |   +3 Suppose that you don't choose the K nodes in the maximum weighted path, it means that at a particular node you chose a path that was smaller than the largest path. Now this means that the farthest distance of the node with ice cream will increase. The best way to visualise this is by arranging the tree structure such that it looks like the most weighted path is a straight line and all other sub paths are hanging from each of the nodes in the max weighted path.
 » 3 months ago, # |   +3 Did anyone actually solve problem B with a solution different from "01010101..."? That would be hilarious.
•  » » 3 months ago, # ^ | ← Rev. 2 →   +5 not entirely different but I sorted ranges based on l and r. Then for each ranges from l to r put alternation 0/1 based ans[l].feeling stupid now
•  » » 3 months ago, # ^ |   -21 I solve it with different idea.
•  » » 3 months ago, # ^ |   -17
•  » » » 3 months ago, # ^ |   +25 Only difference i recognize that your code writes 101010... instead of 010101...
•  » » » » 3 months ago, # ^ |   -27 yeah u are right.... But i told that "I solved it with a diff idea" .
•  » » 3 months ago, # ^ |   0 let us hope that the author's solution gives the same output as in sample test cases, otherwise, they are just camouflage, and let us pretend that the problem is more of solved using logical proof rather than scratch and win strategy
 » 3 months ago, # |   +19 Unhackable round ! xd
•  » » 3 months ago, # ^ |   +10 Though that +1 hack really saved my rating... it gave me like 200 ranks.
•  » » » 3 months ago, # ^ |   0 Lucky you. Some people did not have wrong solutions in their room.
•  » » 3 months ago, # ^ |   +3 i hacked +1.
•  » » 3 months ago, # ^ |   0 D was hackable :D
 » 3 months ago, # | ← Rev. 2 →   +25 A quick system test considering the number of participants and even quicker ratings update.
 » 3 months ago, # |   0 Why is this code getting TLE in test 52 in problem E? 40007267
•  » » 3 months ago, # ^ | ← Rev. 2 →   +3 Imagine star graph (one vertex connected to other n — 1 vertices). For example lets consider center vertex numbered 1. You will call function llenaDist(1, p) n — 1 times. And function llenaDist(1, p) working in O(n). So complexity is O(n2)
•  » » » 3 months ago, # ^ |   0 Thanks! Do you know how can i calculate this distances more efficiently?
•  » » » » 3 months ago, # ^ |   +3 Make tree rooted, do 2 dfs. First calculating dp bottom-up, second calculating it top-down. See submission for details Fuctions called dfs1 and dfs2
 » 3 months ago, # |   +14 legendary speed system test and rating update
 » 3 months ago, # |   0 elijahqi was 4th in standings. After system tests, he is not in the rankings at all. what happened here?
•  » » 3 months ago, # ^ |   0 maybe cheat !
 » 3 months ago, # |   0 Why are long and int of the same limits on the compiler used in Codeforces? In other websites long has wider range than int and equal range as that of long long.
•  » » 3 months ago, # ^ |   0 Which platform are you talking about? I've never seen that. In every new compiler I've seen long long is larger and int and long have same size.
•  » » » 3 months ago, # ^ |   +5 https://www.codechef.com/ide This is not a competitive coding platform: https://ide.geeksforgeeks.org/
 » 3 months ago, # | ← Rev. 2 →   -8 Why the answer of problem E for the second sample is 7 and not 6?If the shops are in : 3, 4, 5.The minimum distance of node i to any shop is:Junction 1: Shop 4 — Minimum distance is 6Junction 2: Shop 3 — Minimum distance is 6Junction 3: It is a shop — Minimum distance is 0Junction 4: It is a shop — Minimum distance is 0Junction 5: It is a shop — Minimum distance is 0Junction 6: Shop 4 — Minimum distance is 6Junction 7: Shop 5 — Minimum distance is 2Junction 8: Shop 3 — Minimum distance is 1Junction 9: Shop 4 — Minimum distance is 6Junction 10: Shop 4 — Minimum distance 5In this way, the answer is 6, isn't it? What is wrong in this solution?
•  » » 3 months ago, # ^ |   +3 shops should form a simple path.
•  » » » 3 months ago, # ^ |   0 Thanks!!
 » 3 months ago, # |   +9 Problem B was kind of a one-shot problem. You need to wait till you realise the answer is alternating zeros and ones.
•  » » 3 months ago, # ^ |   -27 yes , it takes me 1 min
 » 3 months ago, # |   +4 easy problems B, C
 » 3 months ago, # |   0 how to solve problem D?
•  » » 3 months ago, # ^ |   0 I have an interesting idea. let mx=highest value of the elements. if it is odd than 0 will be in (mx/2+1,mx/2+2) position if it is even than 0 will be in (mx/2,mx/2) position now try to build the matrix with 0 in that position for all divisors of n. example: 18 2 2 3 2 4 3 3 3 0 2 4 2 1 3 2 1 1 1 mx=4 0 will be in (2,2) divisors of 18 are 1,2,3,6,9,18 so we will try to build the matrix where m*n= (1*18) /(2*9)/ (3*6)/(18*1)/(9*2)/(6*3) and position of 0 is (2,2) (I think this solution will work but not sure. just sharing my idea with you. :D Let me know if you find anything wrong in this idea)
 » 3 months ago, # | ← Rev. 5 →   0 Can anyone explain me, why one submission gets AC, and other TL4, they seem to have near the same complexity and idea?
 » 3 months ago, # |   0 I think there was a mistake in my source code for problem A. But my solution got accepted. Here is the link to my solution: http://codeforces.com/contest/1004/submission/40001844 If i input 4 as hotel number and 2 as difference and 1 2 4 and 40 as the hotel locations,should there not be all locations in between 6 and 38 and the additional 2 locations for two ends? i think my solution did not cover this part. I hope it can be checked and clarified. Thanks
•  » » 3 months ago, # ^ |   0 The problem description created this confusion to me also as it said the minimum distance must be d.But when I asked about the same they replied "The distance from new point to the nearest existing point should be exactly d."I wasted a lot of time in this :(.
•  » » » 3 months ago, # ^ |   0 Well they specified minimum distance. So it should cover the points in between. I submitted considering to be exactly d but then i realized that all ppints should be there for large difference
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 However, it works because when you compare c[n] — c[n-1] (j = 0, 1, ... n-1) and d * 2, c[n]-c[n-1] is bigger, because c[n] can be everything, something like 1006547729 for example.
•  » » » 3 months ago, # ^ |   0 Thats a good point to consider,but still i think my code won't work. Cause i specifically increased only 2. That means the locations added can never be more than 2 at a time for a single case of difference
 » 3 months ago, # | ← Rev. 2 →   +6 I'm surprised the rating change was shown in just about one hour after contest end. Thank you to the Codeforces team for reducing the waiting time. Hope to see this improvement in future contests!
 » 3 months ago, # |   +7 When you skip B because you have no idea of the right greedy strategy, spend 1h30 on D and at the 1h55 mark understand what B was really asking for...
•  » » 3 months ago, # ^ |   -31 i get the idea in 1 min
•  » » » 3 months ago, # ^ |   -8 I count two minutes (three minus one minute for reading). Maybe this is the reason of downvoting...
•  » » » » 3 months ago, # ^ |   -26 1 min after reading idiot
 » 3 months ago, # |   +2 I'm not gonna say this contest is bad because I'm always grateful when there is a new contest, but the problems' difficulty distribution makes no sense: A, B, and C were all the same difficulty (actually A is probably the hardest). It doesn't even test programming skill, just write fast and pray there aren't any bugs and you get +100 rating.
•  » » 3 months ago, # ^ |   0 Especially with a troll problem like B. :/
 » 3 months ago, # |   0 how to solve A?
•  » » 3 months ago, # ^ |   0 Just open the list "standings", click on anyone's solution and be happy (you'll very soon find the clear to you solution).
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 you can use xi + d , xi — d for i = 1..n without overlappingxi + d must be < x[i+1] so it is goodjust you have to find if the space between tow xi is fitable
•  » » 3 months ago, # ^ |   0 int n,d; int a[200]; set < int > st; int main() { speed; cin >> n >> d; ff(i,1,n) cin >> a[i]; int ans = 2; // x1 - d , xn + d ff(i,1,n-1) { if(a[i]+d
 » 3 months ago, # | ← Rev. 2 →   +6 Problem F is very similar to COCI 2017/18 Round 2, last problem (link to the codeforces blog). The difference is that that there we want the number of ranges with gcd(A[L;R]) = 1, but the same idea will pass (you can look at the comments). So if anyone doesn't want to wait the editorial, he can check it out. Link to my code for that problem.
 » 3 months ago, # | ← Rev. 2 →   0 Am I the only one who thought about Codeforces Round #439 (Div. 2) and people, who solved B and C but did't solve A which was even more funny than today's B?
•  » » 3 months ago, # ^ |   0 I was stuck on A as well. I was really sad that I couldn't even solve A in a contest was thinking of leaving the contest but then saw B and faith were restored. I solved A with a time penalty of 110 (around) points and 150 points attempt penalty.
 » 3 months ago, # |   +8 Your crafting.oj.uz ratings are updated!
 » 3 months ago, # |   0 I think pC should replace pA and there should be another pC which reduces the gap between pC and pD. I don't know why contestant are calling pB troll problem because it was nice simple problem. I don't like pA and pC(as C). Also this was my first contest and I learned that "Implementation is a part of competition and it should be a part of preparation".
•  » » 3 months ago, # ^ |   0 B was a troll problem because of the answer which wasn't any way dependent on input. There was no need of input of l,r segments, the only n was sufficient to generate the pattern. Even if you didn't know that answer should be alternate 0 and 1, you could prove it mathematically to maximize to the fact that in any segment (even number of elements), there should be the equal number of two type of roses for the function to yield the maximum result.
•  » » » 3 months ago, # ^ |   0 It's a competition. I bet that many people have wasted time thinking about l & r. Also it requires finding maximum value attained by downward parabola which I think is okay for Div2 pB .
•  » » » » 3 months ago, # ^ |   0 The problem was tricky. Very very simple differential calculus is required for mathematical proof. After thinking of approach, the main time wasted was checking under various test cases if approach really is correct or not.
•  » » » » » 3 months ago, # ^ |   0 Why check for various test case if you have proof
•  » » » » » » 3 months ago, # ^ |   0 Could not believe that the answer could be this simple.
 » 3 months ago, # |   0 I was able to solve problems A and B but not the problem C. I know it is quite easy. But I somehow couldn't explain myself the logic in my mind. All I could think was of a prefix array will the ith index in it denoting the no. of the unique elements to the left of it in the array. Can someone explain the solution to C? It can be short too, I kind of have a rough idea after looking at the codes of other participants who used sets and maps for the same.
•  » » 3 months ago, # ^ |   0 You probably have guessed it right. I first created a prefix array which gives me the unique elements to the right of an index i. Then we iterated from i=0 to i=n-1, and for each unique element I added the prefix sum from it. Here's the pseudo: for(i=0 to n-1) { if(!marked[a[i]]){ ans+=pre[i] marked[a[i]]=true } } 
•  » » » 3 months ago, # ^ |   0 i too figured it but unable to implement it .......it sucks if this happens
 » 3 months ago, # | ← Rev. 2 →   0 I face a problem with Pypy on CF. I got RE with exit code is 13131313 if I import random library. The same code is AC with pythonhttp://codeforces.com/contest/1004/submission/40007659 — AC with pypy3. http://codeforces.com/contest/1004/submission/40007677 — RE with pypy3 because of import random. Exit code is 13131313 http://codeforces.com/contest/1004/submission/40018157 — AC with python3, (has import random also).Any help?
 » 3 months ago, # |   +1 After 2 years of python I forgot that I have to use long long instead of long. :-D good bye good rating.
 » 3 months ago, # |   0 Editorials are not here....
•  » » 3 months ago, # ^ |   +12 Here it is. editorial
•  » » » 3 months ago, # ^ |   0 thanks..
 » 3 months ago, # |   0 guys can anyone help me with problem C because in that problem i m getting a TLE but still after going through the editorial also i m unable to figure it out...........PLz help
•  » » 3 months ago, # ^ |   0 Iterate from last element. Keep track of number of different elements before current element and also make sure not to count pairs (*,y) multiple times you can do it having a boolean array
•  » » 3 months ago, # ^ | ← Rev. 3 →   0 The complexity of your solution is (1e5*1e5).It will give you TLE.
•  » » » 3 months ago, # ^ |   0 can u let me know a simple way of doing that becoz i m new so dont know much tricks to over come these issues
•  » » » » 3 months ago, # ^ |   0 Okay, The first thing you have to do , "Learn how to calculate time complexity". The complexity is more important than the solution. Watch it on YouTube or google it .
 » 3 months ago, # |   +6 101010101 = LOLOLOLOL
•  » » 3 months ago, # ^ |   -11 FKFKFKFKFKFKF
 » 3 months ago, # |   +4 Editorial here...
 » 3 months ago, # |   0 Can anyone tell me what is wrong with this submission? http://codeforces.com/contest/1004/submission/40022548
 » 3 months ago, # |   -13 The comment is hidden because of too negative feedback, click here to view it
 » 3 months ago, # |   0 Problem A, in the second sample test case, why aren't cities with coordinates 14 and 15 part of the cities Sonya can build hotels on?
•  » » 3 months ago, # ^ | ← Rev. 2 →   0 distance of 14 from 11 is 3, and distance of 15 from 18 is 3, but minimum distance should be 2.