Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

HolkinPV's blog

By HolkinPV, 6 years ago, translation, ,

Good day)

Welcome to regular Codeforces round #199 for Div.2 participants. As always Div.1 participants can take part out of the competition.

The problems were prepared by authors Pavel Kholkin (HolkinPV) and Gerald Agapov (Gerald). Traditionally thanks to Michael Mirzayanov (MikeMirzayanov) for Codeforces and Polygon systems and Mary Belova (Delinur) for translating the problems.

UPD: Score distribution is standard500-1000-1500-2000-2500.

We wish everyone good luck, high rating and excellent mood)

UPD2: the contest is over, hope you enjoy it)

Congratulations to winners:

UPD3: the editorial is published here

• +86

 » 6 years ago, # | ← Rev. 2 →   +22 Thanks for the contest! But Why is the name of Author orange(Master) on the title and purple(Candidate Master) in the text?? Here Master↓ --------------------------------------- --------------------------------------- and here candidate master↓ --------------------------------------- ---------------------------------------
 » 6 years ago, # |   +11 some copy-paste) fixed
 » 6 years ago, # |   +8 You may want to warn everybody about unusual contest time :)
 » 6 years ago, # |   +1 Good Morning (:|
 » 6 years ago, # |   0 is this contest difficult? gonna to see the problems you prepared! and waiting for the score distribution now... hope everybody can enjoy this contest and get high rating!
 » 6 years ago, # |   +9 Sorry to ask, but is this a rule that there will never be an intersection between CF & TC contests?
•  » » 6 years ago, # ^ |   +6 This looks like a good reason...
 » 6 years ago, # |   +5 Good time for Chinese participants:)
•  » » 6 years ago, # ^ |   +5 But I'm sleepy... :(
•  » » 6 years ago, # ^ |   0 +1
 » 6 years ago, # |   +4 most of the solutions in problem C is wrong. check it: 11 21
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 test: 8 7 answer: 3
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 Very easy pretests in each problem...
•  » » » 6 years ago, # ^ |   +11 That's good for hacking ;-)
 » 6 years ago, # | ← Rev. 2 →   0 Can someone find the problem in following logic for A? There are only 3 possibilities: (1 2 4), (1 2 6) and (1 3 6). So I simply read the input find counts for numbers 1 to 7. Let say that combination 1 2 4 is there a times, 1 2 6 b times and last c times. From counts I can calculate a as number of 4s, c as number of 3s and b is number of 6s — c. At the end I calculated counts for used possibilities and checked against input, but got WA.edit: it failed, because I didn't checked that b is non-negative :-/
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 b is the number of 6s — number of 3sUPD: numer of 2s must be must be equal to 4s + (6s — 3s)
•  » » » 6 years ago, # ^ |   0 and while c is number of 3s it is the same...
•  » » 6 years ago, # ^ |   0 I did the same and got AC. Maybe your checks wasn't comprehensive enought.
•  » » 6 years ago, # ^ |   0 A is much simpler than that, the point is that only 1 can be set as the first number in every sequence 5 and 7 cant be in the sequence, you can pick 2 and 3 for the second number if you pick 3 you cant only chose 6 for the third and if you pick 2 you have 2 options, 4 or 6. so you simply check if there is any 5 or 7, and if the count of 2 and 3 equal the count of 1 and the count of 4 and 6, and...(if you want more pm me) good luck ;P
•  » » 6 years ago, # ^ |   0 I got AC too.maybe you forget some conditions.The number of "1" equals to n/3; a==number of "4";a+b+c==n/3;and a>=0,b>=0,c>=0.
 » 6 years ago, # |   0 some helps with C? i dont really get it.
