### vfleaking's blog

By vfleaking, 6 years ago,

Happy Children's Day everyone. What should you do to celebrate the special holiday?

Of course, another Codeforces Round is your best choice!

There is a child who is our friend. Now he has faced a lot of algorithm problem, could you please help him?

We invite you to participate in Codeforces Round #250, which will take place at 17:00 MSK on 6.1 — Children's Day. This round will be held in both divisions.

Note that the starting time of this round is quite unusual.Why? Because it's yet another CF Round held by Chinese! We prepared many interesting problems for you.

Are you getting excited? Don't miss this round!

The problems were prepared by Delayyy, Picks and me. This is our first Codeforces round~~~~.

Many thanks to Gerald, who gave us enormous help during the preparations for this round; to ftiasch, Kissshot and 2333333333333, who are the testers of this round; and to MikeMirzayanov, who created such a wonderful platform.

In Div. 1, scores for each problem will be 500-1000-1500-2000-3000.

In Div. 2, scores for each problem will be 500-1500-1500-2000-2500.

Look! Your high rating is waiting for you! What are you waiting for?

Just participate in this contest and write code fast and nicely, and you will take the high rating home!

Good luck and have fun!

UPD: The contest is over! Congratulations to winners!

Top 5 of Div. 1:

Top 5 of Div. 2:

Unfortunately, no one has solved the problem E in both divisions. What a sad story....

Editorial for the round will be added soon.

UPD2: Editorial for the round can be found here: Editorial

• +557

 » 6 years ago, # | ← Rev. 3 →   +3 cin >> A long long time ago, there is a child who is our friend. cout << A long long time ago, there was a child who was our friend. /* UPD: Thanks for the Round :).Good luck and have fun all */
•  » » 6 years ago, # ^ |   +26 It's my fault.I have removed the stupid "a long long time ago". Oh, my poor English……
•  » » » 6 years ago, # ^ |   +32 i am reminded of this comment long long ago; // in a galaxy far far away 
•  » » » 6 years ago, # ^ |   +11 You have a good sense of humor. I believe this round will be very wonderful :)
 » 6 years ago, # |   +17 So fast announcement of the score distribution!
 » 6 years ago, # | ← Rev. 2 →   +5 "Just participate in this contest and write code fast and nicely, and you will take the high rating home!"
•  » » 6 years ago, # ^ |   +2 I'm sure about that. lol
 » 6 years ago, # |   +9 Happy to see a new template for the round announcement instead of those formal templates with the same sentences (only changing the numbers) used for the last rounds! This round seems special. Everything is new... Wish luck for everyone!
 » 6 years ago, # |   +3 quite looking forward to this round.
 » 6 years ago, # |   +25 Problem E 3000...I guess it must be very hard
•  » » 6 years ago, # ^ |   +9 Maybe you're right!~ Maybe not~
•  » » » 6 years ago, # ^ |   +37
•  » » » » 12 months ago, # ^ |   0 exactly
•  » » 6 years ago, # ^ |   +17 What a very clever guess!!! you must be genius!!
•  » » » 6 years ago, # ^ |   +12 I did the same guess! I must be genius!!
•  » » 6 years ago, # ^ |   +3 Problem E 3000...I guess it must be very hard that was an understatement. not even a single Pretests passed!
•  » » » 6 years ago, # ^ |   +26 Why understatement? More like usual Chinese round :D
 » 6 years ago, # |   +6 Chinese Div 1 E problems with wealth 3000 are usually very hard. Let's see who will solve it..
•  » » 6 years ago, # ^ |   +3 I'm curious about it, too.
•  » » » 6 years ago, # ^ |   -17 lol.
•  » » 6 years ago, # ^ |   +2 Maybe is a child
•  » » » 6 years ago, # ^ |   +15 A child can do any thing including solving E!~
•  » » 6 years ago, # ^ |   +3 I think Chinese Div 1 D problem is also very hard..
•  » » » 6 years ago, # ^ |   0 This time may not.
•  » » » » 6 years ago, # ^ |   0 haha u were right! D was easier than C today! :)
•  » » » » » 6 years ago, # ^ |   +6 Because I set D. :)
 » 6 years ago, # |   +3 Is picks a person?
•  » » 6 years ago, # ^ |   +13 ammm... Maybe he is.
•  » » » 6 years ago, # ^ |   0 broken voice！
•  » » » 6 years ago, # ^ |   0 and maybe he is not! :D
 » 6 years ago, # |   0 What about Russian language?
