Vovuh's blog

By Vovuh, history, 15 months ago, translation, ,

<copy-pasted-part>

Hello!

Codeforces Round #506 (Div. 3) will start at Aug/24/2018 17:50 (Moscow time). You will be offered 6 or 7 problems with expected difficulties to compose an interesting competition for participants with ratings up to 1600. Probably, participants from the first division will not be at all interested by this problems. And for 1600-1899 the problems will be too easy. However, all of you who wish to take part and have rating 1600 or higher, can register for the round unofficially.

The round will be hosted by rules of educational rounds (extended ACM-ICPC). Thus, during the round, solutions will be judged on preliminary tests, and after the round it will be a 12-hour phase of open hacks. I tried to make strong tests — just like you will be upset if many solutions fail after the contest is over.

You will be given 6 or 7 problems and 2 hours to solve them.

Note that the penalty for the wrong submission in this round (and the following Div. 3 rounds) is 10 minutes.

Remember that only the trusted participants of the third division will be included in the official standings table. As it is written by link, this is a compulsory measure for combating unsporting behavior. To qualify as a trusted participants of the third division, you must:

• take part in at least two rated rounds (and solve at least one problem in each of them),
• do not have a point of 1900 or higher in the rating.

Regardless of whether you are a trusted participant of the third division or not, if your rating is less than 1600, then the round will be rated for you.

Thanks to MikeMirzayanov for the platform, help with ideas for problems and for coordination of my work. Thanks to my good friends Mikhail PikMike Piklyaev, Maksim Ne0n25 Mescheryakov and Ivan BledDest Androsov for help in round preparation and testing the round.

Good luck!

I also would like to say that participants who will submit wrong solutions on purpose and hack them afterwards (example) will not be shown in the hacking leaders table.

</copy-pasted-part>

UPD1:

Congratulations to the winners:

Rank Competitor Problems Solved Penalty
1 problem_destroyer420 5 209
2 syh0313 5 225
3 VinceJudge0 5 230
4 kredo 5 234
5 EctoPlasma 5 241

Congratulations to the best hackers:

Rank Competitor Hack Count
1 halyavin 506:-92
2 antguz 121:-20
3 YangYunFei 50:-11
4 UselessChallenger 41:-1
5 zdw1999 41:-2
6 applese 40

1217 successful hacks and 926 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem Competitor Penalty
A i_f_y_m 0:03
B kredo 0:03
C kredo 0:13
D NT_Master 0:17
E syh0313 0:43
F iamunstoppabIe 0:19

UPD2: Editorial is published.

• +126

 » 15 months ago, # |   +10 just have strong pretests because then only hacks make sense
 » 15 months ago, # |   0 Will be original cf round on September 1st?
 » 15 months ago, # |   0 How are you going to detect the people who hack solutions having some if statement to remove them from standings table? Is there some algorithm?
•  » » 15 months ago, # ^ |   +16 I'll try to check all peoples, who will hack their own submissions, manually and check if in their code will appear parts like if (n == 1234) return 1; and similar.
•  » » » 15 months ago, # ^ |   0 Why is it even allowed for people to hack their own submissions?
•  » » » » 15 months ago, # ^ |   +9 Not all hacks of their own code are such as I say above. Many hacks of your code can be useful because there are can be not complete testsets in the contest. But hacks of kind if (n == "blablabla") return 1; are useless and make no sense.
•  » » » » » 15 months ago, # ^ |   0 Few contests back, there was a comment mentioning a person hacking someone else in the same room but both the accounts probably were being used by the same person. This way it won't show up in the list of people who hack themselves but this practice needs to be curbed.
•  » » » » » » 15 months ago, # ^ |   0 We are trying to undermine all such cases but it is very hard to do that without any mistakes or omissions.
•  » » » » » » 15 months ago, # ^ |   -18 哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
•  » » » » » 15 months ago, # ^ |   0 Ah, so you build a tricky/big case and let codeforces check the correct answer for you. Never thought about it, makes sense!
•  » » » 15 months ago, # ^ |   +1 People do like this mostly for dropping their ratings purposely. That is repulsive addiction。
 » 15 months ago, # |   +60
•  » » 15 months ago, # ^ |   +41
•  » » » 15 months ago, # ^ |   +17
•  » » » 15 months ago, # ^ | ← Rev. 4 →   +7 Successful Hacking Attempt …
 » 15 months ago, # |   -33 move contest time 3 hours later .. this time is not good
•  » » 15 months ago, # ^ |   +4 Why did you change your profile picture?
 » 15 months ago, # | ← Rev. 2 →   -66 Well Well Well
•  » » 15 months ago, # ^ |   0 Yes,rated for participants with ratings up to 1600
•  » » 15 months ago, # ^ |   0 Is it communist?
•  » » 15 months ago, # ^ |   0
 » 15 months ago, # |   -26 Warning, this is a joke, don't feel bad if you are div 3.
•  » » 15 months ago, # ^ |   +35 yeah didn't even felt the joke.
•  » » » 15 months ago, # ^ |   +2 yeah, it seems is not funny, I just wanted to hide in a subtle way a sad truth
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   +5 don't underestimate anyone,who knows an extremely low rated div.3 guy is doing some other wonders.
•  » » 15 months ago, # ^ |   +56
•  » » 15 months ago, # ^ |   0 Too real
•  » » 15 months ago, # ^ |   0 I am div -1 ;)
 » 15 months ago, # |   +35 DIV3 ROUND! It's time to challenge your coding skill together with coding speed!
 » 15 months ago, # |   0
 » 15 months ago, # |   +9 coming expert , i wish .
 » 15 months ago, # |   -29