•  » » 6 years ago, # ^ |   0 Consider example of r=8 and h=7. That's the case most solutions failed to answer correctly. You can put two spheres inside box and one more at the center of top semisphere.
•  » » » 6 years ago, # ^ |   0 pufff! how are we supposed to find that out?!
•  » » » » 6 years ago, # ^ |   0 why down rates? not every one here know that much of geometry!
•  » » » » » 6 years ago, # ^ |   0 :D you down rate this as well?!! hahahaha i have 40 downrates already, i dont care!! cows rock!
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +5 Geometry is really basic in this task. I used only Pythagorean theorem.
•  » » » » » 6 years ago, # ^ |   0 That's why you should practice more problems. Following your logic, I can say any task that I didn't solve is bad because "how is anyone supposed to find that out?" even when the definition of "anyone" is not exactly everyone.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +4 It's simple , but I didn't realize that particular case during the contest.Imagine that you have 3 circles puted in that way: 2 down , 1 up. You have the distances between their centers equal to r. So you have an equilateral triangle. Let's name the height of the triangle t. So we have : t^2 + (r/2)^2 = r^2. So t = sqrt(3)/2 * r.Initially you put h/r*2 circles from bottom to top so you remain with h%r. Up there you will have 3 cases: the 2 ones that are obvious ( 1 or 2 circles ) and the one presented below ( with the condition: t < h%r ).Sorry for poor English. Hope it helped you.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   +28 Simple picture:
•  » » » » » » 6 years ago, # ^ |   0 this simple picture is better than any tutorial. :)
•  » » » » » » 6 years ago, # ^ |   0 I've always wanted to know how to generate/draw such pictures.Would you mind sharing the method with us?
•  » » » » » » » 6 years ago, # ^ |   +3 I typed "Geometry" in Ubuntu Software Center. First result was "Kig".
•  » » » » » » » 6 years ago, # ^ |   +8 GeoGebra (http://www.geogebra.org) is a nice tool as well.
•  » » » » » 6 years ago, # ^ |   0 Fantastic explanation thank you very much :)
•  » » » » » 2 years ago, # ^ |   0 i dont understand the condition t < h%r
 » 6 years ago, # |   0 Any ideas for solving E?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +18 I have no idea whether there exists a nice solution which is both easy to code and fast enough. But as far as I can see now, you could use data structures like heavy-light decomposition or use brute force BFS/DFS with some tricky optimization ^_^UPD: You could cut the whole tree into blocks of size sqrt(n) by choosing sqrt(n) key vertexs. For coloring, use BFS in its block and use LCA for each key vertex. And that'll be enough to deal with queries in O(sqrt(n)) each. So you get a O(nsqrt(n)) algorithm overall.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +20 But your solution fails on this test :(http://pastie.org/8305596
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +6 apparently I knew its algorithm using HLD, But I thought that this structure should not be given in atleast Div 2 round. I am bit surprised when I saw the solution http://codeforces.com/contest/342/submission/4421565 which mentions that this is same problem as spoj http://www.spoj.com/problems/QTREE5/
•  » » » » 6 years ago, # ^ |   0 Yes, I thought my program is quite likely to get a TLE in the system test.
•  » » » 6 years ago, # ^ |   -12 Many accepted solutions are wrong(Only BFS/DFS)!I can easily hack them!--!
•  » » » 6 years ago, # ^ |   +16 You can see my O(N*sqrt(N)) solution. The idea is to handle sets of 300s red nodes with BFS, and the rest with O(1) LCA. Not sure if it is considered "easy to code" though :D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +26 I used centroid decomposition and reconstruct "centroid tree". This has O(log n) max-height and has all nodes of original tree. Every node of centroid tree has minimum distances to red node. Query Type 2, i can get minimum distance exploring nodes on the path from queried node to centroid tree's root. Query Type 1, update nodes on the path from queried node to centroid tree's root. Overall, using LCA, O(Qlog^2 N).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Very nice idea. Do you know any similar problems ? ( that use centroid in solution )
•  » » » » 6 years ago, # ^ |   +2 problems like dealing with distances on the tree. TMK, SPOJ/QTREEn series(as above), POJ 1987 and Croc Champ Round 2E[problem:293E].
•  » » » » » 6 years ago, # ^ |   0 Thank you !
•  » » » » » 6 years ago, # ^ |   +4 Thank u! I know Qtree,poj and Croc Champ Round 2E,but what's TMK? Can you say it in details or give me a link? Thank U again!!
•  » » » » » » 6 years ago, # ^ |   +7 To My Knowledge :)
•  » » » » » » » 6 years ago, # ^ |   0 ..ok.. I know it.. orz..
•  » » » » » » » 3 years ago, # ^ |   0 uwi Can you explain the approach to solve the same problem but to answer max queries(farthest distance to a red node) instead of min using centroid decomposition? Thanks.!
•  » » » 6 years ago, # ^ |   0 could you explain how you reconstruct "centroid tree" ??
 » 6 years ago, # |   0 My code gave TLE with cin for T,L,R and gave Accepted in practise when I used scanf for the same.. :-/ Isnt it a bit harsh..??