•  » » 6 years ago, # ^ |   +11 what about the russian language? nowhere in the blog is it mentioned that the problem statements will be in chinese.
•  » » » 6 years ago, # ^ |   +1 We would like to add Chinese language but it seems to need a big change to the website. Maybe we should advise Mike to add Chinese to codeforces? Lots of Chinese participants will be very happy for that.
•  » » » » 6 years ago, # ^ |   0 Such a request should probably already include one qualified translation of the page :D
•  » » » » » 6 years ago, # ^ |   0 Yeah. So i said it needs a big change to the website. Whatever, I'm looking forward to it.
•  » » » » 6 years ago, # ^ |   0 CodeChef now supports both Russian and Mandarin Chinese translations of English problems (xiaodao and stzgd are usually the Mandarin translators). maybe Chinese language will be added to Codeforces soon. :)
•  » » » » » 6 years ago, # ^ |   0 Looking forward to it.
•  » » » » 19 months ago, # ^ |   0 Five years past, We Chinese are able to understand the English, and I like English so much!
 » 6 years ago, # | ← Rev. 2 →   +16 Unleash the child coder within
 » 6 years ago, # |   +3 Today is my first Children's Day after my 18th birthday. I'm looking forward to having a memorable contest. Thank you very much. Good luck.
 » 6 years ago, # |   0 Wow, a typical Chinese style announcement. LOL
 » 6 years ago, # |   +4 I think this announcement is very nice :) It seems it will be a funny round.
 » 6 years ago, # |   +10 A contest on my birthday :D Thank you very much. Good luck.
•  » » 6 years ago, # ^ |   +11 Happy birthday :D
•  » » » 6 years ago, # ^ |   0 Thanks :D
 » 6 years ago, # |   0 No Chinese Discription.....Sad....
•  » » 6 years ago, # ^ |   0 click zan
 » 6 years ago, # |   +22 a 3000 E …… no one can solve Chinese's E until……
•  » » 6 years ago, # ^ |   +50
•  » » 6 years ago, # ^ |   +21 Not exactly rightThere was some people solve E in WJMZBMR's round & cgy4ever's round
•  » » » 6 years ago, # ^ |   +3 though even tourist can't solve WJMZBMR's div2 E :P
•  » » » » 19 months ago, # ^ |   0 @toursit
•  » » 6 years ago, # ^ |   0 Click ZAN
 » 6 years ago, # |   +3 I hope i do something better this time...All the best to everyone :)
 » 6 years ago, # |   +11 Obviously, the problem E is going to be a good surprise :D
 » 6 years ago, # |   0 vfleaking is good at I think problem E can't be solved by Ordinary people 。。
 » 6 years ago, # |   0 i thing it does not connect!"Happy Children's Day everyone. What should you do to celebrate the special holiday?Of course, another Codeforces Round is your best choice!"
 » 6 years ago, # |   0 Problem E 3000 again... just can't imagine how hard it can be :p The same as last chinese round
 » 6 years ago, # |   +7 My previous contest was good bye 2013. After a long time I registered today again. Then what do I see? Chinese problem setter with 3000 pointer E!! Perhaps I should postpone my first contest of 2014 till "Good Bye 2014" :p
•  » » 6 years ago, # ^ |   +17 Not like you have to solve E... not like anyone will solve E...
•  » » » 6 years ago, # ^ |   +8 True. I barely passed the pretest for A. Definitely going down today.
•  » » » » 6 years ago, # ^ |   0 me too... going down consecutively for the 4th time :(
 » 6 years ago, # |   0 Can I upvote twice? Or thrice? Please?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 As far as I know, you cannot. Sorry :)
•  » » » 6 years ago, # ^ |   0 .
 » 6 years ago, # | ← Rev. 3 →   0 I'm probably going to kill the problemsetter if in Div1 250C the 6th pretest (the one almost everyone has failed in their first submission) has multiple copies of the same vertex.I do really hope that there is another reason for my solution failing it... :D
•  » » 6 years ago, # ^ |   0 Come on, that test wasn't so bad... pretests 5 and 9 were equally [sarcasm]user-friendly[/sarcasm]I'm guessing more like tricky situations with diagonals inside/outside the polygon with multiple collinear vertices — the standard geometric axe
•  » » » 6 years ago, # ^ |   0 Oops I gave you -1. [truth] I wanted to give +. Liked that [sarcasm] [/sarcasm] [/truth]
•  » » 6 years ago, # ^ |   0 Maybe collinear segments? It took me more than one hour to find this... So bad that I didn't have it in my library ; d.
 » 6 years ago, # |   +14 A Google search on mysterious number 998244353 leads to integer FFT, maybe that's a hint to problem E, but I can't got any idea.