•  » » 15 months ago, # ^ |   +5 Welcome to future,your rank in 504 will be 2942.
•  » » » 15 months ago, # ^ |   0 Ya, they have beaten me up
•  » » 15 months ago, # ^ |   0 Same here
 » 15 months ago, # |   -18 Hope there will be strong pretest. Don't want the codeforces changes to the hackforces. Thank you very much.
 » 15 months ago, # |   0 Hope that I will become expert after this contest. :)
•  » » 15 months ago, # ^ |   0 gl hf
 » 15 months ago, # |   +27 Why the 15 minute delay ?
•  » » 15 months ago, # ^ |   +11 standartno
•  » » 15 months ago, # ^ |   0 its good but its bad
•  » » 15 months ago, # ^ |   0 So that no of registrations crosses 9k mark...
•  » » 15 months ago, # ^ |   0 For few seconds, the website crashed as well. Maybe the delay was to fix the issue
 » 15 months ago, # | ← Rev. 2 →   0 Delay :(
 » 15 months ago, # | ← Rev. 2 →   -12 WHY 15 MINUTES DELAY?
 » 15 months ago, # | ← Rev. 2 →   -10 typedef Codeforces_Rounds 15_Mins_Delay
 » 15 months ago, # |   -6 15 minutes delay -_-
 » 15 months ago, # |   +39 The Wait!!!
 » 15 months ago, # |   +13 00:00:15 -> F5 -> 00:15:00
 » 15 months ago, # |   +33 Someone please make a Codeforces Delay Predictor -_-
 » 15 months ago, # |   +75
 » 15 months ago, # |   +3 how to solve A?
•  » » 15 months ago, # ^ |   +43 To solve A: 1. Wait for 15 minutes. -_- 2. Open contest page. 3. See question A. 4. Solve.
•  » » » 15 months ago, # ^ |   -18 Nice
•  » » » 15 months ago, # ^ |   0 Yeah, it works, 10q
•  » » » » 15 months ago, # ^ |   0 Haha, LOL. Yep, just Codeforces thing :p
•  » » 15 months ago, # ^ | ← Rev. 2 →   0
•  » » » 15 months ago, # ^ |   0 are you genius evil hacker?
 » 15 months ago, # | ← Rev. 2 →   -8 Before:00:00:15 before start, Now:00:08:00 before start, Will-be:This round will be unrated :)(JUST JOKING)
 » 15 months ago, # |   0 Will participation cross 8500 :)
 » 15 months ago, # |   -17 Hackforces, Delayforces, Memeforces, Mathforces, who's next??
•  » » 15 months ago, # ^ |   +2 Unratedforces
•  » » 15 months ago, # ^ |   +23 dragonforces
•  » » 15 months ago, # ^ |   +45 Wrongproblemorderforces
 » 15 months ago, # |   +7
 » 15 months ago, # |   +24 Is it Div 3 contest? I think it's too difficult
 » 15 months ago, # | ← Rev. 2 →   +4 .......ANNOUNCE.....You may do in such way, we'll understand
 » 15 months ago, # | ← Rev. 2 →   +1 I am getting wrong answer on test 1 problem A and can't even figure out why. :'( edit: figured
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 I find B easier than A so tried B, thought have a perfect solution but only getting wrong answer. Div 3 contests are always something special. Edit: Finally solved and that's first for me in a div 3 contest, even I'm kinda new here :P
 » 15 months ago, # |   0 How to solve problem D ?
•  » » 15 months ago, # ^ |   0 I didn't actually give it a go, but I believe you should calculate ((V[i] * 10 ^ j) % K) for every i and j and then, for each j, build a frequency array / map of these such values. After that, it's easy to see that for every V[i] the amount of elements you can pair it up with is freq[j][K — (v[i] % K)].
•  » » » 15 months ago, # ^ |   0
•  » » » » 15 months ago, # ^ |   0 It was hacked. You should let your code run faster. 42080262
•  » » » » » 15 months ago, # ^ |   0 This too!
 » 15 months ago, # |   +12 this is not div.3 contest
•  » » 15 months ago, # ^ |   -58 i hate vovuh
•  » » » 15 months ago, # ^ |   +45 This is sad :(
•  » » » » 15 months ago, # ^ |   +13 Although I found the problems harder than the last div3 contest, I still enjoyed it! At the end of the day, I'm sure I'll come out of this round knowing more than I did before(once the editorials are out of course xD)So a relatively difficult div 3 contest(compared to past div 3 contests) isn't necessarily a bad thing :)
•  » » » » 15 months ago, # ^ |   +13 Vovuh why not increase the time limit to 2.5 hours because i think most probably div3 contests have a large fraction of people who always thinks that if i could have given 15 more minutes i could have definitely done one more problem(i m one of them).. i mean this just boosts up the confidence and belief.. this suggestion may be immature but i feels at least 2.5 hours should be given for 6 problems to do justice with the contest,those who solves first will have better rank whether the time is 2 hours or 3 hours.. although these contests are awesome always if one try to solve problems before or after contests .
•  » » » » 15 months ago, # ^ | ← Rev. 3 →   -19 I don,t know why Mike trusts so much on Vovuh for div-3 he prepares really bad div 3 rounds
 » 15 months ago, # |   0 I try to solve Problem B with a solution of upper_bound(a[i]*2) but fails. How to solve this?