•  » » 6 years ago, # ^ |   0 what is you algorithm?
•  » » » 6 years ago, # ^ |   0 Just simple simulation..
•  » » 6 years ago, # ^ |   0 Res=Res+'X'; This takes O(length), use Res+='X';
•  » » » 6 years ago, # ^ |   0 But the solution which passed actually just used scanf instead of cin.. Dont u think in an algorithmic contest it is better if such things which are language based should be avoided..??
•  » » » » 6 years ago, # ^ |   0 Runtime with scanf = 1746 ms (your solution), I got Accepted in 404 ms using cin.Runtime with scanf and += operator = 92 ms (your solution).
•  » » » 6 years ago, # ^ |   0 what's the complexity of Res+='X'; ?
•  » » » » 6 years ago, # ^ | ← Rev. 5 →   +1 It depends on the capacity of the string, if s.size()
 » 6 years ago, # | ← Rev. 2 →   0 my silly mistake in B : could not realise that f could be smaller than s. so stuck with wrong answers on pretests even.
 » 6 years ago, # |   0 Spent 2 hours only on problem D and finally got accepted...just 1 min before the contest ended. I think the problems are harder than usual div.2 contests.
 » 6 years ago, # |   0 i had advanced to Div-1 in the last contest, but i would still have liked to take part in this one unofficially. unfortunately missed it due to the unusual time and because Codeforces decided not to send a mail to its users! :/ please make sure this doesn't happen again! :)
•  » » 6 years ago, # ^ |   +4 You don't receive any notification about Div 2 only contests if you're Div 1.
•  » » 6 years ago, # ^ |   +3 There's virtual participation for that. I, for one, miss many contests, since I'm often in regions without solid internet connection, but I always participate virtually later.
 » 6 years ago, # | ← Rev. 3 →   +1 Very weak pretests for task C.
 » 6 years ago, # |   +9 The test data for task E is too weak. Many solutions only used brute force BFS which would fail on most tests where the tree's height is big ( e.g. form a string ).. but the system test didn't include any of these cases. What's more many O(n^2) brute force even ran faster than my O(n\log^2 n) solution, while some O(n\sqrt n) solution got TLE or MLE.. Just a remind to the task setter.. Don't just use complete random data when designing test cases.. Think about possible "strange optimization" for brute force and designing test cases against them is very necessary, since passing system test with brute force is unfair to the ones who wrote complicated correct solution and to those who didn't write brute force.
•  » » 6 years ago, # ^ |   0 however, i think the test data of this problem is really hard to designed. p.s. your solution may be improved to ? the usage of priority_queue is redundant.
•  » » » 6 years ago, # ^ |   0 I didn't use priority_queue.. I think if we solve it by the original heavy-light weight decompisition, it's hard to achieve time complexity better than n\log^2n.. Maybe this solution can be improved to O(n\log n) by Yang Zhe's 'global balanced binary tree' technique ( link: http://wenku.baidu.com/view/75906f160b4e767f5acfcedb.html ).. But I'm not sure..
•  » » » » 6 years ago, # ^ |   0 It seems that task E can be solved by tree's divide and conquer algorithm in O(nlogn) instead of "the original heavy-light weight decompisition". I just solved it by which.
•  » » » » » 6 years ago, # ^ |   0 I read your code, it's really a nice solution. Thank you very much :)
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 sorry for my mistake. I hadn't seen your code yet. as Yokisami pointer out, an O(qlogn) exists indead.additionally, "global balance tree" isn't invented by Zhe Yang. some papers have been published before that.
•  » » 6 years ago, # ^ |   +3 It's not an exact true. Look at the 19th test. By the first several numbers you can guess its structure. There are a lot of tests with a huge hight of the tree.The another thing is that some of bfs' use strange unexpected optimizations. Please, post your generators against such ones, if you see such solutions. We will add the tests to the testset. As ftiasch say, the test data of the problem is really hard to design. We've break a lot of solutions, but some of them passed. We are sorry for that.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 this test would make the first several solutions with shortest code length fail.. ( i thought at first these solutions used some proof to ensure the time complexity but soon found out they are just brute force.. ) 100000 100000 1 2 2 3 ... 99999 100000 1 2 2 100000 1 3 2 100000 1 4 2 100000 .... 1 50001 2 100000 
•  » » » 6 years ago, # ^ |   0 is it true that the problem-setter can perform hack during the contest? if it is true, i guess the author should do it to prevent this kind of solutions from accepted.
 » 6 years ago, # |   0 Can someone please explain problem D 's solution to me ? I am not able to understand the solution from the editorial.Thanks
 » 5 years ago, # | ← Rev. 2 →   0 can anyone explain more the idea of the problem E (other ideas than heavy light decomposition)