"The participation fee is €1270 per person"

Auto comment: topic has been translated by vlad8 (original revision, translated revision, compare)

Let X be the answer. It's easy to see that X = A * B * C — numberOfBadTriples. Bad Triples are triples where one of numbers is more of eq to sum of another 2. So the only problem now to score them fast. Let firstly score number of triples where C >= A + B. What is it? It's Sum(i,1,A)(Sum(u,1,B)(Max(0,C — i — u))); It's easy to see that Max(0,C — i — u) == C — 2 only for i==u==1, Max(0,C — i — u) == C — 3 in 2 cases: i==1, u==2 and i==2, u==1, Max(0,C — i — u) == C — 4 in 3 cases and so on. It's the main idea and then it's easy find O(1) formula for this sum, it I will leave for u)

Nice solution! But lets S = "111..(50)" + "000..(100)" + "111..(850)". So you will find that there 100 zeros, then you will add 1 850 times, then start getting NO answers and add zeros 100 times, then binary search and adding left part of S, so you will have 850 + 100 + 150 queries + binary search. Don't I understood something or it's really a problem?

If I correctly understood problem statement the solution is follow: 1) Ask if "1" in S 2) If YES ask if "11" in S else ask if "01" in S 3) And do so, each time having NO answer swap last symbol, it's easy to see that we will decode such way, but there's one problem — when we get end of the string we won't know it. So you have to score NO and when you get 12 NO in row you should start deleting symbols one be one to know where is the end of string 4) And for this strategy you will decode correctly every time if there's no "000000000000" substring in S. So maybe it's better to add random symbol every time It's all. Does anyone has no-randomized algorithm?

Some informal proof: 1) Answer is sum of depth of universities (constant) — sum of LCA of chosen pairs, so to maximize an answer we have to minimize sum of LCA. 2) So we have to proof that sum of LCA is minimal when we pick pairs (i, i+k). 3) LCA of (i, i+x) never becomes more with x growing, so for every i we want to chose as big x as possible. 4) Now it easy to see that if we will never match some university from first k with some other from first k, because we will have that way some pair from second k too, and we can swap them with making LCA sum less of same easy way: ....1......1....k....2....2......=>....1..........2....k.....1.......2.... (1 and 2 are pairs number 1 and 2) , because x became more in both pairs. 5) So we just need to chose permutation of pairs of second k universities like: 123456 p(1)p(2)p(3)p(4)p(5)p(6) 6) Lets dist(i) = distance between pair number i. Now the main statement: dist(i)>=dist(i-1) in one of optimal solutions. Proof: let dist(i)<dist(i-1) for some i. Than we have next ....i-1 i....k...i(0 or more universities)i-1.... By swapping it to ....i-1 i....k...i-1(0 or more universities)i... we will never makes answer worse because if LCA of i-1 pair now became bigger by a than it's easy to see that LCA of i pair will become less at least for a (easy to see from that "new LCA's" of i-1 pair was definitely lost by pait i, and maybe even more because left i is righter and may have even depther LCA). 7) So dist(i)>=dist(i-1) and the only case when it works is when dist(1)==dist(2)==...==dist(k)==k because dist(1)>=k and sum of dists == k^2. All=) P.S. It's not informal now, but it was such in my head when I started writing))

Solution for problem F: 1) Lets try to find any simple path from S to T. It has O(n) edges. Of course if there isn't such path the answer is 0. 2) It's obvious that we have to delete at least one of these edges. Lets iterate over these edges and try to delete each of them. 3) Now we have graph where we can delete no more than 1 edge. If now there isn't path from S to T than we just do ans=min(ans, w of edge that we chosen on step 1); If there is path between S and T we can use bridges-finding algo. It works in O(m). It's easy to see that we can delete every bridge to delete the path between S and T. So we just chose the cheapest bridge and do ans=min(ans, w of edge that we chosen on step 1 + w of cheapest bridge); 4) Of course if we didn't find any bridges on any iteration ans is -1, else just cout<<ans. Total we get O(nm)

Can someone explain me what the difference in these solutions, why first works this and second this gives WA 45? The only difference is in 61-63 lines, but as I can see they should do the same thing (the same representation as a result)?

Can you show me this accepted solution? My solution with this approach got WA 45, and the mistake in case when they are not close to each other My solution itself

Who draw the picture from post? Mike, you, or maybe there is nice site with programming pictures?))

Could someone give me D div 2 test 3 third testcase fully, I just can't understand what's wrong with my code, thanks in advance

Hmhmhm...

translate: I need downvotes._.

For example answer is the sum with i from 2 to 100 P(100,i) p(n,k)=p(n-1,k-1)+p(n-k,k), start of dinamics with p(i,i)=1, p(i,1)=1, p(i,i+a)=0(a>0)

We can count for each posicion sum of numbers of Big letters righter and Small letters lefter it, and the answer will be minimum of this sum for all posicions (sorry for my English:))

Hm, as I understood I can't submit tasks like VK Cup 2012 Wild-card Round 2 and some others specific contest were here. Is this any way or I really can't submit them now?

Hala Madrid!!!!!!!!

Wow guy. Just wow. It's something I need. Thanks a lot!!!!!!!!