•  » » 15 months ago, # ^ |   0 You miss read the statement.
•  » » » 15 months ago, # ^ |   0 What a foolish mistake. now i understand. It just need to compare a[i] and a[i+1]. Thanks!
•  » » 15 months ago, # ^ |   0 I solved it with sliding window
•  » » » 15 months ago, # ^ |   0 Even I tried the same but got wrong i case 4 int ans=1,i,j=0; for(i=1;i 2*a[j]) j++; ans=max(ans,i-j+1); } Could not find what is missing. Please help. Thanks
•  » » » » 15 months ago, # ^ |   0 My codeint res=1,sum=1,aux=0; for (int i=0;i=arr[j]) { res= max(res,sum); aux=j;} else { i=j-1; sum=1; break; } } if(aux==n-1) break; } 
•  » » » » » 15 months ago, # ^ |   0 Thanks got it,I misunderstood the problem
•  » » » » » 15 months ago, # ^ |   0 I think the time complexity of your code is not right. You can use double-end queue (deque). Like this. 42036114
 » 15 months ago, # |   0 In problem F, what does this mean : "all tiles of at least one color would also form a rectangle." ?
•  » » 15 months ago, # ^ |   +2 At least one color must form a rectangle i.e if you remove red, blue must form a rectangle or if you remove blue, red must form a rectangle
•  » » » 15 months ago, # ^ |   0 Thank you.
•  » » 12 months ago, # ^ |   0 I also was not able to understand the problem statement because of this. According to Firastic, the intended meaning is quite different to what they wrote.
 » 15 months ago, # |   +1 What is pretest 4 for B?
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 A pretest of this type: your solution should be based on the statement and not the samples.
•  » » » 15 months ago, # ^ | ← Rev. 2 →   +4 Got it, but that was still a shitty statement. Could be framed better.
 » 15 months ago, # | ← Rev. 2 →   0 Welcome to Codeforces Round #506(Div.2)Edit: only A isnt a Div.3 A problem.. B is easy but the trap in reading the statement is just so unexpected other problems are Div.3 problems
 » 15 months ago, # | ← Rev. 2 →   -29 pretest 6 in A. I want to know that sh*t and yea, i still hate vovuh and his friends who always writes shity contests. (I'm not afraid downvotes)
•  » » 15 months ago, # ^ |   0 try this input:6 2abababoutput should be: abababab
•  » » » 15 months ago, # ^ |   0 ohhhhh, got it, by the way thanks
•  » » » » 15 months ago, # ^ |   0 Why do his contests then?
 » 15 months ago, # |   0 How to handle the case in D when 2 | k or 5 | k. Is there an easy way to do this than to calculate modulus for all possible factors of k which still aren't coprime to 2 or 5
•  » » 15 months ago, # ^ |   0 Your approach seems not to be on the correct path. You may want to think it differently.
 » 15 months ago, # |   0 What's pretest 7 on C? I can't figure out where I screwed up.
•  » » 15 months ago, # ^ | ← Rev. 3 →   +6 My guess is that it is something like this: 300000 1 100000000 2 100000001 3 100000002 ... 300000 100299999 
 » 15 months ago, # |   -7 There should not be hard deadline time to end the contest, atleast 20-30 seconds extra should be given, given the initial load on the system. I missed the D by 1 second today.
•  » » 15 months ago, # ^ |   +1 Same here, I putted the code and clicked submit and there was almost 10 seconds, but it wasn't submitted :(.
•  » » 15 months ago, # ^ |   +6 Then that hard deadline should have a hard deadline. xD
•  » » » 15 months ago, # ^ |   0 Yeah, no.
 » 15 months ago, # |   -26 Honestly, Its seems like Div-1 to me.
 » 15 months ago, # | ← Rev. 2 →   +5 I solved C with Segment Tree, is there other topics solve this problem? because I feel that it is easier than SegTree when I saw someone solved it quickly.
•  » » 15 months ago, # ^ |   +10 only the top 2 numbers matter.  sort(l , l+n); sort(r, r+n); reverse(l, l+n); int ans = r[0] - l[0]; if(!notin(l[0], r[0])){ ans = max(ans, r[1] - l[0]); ans = max(ans, r[0] - l[1]); } else ans = max(ans, r[1] - l[1]); cout << max(0,ans) << endl; 
•  » » » 15 months ago, # ^ |   0 Thanks, I will see your submission for more details.
•  » » » » 15 months ago, # ^ |   +4 Initial idea is that if you consider all the segments, the intersection is formed by lowest right end and highest left end.Now, if you want to improve your intersection, you would want to either: Extend the right end of some segment or Extend the left end of some segment. Now think about which one would you choose.
•  » » » » » 15 months ago, # ^ |   +1 Yeah I got it now, thank you very much :D
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 Easy O(n log n) with multiset 42096347
•  » » » 15 months ago, # ^ |   0 Good idea :D, thanks for sharing it!
 » 15 months ago, # | ← Rev. 3 →   0 can someone plz tell me what is wrong in this approach for E? A node ( > depth 2) may be reached through child or parent who has a direct edge or there is a direct edge to this. SO, a) if i want to reach this node from parent, then for each child there must be a direct edge or any of their children must have a direct edge. b) if i want to reach this node from children, any one can have a direct edge and others can have direct edge or their children can have a direct edge. c) if i have a direct edge to this node, then i can take the min( a, b, c);Can someone plz tell me what is wrong here, here is the link, https://ide.geeksforgeeks.org/Nn0MdojmeD
 » 15 months ago, # | ← Rev. 2 →   +2 Will an O(10 * n * logn) solution pass systests for problem D? Link