•  » » 6 years ago, # ^ |   0 That'd be finally one nice modulo that allows it. It's annoying that you can't do FFT with the most common ones, 109 + 7 and 109 + 9...
•  » » 6 years ago, # ^ | ← Rev. 6 →   0 That's quite possible. Note that if we were to count number of directed paths (let's say, there can be no left children), our answer would be the coefficients of the following polynomial: (it's easy to see if you know anything about generating functions). However, at the moment I have no idea how to generalize it to count number of trees... ;)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Okay, so let's define the generating function as follows: there are ci good binary trees of weight i. Then P(x) satisfies P(x) = 1 + (xc1 + xc2 + ... + xcn)P(x)2Explanation: every tree is either a "dead end" ("empty set"); this is this 'one' in the equation or a vertex having one of the weights: c1, ..., cn and two subtrees (maybe non-existent). Of course, each of the subtrees can be described by the same generating function P(x). That's why we have the second addend.However, I have no idea how to compute P(x) fast (even the m lowest coefficients)...
•  » » » » 6 years ago, # ^ |   +8 Square root of polynomials is the solutiin. However, to let it easier, we let divide and conquer + FFT pass it, even though the only person who do this got TLE with some reason...
•  » » » » » 6 years ago, # ^ |   0 How to calculate the square root of polynomial fast?
•  » » » 6 years ago, # ^ |   0 In problem E answer is the same row, but with catalanian numbers as a coefficients
 » 6 years ago, # |   +11 how to solve Div-1 B?
•  » » 6 years ago, # ^ | ← Rev. 3 →   +8 i used maximum spanning tree and disjoint set.cost for each edge between U and V is min(animal[U], animal[v]) .
•  » » » 6 years ago, # ^ |   0 Then...How to get the answer in this way? I'm afraid I still don't know what to do next.
•  » » » » 6 years ago, # ^ |   +3 while you build maximum spanning tree you can calculate the answer. when you add edge U-V the number of ways use this edge is ( number of nodes are reachable nodes from U in spanning tree before adding U-V) * (number of reachable nodes from V in spanning tree before adding U-V) so ans+=(cnt[U]*cnt[V])*Cost[U-V], and then you add U-V to the maximum spanning tree with updating disjoint set (like Kruskal algorithm).
•  » » 6 years ago, # ^ |   +6 I used a Union-Find approach, where you add the nodes from largest value to smallest value. Then think about what happens when you add a new node — all nodes that are not yet connected must use a node that is at least this low. It then comes down to combining multiple adjacent components of already added nodes, think about this and you will figure it out (its simply multiplying the sizes together with the current node value).Not sure if this is intendend solution or even passes systest, but it worked on pretests.
 » 6 years ago, # |   +86 (•_•) I guess( •_•)>⌐■-■ in this contest(⌐■_■) we were troll'DYEEEEAAAHHH! Srsly, D... I wonder how many people had the same trololo solution as me: keep an interval tree that allows operation 3 and is able to find the largest number in a given interval along with its position; when performing operation 2, just keep taking out the largest number and moduling it until there are no numbers  ≥ x; sums are then handled by a Fenwick tree.I have a nice proof of why it works: consider a number a and applying a = an = a%x on it for various x. If such an operation had any effect, then either or the next modulo that has any effect is , or it's . In the second case, , and in the third, . We can see that after 2 modulos do something, a must decrease at least 2 times, which can only repeat times. Therefore, the total number of actions for all operations of type 2 is and with lookup and related updates, plus the cost of processing the other queries, gives total time complexity . WIN!