•  » » 15 months ago, # ^ |   0 Yes, it will. Mine did.
•  » » » 15 months ago, # ^ |   0 42061028 will this pass
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 I don't understand but it already says Accepted.edit: oh you are worried about hacking phase, it wont exceed time limit, that case is already there.
•  » » » » » 15 months ago, # ^ | ← Rev. 2 →   0 hmmm.what's that case well
 » 15 months ago, # | ← Rev. 2 →   0 For problem E: We should start processing leafs and add to the result the number of their parents only if those parents distance from 1 is > 1 (level 2 or further)... Remove current leafs, their parents and the adjacents to their parents from the graph.. Repeat the process on the new graph.Is this approach correct ? What is a better one ?
 » 15 months ago, # |   0 Whats pretest 5 in A? Just can't figure it out :(
•  » » 15 months ago, # ^ |   0 try this input:6 2abababoutput should be: abababab
 » 15 months ago, # |   +2 Can someone tell me about solution for problem E ?
•  » » 15 months ago, # ^ |   +1 DP d(i, j): i represent the index of the nodes, j represent the depth of node i; http://codeforces.com/contest/1029/submission/42054107
•  » » 15 months ago, # ^ |   0 The complexity is O(n)
•  » » 15 months ago, # ^ |   0 Root the tree at 1. Sort the nodes by their depth in descending order (so we start with leaves). Make an array to store if we can reach a node in <= 2 steps. Loop through the nodes by depth and if not marked create a connection to the parent of that node and mark all the neighbors of the parent in the array.
•  » » 15 months ago, # ^ |   +1 I was trying it with dp, though couldn't complete the code within contest. My idea was to consider states if there is an edge from 1 to v or not. if there is an edge from 1 to v, then there can be edge from 1 to childrens of v or not. if there is no edge from 1 to v, then there must be an edge from 1 to atleast one of child of v
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 I have also used the same approach: http://codeforces.com/contest/1029/submission/42130661 The function reqd() does the main job. But I'm getting wrong answer on test case 8.The function prepareChild() turns our indirected tree to directed tree using BFS.Can you tell what's wrong here?
 » 15 months ago, # | ← Rev. 2 →   +5 Seems like problemsetters have been missing how problem A should be :D for the last few contests.
 » 15 months ago, # |   +2 Am I the only one who misread the problem statement of B? I guess no.
 » 15 months ago, # |   0 problem F, finished in 10 mins after contest :((
•  » » 15 months ago, # ^ |   +3 during the contest I coded it in 8 minutes but I got WA37 did you get the problem in this test?
•  » » » 15 months ago, # ^ |   0 the same problem, in the last 5 minutes of the contest, I knew my mistake but i did not have enough time to code :|
 » 15 months ago, # |   0 How to Solve C ?
•  » » 15 months ago, # ^ |   0 I tried to find maximum of left interval and minimum of right interval. Let max1=difference of 2. Then remove the row in which left array max is there and find max2. Then finally remove only the row in which right array min is there, max3. The answer is max(max1,max2,max3,0)
•  » » 15 months ago, # ^ | ← Rev. 3 →   0 The intersection length of n segments is min R - max L (invalid if it's negative), so just ignore each segment and evaluate length, i used multiset to insert/remove in O(log n). I'm doing this for n segments, so the total complexity is O(n log n).Code: 42096347
 » 15 months ago, # |   0 what's wrong with 37'th in problem F ?
•  » » 15 months ago, # ^ |   0 Small infinity(got wa on 37 too).
•  » » 15 months ago, # ^ |   0 2 large prime numbers, so only rectangle with side 2 will pass
•  » » » 15 months ago, # ^ |   0 sorry can you explain more?
•  » » 15 months ago, # ^ |   0 the area (a + b) can only be divided by 2, some people have the answer 6179835302 because they devide it by 64728, but we can't color the rectangle like this because " all tiles of at least one color would also form a rectangle ". The solution is check that are there any divisor of a (or b) (called i) that i <= (divisor of S (called div)) and a/i <= (S / div) so we can have a rectangle with size div * (S / div).my code : https://ideone.com/3bFclD
 » 15 months ago, # |   0 good contest.But I got ac to C after 10 minutes after the contest is finished
 » 15 months ago, # |   0 Nice contest : )
 » 15 months ago, # |   +3 for me the statement on b,c are very confused after explanation b become clear and I'm solve it, c after contest solve it its easy but not clear with this statements.
 » 15 months ago, # |   +1 Is it possible to share ideas of hacks with other people before the end of the hack phase? Does it violate the rules?
 » 15 months ago, # |   +4 Honestly, when I saw problem A, I thought for a second if it is really Div 3 (and I haven't passed A). It was quite good, except they were a bit too hard for newbies (like me), and frankly some problems were more suitable for Div 2, or even Div 1 instead. Still, I appreciate the hard work of today's contributors for thinking up the problems!
 » 15 months ago, # |   +1 is it a rated contest or not ? also i can't understand the General announcement, which say (We will publish separate standings for trusted participants after the contest.):) :) :)
 » 15 months ago, # |   0 I wish I could code this fast XD. Parallel Programming :P
•  » » 15 months ago, # ^ |   -9
•  » » 15 months ago, # ^ |   +1 Why his submissions are not showing after testing?
 » 15 months ago, # |   0 seems like another halyavin day , nearly 450 hacks . wow again .
•  » » 15 months ago, # ^ |   0 I can't comprehend how do you even hack. There are too many solutions and most of them are fully correct. Can somebody explain, please?
•  » » » 15 months ago, # ^ |   0 He might have a self created program which runs multiple codes at a same time or maybe downloads all the codes of the competitors . maybe , maybe not .
•  » » 15 months ago, # ^ |   0 It seems he is the one brought done the submissions of D for ~640 to ~150
 » 15 months ago, # |   +96
•  » » 15 months ago, # ^ | ← Rev. 3 →   +2 lol，halyavin is really good at hacking，I have been hacked by him for many times. But I maintain it also help me develop my skills，because the probability I will be hacked decreased more now at least.
•  » » » 15 months ago, # ^ |   0 can you please explain your code for E?
•  » » » » 15 months ago, # ^ |   +1 Firstly, we get a tree rooted by 1. We get dep[i] to express the depth of i in the initial tree, and let's call a vertex is right if the distance to 1 equal or less than 2. Obviously, if a vertex i with dep[i] <= 2, then the vertex is right. Our goal is to make all the vertex right. Consider we link 1 and a vertex i, it makes all the vertexs which are adjcent to i right. So in my solution, we first sort all the vertex in the decreasing order of dep[], and consider them one by one. If we find a vertex i is not right yet, then we link 1 and fa[i], which fa[i] is the father of i in the initial tree, and it will make all the vertexs which are adjacent to fa[i] right. It can be proof that in this way we use the least steps. XD
•  » » » » » 15 months ago, # ^ |   0 why do we choose the vertex with largest depth first?
•  » » » » » » 15 months ago, # ^ |   0 Because we have to deal with it, if we don't solve it this time, we must solve it next time. And solve it from down to up do not influent others, because all the vertex in this subtree are right.
•  » » » » » » » 15 months ago, # ^ |   0 thanks a lot!
•  » » 15 months ago, # ^ |   0 Can I have the original picture plz?
 » 15 months ago, # |   0 Did anyone solve B using dp and implicit segment tree? I guess it's an overkill, but to me it seemed better than to guess that the solution is always a continuous segment.
•  » » 15 months ago, # ^ |   0 I guess that this solution would be the best if the sequence was not in increasing order.
•  » » 15 months ago, # ^ |   0 It's just a cumulative sum problem!
•  » » 15 months ago, # ^ |   0 You can try to prove it during the contest. Just imagine you have already some subset, with the last element at index i (the array is sorted, and all of the elements with indexes > i are bigger). Now you want to try to add another element to this subset, suppose you added element j (j > i+1). Now you can see, that if element a_[j] <= a_[i]*2, the same applies to other elements in an interval [i+1, j-1] and it's always worth it to take smaller element. But why? Consider x as the smallest integer in the subset we consider at the moment. It's easy to see we want to minimize the largest integer in our subset (lets name it y), so 2*x >= y. This strategy applies to every element we consider in our subset — concluding — our subset will always be contiguous (if the array is sorted). Please correct me if I made some logical mistakes.
 » 15 months ago, # | ← Rev. 2 →   0 in problem B 2 1 2how is the answer 2 ?i knew that the statement contained <= but i thought that it is < how isn't there any pretest to check this ?
 » 15 months ago, # | ← Rev. 3 →   +1 Just curious, how could someone (or to be precise, antguz) confidently hack my O(10 * n * log(n)) solution of problem D to successfully give a TLE verdict?My hacked solution: 42049909My re-submitted one (with some slight optimizations, still TLE on other similar tests, which gave the conclusion that my solution ran at somewhere around 2.5-3s): 42071241
•  » » 15 months ago, # ^ |   +3 I had the very same issue as you so I thought of helping. TLE will go if you use unordered_map. Link to your submitted solution.
•  » » » 15 months ago, # ^ |   0 sigh Ah yes, unordered_map... Thanks! :DP/s: Still seeing that got TLE is insanely weird :-P
•  » » 15 months ago, # ^ |   +8 I think the issue is not in usage of map instead of unordered_map, but it is in that you used the operator [] when you wanted to add values to the result.Instead, you should check if a key you want to add its value was already existed in the map by the member function count(), and if yes, then add the value of that key to the result.Because when you use [], if the key in [] is not existed yet, this operator will create it, so the size of the map will increase by one, and so on. So, the time needed to access the map will also increase with the increasing of its size, thus you will get TLE.Check my submission for more details.
•  » » » 15 months ago, # ^ |   +3 Well, just as I was discussing with one of my friends about this exact issue.Yeah, I was critically careless in that, thinking O(10 * N * log(10 * N)) will do no harm. I was stupid :-PGuess this should be a huge lesson for me from now on. Thanks! :D
•  » » » 15 months ago, # ^ |   +3 Thank you very much!
 » 15 months ago, # |   0 Can anyone please point out why my code is giving TLE for problem D? I have tried all the optimisations I could think of at my level. It would be really helpful if someone can help me out here. Thanks in advance !!