•  » » 6 years ago, # ^ |   +11 It's quite right. You can think about how to solve it when operation 3 is segment modify.
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 i don't know way My Solution got TLE, for operation of type 2 i update an interval if maximum number in this interval is >mod.
•  » » » » 6 years ago, # ^ |   +3 Updates all numbers in the interval or just the ones that are actually larger? It's a huge difference in complexity.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 it's a segment tree, if int an interval C , node[C].max<=mod then i return other wise i process this interval with calling upd(i*2), upd(i*2+1), i think this should update only bigger number ans skip the other ones.
•  » » » » » » 6 years ago, # ^ |   +3 Sounds like it should work, maybe it's just a problem with constant factors.
•  » » » » » » » 6 years ago, # ^ |   0 maybe, that's disappointing :(
•  » » » » » » » » 6 years ago, # ^ |   0 Looking at your code's times: or maybe an unlucky infinite loop. Or I'm wrong and it's really too slow, maybe by little and there's an evil test. Who knows...
•  » » » » 6 years ago, # ^ |   +3 There is bug in function updmod: nd[i].m=x;
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 oh, that was a stupid bug ! :(( thanks
•  » » » » » » 6 years ago, # ^ | ← Rev. 4 →   +3 Try this: if(nd[i].m
•  » » » » » » » 6 years ago, # ^ |   0 i got it, thanks. i should be more careful next time
•  » » 6 years ago, # ^ |   +16 Same as your solution, but I used a division into sqrt(N) blocks instead of a segment tree (and for each block I maintained a multiset with the sorted elements, in order to easily update only the needed numbers at each modulo operation). I was very reluctant to implement this and I thought quite a long time about how I could "compose" two modulo operations, but after not finding any way of efficiently composing them, I implemented this just in case :) Still, it could have TLE'ed, because of the sqrt(N) factor (compared to only a log(N) factor in the segment tree solution), but it didn't.
 » 6 years ago, # |   -7 I guess it would me more correct to put Div2 C problem worth 1000 points.
•  » » 6 years ago, # ^ |   0 The solution was quite easy, but realizing it wasn't (in my opinion).
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +3 In my opinion realizing this problem was very easy. Here is my code. 6772286
•  » » » » 6 years ago, # ^ |   0 Please, what is the proof behind your solution?
•  » » » » » 6 years ago, # ^ |   +1 proof explained here
•  » » » » » » 6 years ago, # ^ |   0 thanks!
 » 6 years ago, # |   +23 I am really surprised by the elegant solution for Div 1 A ( min of each end of an edge ). It's like instead of removing the nodes, we were just cutting the ropes.
•  » » 6 years ago, # ^ |   0 So was I. That's really an awesome solution!
•  » » 6 years ago, # ^ |   0 you say Div2 B?
•  » » » 6 years ago, # ^ |   0 Div1 A = Div2 C.
•  » » 6 years ago, # ^ |   +11 Thanks, I'm glad you like it >_< .
•  » » » 6 years ago, # ^ |   +22 BTW is vfk some kind of abbreviation of vfleaking?
•  » » » » 6 years ago, # ^ |   +20 Yes! You find it! :)
•  » » » » 6 years ago, # ^ |   +4 You got it! =w=
•  » » 6 years ago, # ^ |   0 I can't figure it out why this solution get write answer ? can you explain more please
•  » » 6 years ago, # ^ |   0 How to prove it?
•  » » » 6 years ago, # ^ |   0 forthright48's and following idea are same ideas, but idea below is more intuitive I think:Idea:First choose the toy with maximum vi, and remove it. Now remove toy next with maximum vi (if it has any adjacent rope, of course). And so on.
•  » » » 6 years ago, # ^ |   0 proof explained here
 » 6 years ago, # |   +43 At the start I opened Div1 problems instead of Div2 and thought the problems look much tougher than the usual rounds. So I checked the dashboard and found 230 people had already solved A(Div2 C) so I decidded to manage it somehow and started working on it. I got the idea in a few minutes and thanks to my poor internet connection after reconnecting 2-3 times when I finally tried to submit it showed "You must be registered to submit" error. Only then did realize my mistake and finally solved my first problem C in contest time. :D Earlier I did not even read problems beyond B because I thought they are too hard for me. But after this I think I will atleast read all problems after solving A and B.
•  » » 6 years ago, # ^ |   +4 Sometimes C is much easier than B!
•  » » » 6 years ago, # ^ |   +1 Yeah this was one of those occasions. I couldn't solve B.
•  » » 6 years ago, # ^ |   +17 That is a great story, congratulations! Sometimes the biggest obstacle is the belief “This problem must be too hard for me.”
 » 6 years ago, # |   0 Prob C Div2 which is Prob A div 1 is it a greedy or DP problem ?
•  » » 6 years ago, # ^ |   0 It's a "don't think hard, think smart" problem. Read the comments above before asking.
•  » » 6 years ago, # ^ |   0 As I thought (it might be wrong), we can add to sum minimal cost of line from a to b or from b to a for every line.
•  » » 6 years ago, # ^ |   0 Greedy.
•  » » » 6 years ago, # ^ |   0 do u mean remove the nodes in decreasing order of ? if so, can u give a proof for this? i couldn't prove it during contest, so i just checked that it worked for all sample cases (and 2 more of my own), and implemented it!
•  » » » » 6 years ago, # ^ |   +1 Yup, remove the vertices in decreasing order of vi. It's obvious that you can do it, and that this way, each edge will be removed exactly once, adding cost vi to the total. Also, when an edge is removed, it adds to the total cost v of one of its endpoints, so this greedy gives the total cost equal to this lower bound.
•  » » » » » 6 years ago, # ^ |   0 will, can you please explain this case 5 4 10 20 20 20 20 1 2 1 3 1 4 1 5 
•  » » » » » » 6 years ago, # ^ |   +27 My name isn't Will :DWe have 4 parts connected to a central one. Removing each of those 4 parts costs us 10, and that's what we get when taking min(v1,vx) for x=2,3,4,5.
•  » » » » » » » 6 years ago, # ^ |   0 I know i meant the word will :3 thank you for explanation, im convinced now :D
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +13 When we remove vertex i, we get a cost from vertex j (namely vj). Assign this cost to the edge ij. Then the total cost required is the sum of costs of all edges.Note that each edge is only counted once (when removing one of its endpoints; removing any other vertex doesn't affect this, and removing the second endpoint has no effect as the first endpoint has gone), and its value is the cost of one of its two endpoints. Thus we minimize the total cost by minimizing the costs of all edges, namely by choosing the smaller cost for each edge.When we remove the nodes in decreasing order of vi, we always assign the smaller cost to each edge. Suppose for edge ij, we assign the value vj, but vi < vj. Then we should have removed vertex j first and assigned the value vi to the edge, contradiction. Thus we have assigned the smaller cost to every edge, and thus we have obtained the smallest total cost.
•  » » » » » 6 years ago, # ^ |   +3 Nice explanation. I also couldn't proof it during contest.
•  » » » » » 6 years ago, # ^ |   +8 nice proof. thanks a lot! :)
•  » » » » » 6 years ago, # ^ |   0 I tried to find the i-th node having the minimum sum of energy of its connected j-nodes and removed the i-th node iteratively. I was wrong hoping that greedy approach would work here :( I did not think that removing minimum sum cost of connected node can have its own energy values too high and thus increasing the total cost. Still I understood my mistake and i hope i don't commit this mistake again
•  » » » » » » 6 years ago, # ^ |   0 The solution is actually greedy, but in a different greedy way (take the vertex with the largest cost every time).Your solution fails for the following: 3 2 3 2 2 1 2 1 3 A vertex with cost 3 is connected to two vertices with cost 2.Your solution dictates that as both of the cost-2 vertices have lower minimum sum of costs (namely 3) as opposed to the cost-3 one (namely 2 + 2 = 4), you remove one of them first. This way you get an answer of 5, while the optimal solution is 4 (remove the cost-3 vertex first).
 » 6 years ago, # |   +4 Hi setters, I really like at least those problems I had a chance to read — A, B, C, D in DIV2, thanks ;-)
 » 6 years ago, # |   0 Any hint for task D div2?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 DSU. Kruskal's algorithm.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 It's not the Kruskal algorithm in fact. It just uses disjoint set union.
•  » » » » 6 years ago, # ^ |   0 Mmm, in my solution in the end I have maximum spanning tree so I think it can be called Kruskal algorithm.
•  » » » » » 6 years ago, # ^ |   0 Well, I'm sorry then. In my solution I do not use Kruskal's algorithm at all.
•  » » » » » » 6 years ago, # ^ |   +6 Oh, no problem. I think ideas of all solutions are the same and having Kruskal or not is just question of implementation.
 » 6 years ago, # | ← Rev. 3 →   +6 At first, I didn't know how to solve A and got WA twice. Then, I checked Status and noticed that the memory usage of those who passed pretests was too low. I realized that I didn't have to make an adjacency matrix XD
 » 6 years ago, # | ← Rev. 2 →   0 Nice round. It seems that the ones who predicted there won't be any accepted solution to E where right. I want to ask what are some good materials on FFT (because Wikipedia gives a lot of probably interesting stuff, but they seem too mathy to apply in any programming contest task). Thanks in advance.
•  » » 6 years ago, # ^ |   0 "Introduction to Algorithms".
 » 6 years ago, # |   +5 hacking at DIV2 was like hell :D pretty contest,thanks vfleaking
•  » » 6 years ago, # ^ |   0 i only wish Div-1 also had more hacking opportunities! other than that, it was a great round! keep it up vfleaking! :)
 » 6 years ago, # | ← Rev. 2 →   -16 I think that the test cases for Div1D are weak because many users get accepted solutions using O(NlogN) for operations type 2. For example Petr solution: 6770456
•  » » 6 years ago, # ^ |   0 It's in average, because each number X can be decreased with operation Mod only times.
•  » » 6 years ago, # ^ |   +5 I explain it here
•  » » » 6 years ago, # ^ |   -8 consider this test caseN = M = 10^5all elements a[i]=10^9all querys of type 21st — [1 N] x=10^9 — 12st — [1 N] x=10^9 — 23st — [1 N] x=10^9 — 3..what is the complexity for this test case?
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   +21 LOL, after the first query all numbers will become 1's, so other ones will be processed in O(1) time.
•  » » 6 years ago, # ^ |   0 the time limit is 4 secs. And it is not O(nlogn) for operations type 2. When the maximum of an interval is smaller than the mod number, this interval can be skipped, because x%m=x, when x=m,we can get x%m
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 That's because a number won't be done modulo operation efficaciously too many times.
•  » » 6 years ago, # ^ |   0 Solution of 1D works in O(MlogNlogMAX) , we can use potential method to prove it. Let's assign the potential of number P be logP, then if that number is changed by operation 2 its potential decreases at least 1. And then build an interval tree which supports dynamic RMQ problem, and while working on operation type 2 first check if the maximum element in range(l,r) >= M, then process it on that number, until such number doesn't exist in asked range.We can see that:Initially: the potential of the sequence <= NlogMAXOperation 1: costs O(logN) time, and potential doesn't change. Amortized complexity = O(logN).Operation 3: costs O(logN) time, and potential increases at most logMAX, as we need O(logN) time to clear 1 unit of potential, amortized complexity is O(logN + logNlogMAX).Operation 2: We need O(logN) time to check the maximum <= M, and because the time to clear potential is included in operation 3, this is not counted in total time.Summing up all these cases gives us O(MlogNlogMAX) total time complexity
 » 6 years ago, # |   -17 Мне неясно почему в задаче A DIV.2 в 28 тесте ответ С, а не A?
•  » » 6 years ago, # ^ | ← Rev. 2 →   -23 Два хороших ответа: A и D. Значит, мальчик выберет ответ C1 по крайней мере в 2 раза меньше и 2, и 4, и 8А 8 по крайней мере в 2 раза больше и 1, и 2, и 4
•  » » » 6 years ago, # ^ |   -7 could both write in english for everyone understand? or translate in google like me
•  » » » » 6 years ago, # ^ |   +3 It's because lucAbalo forgot to check Russian language when writing the comment.lucAbalo: Why in Div2 A "C" is answer to 28-th test, but not "A"?me: Two good answers A and D. So, boy will choose answer C1 is at least 2 times less than 2, 4, 8And 8 is at least 2 times greater than 1, 2, 4
•  » » » » 6 years ago, # ^ |   0 Google translation is convenient...but the result may be strange for understand....
•  » » 6 years ago, # ^ | ← Rev. 2 →   -8 Потому что D длиннее всех остальных вариантов как минимум в два раза, а значит у нас есть два хороших варианта, в таком случае мы должны выбрать С. upd: не заметил ответ выше :)
•  » » 6 years ago, # ^ |   0 answer D and A satisfy the conditionsin this case you should print C
 » 6 years ago, # |   +6 BOOOOOOOP!I just found out what my WA in div1 B was about. I forgot to add 1LL* once...
•  » » 6 years ago, # ^ |   0 Perhaps you won't forget it any more~ XD~
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 I doubt it. It isn't really forgetting, just that I don't write it even if I realize that it should be there, and don't notice it. I don't really have time to check my code line by line and compare it with my idea of the algorithm.
•  » » » » 6 years ago, # ^ |   0 when it comes to this kind of problem, especially in the problem there is a sentence like "please use 64-bit....." I always declare all the variable as long long.....
•  » » » » » 6 years ago, # ^ |   0 It can still fail. Suppose that you're actually multiplying vector/string sizes — you'd still need to cast them, and if you're used to thinking "if I declare all as long long, then it's fine", you can fail in that case.Everything can fail, especially if you just unexplainably don't write something.
 » 6 years ago, # |   +8 I finish my div1D code at 1:59:59, and submit it...then unfortunately,out of time,just a second.... then after system test....I submit it again, accepted.what a sad story...
•  » » 6 years ago, # ^ |   +3 http://codeforces.com/blog/entry/8341#comment-140681 I know that pain :P
 » 6 years ago, # |   0 Problem Div1 C is similar to this problem Ears Cutting
 » 6 years ago, # |   0 I used a DP solution for DIV2 B to collect the sum which gave TLE at system testand i thought of DIV2 C as a graph problemI wasn't pretty sure about disconnecting the node which has a minimum-cost neighbors, maximum neighbors or the node which has maximum cost and none of them gave me optimal solution.i'm going really down today but Great contest!.Lesson learned, Never overestimate the problem!
•  » » 6 years ago, # ^ |   0 Honestly speaking, I solved DIV2 C using greedy algorithm, which was really out of my expectation.
•  » » » 6 years ago, # ^ |   0 yes. i thought of every possible way to solve this problem except the greedy way! :D
•  » » 6 years ago, # ^ |   0 How is your dp then? Actually using dp and simple backtrack can run in linear time, should be fast enough
•  » » » 6 years ago, # ^ |   0 Hi icalFikr, could you please explain the dp method? Thanks
•  » » » » 6 years ago, # ^ | ← Rev. 3 →   0 I'm not pretty sure if its called DP or elseSuppose we have range [0..X], we can make every number from 0 to X with lowbit of some elements from set S.If we add one more element from S, supposed to be M. We can update range become [0 .. X + lowbit(M)], the proof is really easy. So, range [X + 1 .. X + lowbit(M)] can be arranged by M as last component.After we precalc last component for each X <= sum, we can backtrack the query and find all of components of sum.Sorry for my bad english ^^Here is my solution if you want to know more
 » 6 years ago, # |   +5 please update the ratings soon
•  » » 6 years ago, # ^ |   +1 done
 » 6 years ago, # |   +1 Very nice contest in this special day. Problems was very interesnting to solve, and the div 2 A problem was like a bomb for hacking. I want more contest from you vfleaking
 » 6 years ago, # | ← Rev. 3 →   0 подскажите почему в задаче А вот такой тест дает ответ А сам тест A.aaaaB.aaC.aD.a
•  » » 6 years ago, # ^ |   0 "Why the answer is A and not C?" -- Google TranslateC and D aren't great, because the 1-character C is not twice shorter than the 1-character D. However, if we modify the case: A.aaaa B.aa C.aa D.a `Then yes, A and D are both great, and so the answer is C.
 » 6 years ago, # |   0 What is the complexity of optimal solution for Div2B?
•  » » 6 years ago, # ^ |   +1 O(Limit)
 » 6 years ago, # |   0 why have you added test case on div 2 B problem after the contest
 » 6 years ago, # |   0 the sad thing is that the only one who submit E problem got WR in testcase 15 :(
•  » » 6 years ago, # ^ |   0 only one who submitted passed pretests :)
 » 6 years ago, # |   0 im not convinced with the solution of problem C Div2 does any one has any proof for it ??
•  » » 6 years ago, # ^ |   +3
•  » » » 6 years ago, # ^ |   0 Thanks :D
•  » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   0 Thanks :D
 » 6 years ago, # | ← Rev. 2 →   +2 my rating was not changed :D
•  » » 6 years ago, # ^ |   0 u will find urself under Balance points in the round stats published by DmitriyH.
 » 6 years ago, # |   +22
 » 6 years ago, # |   0 Wow, kids from China. such a great round!
 » 6 years ago, # | ← Rev. 4 →   -8 [problem:C] i am getting run time error,pls help me
 » 6 years ago, # |   0 I red in the editorial: If the line segment (i, j) cross with the original polygon or is outside the polygon, f[i][j] is just 0. We can check it in O(n) time. Can you please explain me — how to check this?
 » 6 years ago, # |   0 For Div.2 problem D: I thought of a Floyd Warshall solution but the n is very big :( Any help ?
 » 3 years ago, # |   -10 Can you add the editorial link to the contest material.