•  » » 15 months ago, # ^ |   +5 use unordered_map
•  » » » 15 months ago, # ^ |   0 Thanks a lot. It worked
•  » » 15 months ago, # ^ |   +1 http://codeforces.com/blog/entry/61399?#comment-453807 . Hopefully this comment of mine helps you to get an AC by using map only.
 » 15 months ago, # | ← Rev. 5 →   0 Are there any better solution in problem B? I use dp and RMQ to solve this problem, but I think it's too complex for the problem B in div 3 contest :((I use F[] with the meaning that F[i] is the answer ending at i. I use lower_bound to find the minimum value that more or equal A[i] / 2 (called j), than find the maximum value of F from j to i — 1.P/s : If the array isn't in increasing order, what should we do? Edit: If the problem like this : find the maximum length of a subsequence ( by delete some elements ) (like LIS) but a[i] <= a[i-1] * 2 in this subsequen. what will we do?eg:Input n = 3 array[] = {2, 1, 4}Output 2 ( 1 and 4 )
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 You can traverse greedily in O(n): find the longest increasing subset that the criterion aij + 1 ≤ aij * 2 holds true.So, of course, if the array isn't sorted yet, we can just sort it beforehand — nothing special.
•  » » » 15 months ago, # ^ |   0 Thank you.If the problem like this : find the maximum length of a subsequence ( by delete some elements ) (like LIS) but a[i] <= a[i-1] * 2 in this subsequen. what will we do?eg: Input n = 3 array[] = {2, 1, 4}Output 2 ( 1 and 4 )
•  » » 15 months ago, # ^ |   0 Excluding the last element (i.e., the biggest), you can just calculate the length of the largest interval I = [L,R) such that I[R-1] <= 2 * I[R-2] holds.So L starts at 0, R at L+1, keep increasing R until the property I[R] <= 2 * I[R-1] is false. Then reset L = R, and repeat the process until R >= N. After doing that, the answer is the max R-L difference you've found in this process. There is one corner case: N = 1.
•  » » » 15 months ago, # ^ |   0 Thank you.
 » 15 months ago, # |   +1 Freakin' A Again >(
 » 15 months ago, # |   0 In problem D, using unordered_map gives TLE while submission with map gets accepted. I can't figure out why.http://codeforces.com/contest/1029/submission/42063201 (same code with unoedered map)
•  » » 15 months ago, # ^ |   +5 Some special data can make the complexity of unordered_map become O(n).(like test 64. I used pb_ds and got accepted after the contest. :P
•  » » » 15 months ago, # ^ |   0 knew this thing but ignored it don't know why -_-
•  » » 15 months ago, # ^ |   +1 42061028 this got hacked(map) -> tle verdict on hacking 42073938 this got tle at test 66 unoredered mapany reasons?
•  » » 15 months ago, # ^ |   +6 Unordered_map is implemented using hash table. So due to collisions in the worst case it can be O(n) for accessing an element. But map guarantees O(logn) for access.
 » 15 months ago, # |   0 CodeForces is the worst. Solution 1 Solution 2 Both solutions are the same. So during system testing, my correct solution fails only because of the load on CF server, which is basically CF's fault. So now I've to pay for it to settle for a worse rank.And I know even tagging MikeMirzayanov won't do anything because these kinds of crap has happened before and nothing was done.
•  » » 15 months ago, # ^ |   +24 Your solution was already borderline. Also, time is actually calculated by the no of clock cycles your solution takes to finish execution, and not wall time, so I don't think it has anything to do with server load. +-100ms in similar code execution can be expected
•  » » » 15 months ago, # ^ | ← Rev. 2 →   0 Yes I know it was borderline. It had passed test 7 in 2.8 s during the contest. But I think it's the server load only because I've read more such cases in a few contests held earlier and my solution to D also took more time to execute than it took during the contest.In general I have observed that borderline solutions fail only during system testing leading me to believe that load during system testing is the only reason, because otherwise they still pass.
 » 15 months ago, # |   +4 When will ratings get updated?
•  » » 15 months ago, # ^ |   +4 Finally Blue Yaaay!!!!!!
 » 15 months ago, # | ← Rev. 5 →   +1 I don't know why this submission for problem C 42040684 got hacked and then I again made the submission 42076792 with the same code and it passes all the tests, this seems to be a serious issue, as its the fault of the system which gives different execution time for the same solutions and unexpected time penalties. I think the hacked test case is the last one #71 ..Plz have a look at it.....
 » 15 months ago, # |   +1 Was the time limit too strict for problem D?42055423 Uses unordered_map and gets a TLE; 42076582 Uses cc_hash_table and gets an AC.Time complexity of both solutions is O(11*N).
•  » » 15 months ago, # ^ |   0 but both of them is log(n) data structure. So the Time complexity is O(11*N*log(N)).The unordered_map runs very very slowly.
•  » » 15 months ago, # ^ |   0 maybe there are better solutions...
•  » » » 15 months ago, # ^ |   0 Asymptotically the solution should get an AC, but as noble_ said unordered_map is very slow.https://codeforces.com/blog/entry/50626 I found this quite useful.
•  » » » » 15 months ago, # ^ |   0 after testing, I found that map or unordered_map will both get an ac, and unordered_map is slightly faster ..using long long in map will be slower
•  » » 15 months ago, # ^ |   0 tweaking load_factor of your hash table gets AC in 1044ms (42080080).
•  » » 15 months ago, # ^ |   0 Worst case time complexity of unordered_map is O(n).
•  » » 15 months ago, # ^ |   +3 AC with unordered_map ~997ms
 » 15 months ago, # |   +10 Problem D makes me very sad.I write a O(n * logn * 11) then get a TLE on test 28.I make some optimization to O(n * logn * 10) then AC.
•  » » 15 months ago, # ^ |   0 I got TLE on test 28 during the contest https://codeforces.com/contest/1029/submission/42058174Resubmitted exactly the same code and got AC (added 1 extra comment line). https://codeforces.com/contest/1029/submission/42078570on test 28, time is 1871ms
•  » » » 15 months ago, # ^ |   0 TLE on test 39 https://codeforces.com/contest/1029/submission/42079643 same code AC https://codeforces.com/contest/1029/submission/42079619 time 1653 ms on test 39Can someone explain why there are such big time differences?
•  » » » » 15 months ago, # ^ |   +5 If you check for C[j].count(needed) before taking its value, it gets AC in 350 ms. Even if it's zero, it creates the node for it in rb-tree anyway, thus increasing both memory usage and time.
 » 15 months ago, # |   0 When will ratings change?
 » 15 months ago, # |   0 How to solve problem D?
 » 15 months ago, # |   +1 when will the editorials be out??
 » 15 months ago, # |   +1 The same code for Problem D running on G++11 gives TLE on test 50, and with G++14 gets Accepted. I don't think such stiff time limits give fair assessment.
 » 15 months ago, # |   0 How to solve D? just an idea will be helpful
•  » » 15 months ago, # ^ |   0 Assume you are at a point ai and assume ai is l digits long. Then ai gives a solution when there exists aj in the array with the property 10l × aj + ai. has a remainder 0 when divided by k. With a bunch of precomputing you can find how many ajs have this property. However you have to be careful to remove the case when i = j. Also for the precomputing using 10 maps or unordered_maps for each of the powers of 10 you need seems to lead to TLE. You can avoid this issue by instead sorting and using a binary search.
•  » » » 15 months ago, # ^ |   0 got it, thanks for the idea
 » 15 months ago, # | ← Rev. 2 →   0 UPD: Sorry I got it, the answer of my idea is 2 + 2 * (a + b). So, never mind.In F, is there any statement in the statement denys us from coloring the tiles as a rectangle with dimensions (1 * (a + b)), so the answer will be a + b + 2?Because in the given samples (and all testcases I guess), the answer with my idea is always less than or equal to the answer from these samples.
 » 15 months ago, # | ← Rev. 3 →   +54 For Problem D — TLE issue People here find the Time limit strict ( even I did ) , but actually it isn't that strict. The only issue while using map which almost everyone is facing is : If u simply do ans += mark[digits][requiredmod]; then even though that required mod doesn't exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1), and if you do this n*10 times the size of the map would increase and therefore the time to search as wellSo what u need to do is first search whether that element is present in the map and then add it to the answer, as shown below :if ( mark[digits].find(requiredmod)!=mark[digits].end() ) ans += mark[digits][requiredmod];This is the only difference in my accepted and TLE solution.Accepted Solution : http://codeforces.com/contest/1029/submission/42081763 TLE Solution : http://codeforces.com/contest/1029/submission/42082128
•  » » 15 months ago, # ^ |   0 "then even though that required mod doesn't exist in the map, then also it will be added to that map and now the size of the map = (actualsize+1)". It is your assumption or document that says so ?
•  » » » 15 months ago, # ^ | ← Rev. 3 →   +12 No it is not my assumption. Very simply, you can compare the memory of both of my solutions. Why open the documentation when you can code... LOL. map < int,int > mark; mark[1] = 2; cout << mark.size() << endl; int val = mark[0]; cout << mark.size() << endl; Output :12
•  » » » » 15 months ago, # ^ |   0 Thank you, that's interesting !
•  » » » 15 months ago, # ^ |   +6
•  » » » 15 months ago, # ^ |   0 Tried everything and still got TLE on different tests. After that, I read your comment, changed that line, and got AC with 342 ms. Incredible :P
•  » » » » 15 months ago, # ^ |   0 Great ;p
•  » » » 15 months ago, # ^ |   0 It is true, whenever you wanna create a new element x in a map you can just doM[x];This is the same case, doingans += M[ x ][ y ];Will always create a new element [x][y] if it didn't exist.
•  » » 15 months ago, # ^ |   0 For me, changing unordered_map to map helped me solve the TLE issue.
 » 15 months ago, # | ← Rev. 2 →   +13 DP Solution for Problem EDP state : (node, cur, par) node -> The index of the nodecur ( 0 or 1 ) -> Whether the given node either has or is supplied with an extra edge connecting it to the root par ( 0 or 1 ) -> Whether the parent of the given node either has or is supplied with an extra edge connecting it to the root Now 3 cases arise : cur:1 -> sum over all children {min(solve(child,1,1) + 1, solve(child,0,1))}cur:0 par:1 -> In this case the current node has a path of length 2 to the root by going to its parent and then from parent to the root. sum over all children {min(solve(child,1,0) + 1, solve(child,0,0))}cur:0 par:0 -> This is the most important case. Main Point : This node doesn't have a path of length atmost 2 to the root, so it has to make use of ATLEAST 1 of its children* Case 1: Leaf node -> You need to make an edge straight from here to the root. ans =1Case 2: Internal node -> Select atleast one child from which you will make a direct edge to the root. Code for this : vector < pii > vec; int sum = 0,idx = 0; for ( auto child : adj[node] ) { vec.pb({solve(solve(child,1,0)+1,solve(child,0,0)}); sum += min(vec[idx].first,vec[idx].second);idx++; } int ans = INT_MAX; for ( auto child : vec ) ans = min(ans,sum+child.first-min(child.first,child.second); 
•  » » 15 months ago, # ^ |   0 can u help me with this i am not understanding why this approach will fail dp[i][0]- best ans of subtree rooted at i such that i don't have direct edge to 1 dp[i][1]- best ans of subtree rooted at i such that i have direct edge to 1 ans is sum of min(dp[j][0],dp[j][1]) j is child of 1 https://codeforces.com/contest/1029/submission/42097382
 » 15 months ago, # |   0 For E does greedy approach like this work? Take any leave. If its distance to root in the input tree is <=2 we are done for this leave. Else connect parent of this leave with the root and delete this parrent and all his sons and his father from the tree.
•  » » 15 months ago, # ^ |   0 yes it works, but you have to sort by dist first, check this
•  » » » 15 months ago, # ^ |   +1 U mean depth? That is obvious we need to take the deepest leave always.
 » 15 months ago, # |   +1 Could you please publish a tutorial for the contest !
 » 15 months ago, # |   +4 Can I get a tutorial for this contest?
 » 15 months ago, # | ← Rev. 4 →   0 Could you please publish the results, the best hackers and the tutorial?And we know, the best hacker is halyavin as usual.
 » 15 months ago, # |   +13 It's sad having problem E with all tests except samples n = 200000. Have WA8 and don't know how to debug)
•  » » 15 months ago, # ^ | ← Rev. 2 →   0 Why don't you attach your code? I think you were wrong while not interested if addition edge from 1 -> v then we could go from 1 -> v -> parent (v).
•  » » » 15 months ago, # ^ |   0 You're absolutely right. It's just about "aaarrrgghhh why I can't just copy failed test?"
 » 15 months ago, # |   +16 I think the ranklist has something wrong.Such as the participants Vincejudge0's solution for D was failed during the system test, but the ranklist shows that he/she solved 6 problems. Is this a bug?Vovuh Please check it. :D
•  » » 15 months ago, # ^ |   +15 Hope I fixed it now, sorry, there is a problem with Codeforces API, I don't know where is the bug. Thank you for your comment!
•  » » 15 months ago, # ^ |   +15 I agree.
•  » » » 15 months ago, # ^ |   +8 I disagree.
•  » » » » 15 months ago, # ^ |   +5 I agree.
•  » » » » » 15 months ago, # ^ |   +8 I disagree.
•  » » » 15 months ago, # ^ |   +11 Are you playing inclusion–exclusion principle？
•  » » 15 months ago, # ^ |   +18 I agree too.
 » 15 months ago, # |   0 42038360 He use “for(int i=1;i<=floor(sqrt(a)+0.5);i++)” .He got TLE on my computer because calculate sqrt() many times is much slower than calculate it at first. But codeforces maybe use -O2 -O3 or something and he Accepted. :(
 » 15 months ago, # |   0 Can someone tell me why I'm getting TLE in D? my submissionI read all the comments but can't figure it out.. :(
•  » » 15 months ago, # ^ |   0 Honestly i don't know, i tried playing with your code for a bit but i still got TLE. If it helps, my TLE on-contest submission used about 80k memory, and then it went down to about 10k with the Map.count(). Yours is still ~80k for some reason
•  » » » 15 months ago, # ^ |   0 Thanks. I think my code structure is the problem. Compare to editorial and accepted codes, I insert ten times more nodes.That might slow down map operations and maybe larger memory consumption itself can be a problem.
•  » » » » 15 months ago, # ^ | ← Rev. 2 →   0 If it helps you, i've solved it quite fast by using a single map:https://codeforces.com/contest/1029/submission/42099251But i'm pretty sure you should be able to solve it using a map for every amount of digits (in fact, it should be even faster).
 » 15 months ago, # | ← Rev. 2 →   0 Why does this TLE?Can't find the reason.....The time complexity should be O(n*log(10n)) (Correct me if I'm wrong) http://codeforces.com/contest/1029/submission/42107686
•  » » 15 months ago, # ^ | ← Rev. 3 →   +3 std::map is not O(1),and log10(n)=log2(n)*log10(2) so your code is O(nlog^2(n))
•  » » » 15 months ago, # ^ |   0 OH!Thanks
 » 15 months ago, # | ← Rev. 2 →   0 Sir , I think that you should change the limit exceed of Problem D, I got TLE on test31，but my algorithm is correct. Sorry for my poor english
•  » » 15 months ago, # ^ |   0 Here is my code : (https://codeforces.com/contest/1029/submission/42053492)
 » 15 months ago, # |   0 Hope that the contest page doesn't show "starting in 15 minutes" after 3 minutes