By ItsNear, 5 years ago, translation, ,

Hello everyone!

The second round of MemSQL Start[c]UP 2.0 will take place today, August, 10th, 10:00am PDT. There will be two contests running simultaneously, one for people who participate onsite, and one for everybody else who advanced to the round two. Both rounds share the problemset and are rated based on the combined scoreboard.

Onsite participants will have special prizes for first three places. All onsite participants as well as the top 100 in the online contest will receive a start[c]up t-shirt.

People who have not advanced to the round two can participate in the round unofficially. Unofficial participation will be rated.

The contest will be 3 hours long, and will feature 6 problems. The score distribution is 1000-1000-1500-2000-2500-3000.

Good luck and happy coding!

UPDATE: final results will be delayed.

Announcement of MemSQL start[c]up Round 2
Announcement of MemSQL start[c]up Round 2

• +208

 » 5 years ago, # |   +54 "Since you are not in the top-500 of MemSQL start[c]up Round 1, your participation in Round2 will be marked as out-of-competition. However, the round will be RATED for you. Please be advised that this problemset is not designed for Div2 participants, and you might end up with zero problems, which will result in a significant loss of rating. Are you sure you want to register for the round?"Awesome Warning :D
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Forget what I have written before. Something strange has happend with me. xD
•  » » » 5 years ago, # ^ |   +18 Congratulations！
•  » » » 5 years ago, # ^ |   +5 Good for you :)
•  » » » 5 years ago, # ^ |   +10 Clap clap! clap for him :D
•  » » 5 years ago, # ^ |   +8 Proved true! :(
•  » » » 5 years ago, # ^ |   +5 Yay , I did not played :D
•  » » 5 years ago, # ^ |   0 should have followed that :(
 » 5 years ago, # |   +2 The time of this round is too late.I like Chinese round.But I'd like to take part in this round. (●′ω●)
•  » » 5 years ago, # ^ |   +15 So, I plan to go to bed at 7 p.m., and wake up at 0:30 a.m..
•  » » » 5 years ago, # ^ |   0 It's a good idea.
•  » » 5 years ago, # ^ |   +6 In my country, the contest was held from 0AM to 3AM (Aug 11). Despite having to go to school at 6AM, I still participate :)
•  » » » 5 years ago, # ^ |   0 me too,It's very sleepy for me to participate..
•  » » 5 years ago, # ^ |   +8 At least, It was a great round for tourist. He broke another record. (Rating 3260)
 » 5 years ago, # |   -18 The only way I can solve a problem is if it is math.. so lets hope for math!
•  » » 5 years ago, # ^ | ← Rev. 2 →   -13 do you have to be respectfully reminded again that this is not IMO.
•  » » » 5 years ago, # ^ |   +21 What if I tell you that all the problems here are about math?
•  » » » » 5 years ago, # ^ | ← Rev. 3 →   -8 Being pure math [which he refers to] is not equivalent to being about math. In other words, your definition of "about math" cannot be correlated with his definition of "math".
•  » » » » » 5 years ago, # ^ |   +43 Sorry I thought this was IMO webpage.
•  » » » » » » 5 years ago, # ^ |   -15 Yes, I thought so.
•  » » » » » » » 5 years ago, # ^ |   -8 Well, A was math and because of this I managed a +111! I think i'll be posting "lets hope for math" more often!
•  » » » » » » » » 5 years ago, # ^ |   -10 I think i'll be posting "let's not hope for math more often".
•  » » » » » » » » 5 years ago, # ^ |   +23 D was math too. Why didn't you solve it?
•  » » » » » » » » » 5 years ago, # ^ |   -11 Because it is D :(
•  » » 5 years ago, # ^ |   -39 are you fu**ing kidding me again??!
 » 5 years ago, # |   +14 The only difference between official and unofficial participation is that TOP100 receive T-shirts :P?
•  » » 5 years ago, # ^ |   -10 hmm, good point. i wonder if unofficial participants who finish in top 100 will receive a T-shirt or not.
•  » » » 5 years ago, # ^ |   +30 Last year I finished 19th and received nothing, because didn't participate in the first round.
•  » » » » 5 years ago, # ^ |   +12 tourist win the online round last year, but he couldn't receive anything
•  » » » 5 years ago, # ^ |   0 If so, then there won't be absolutely any difference between them :P.
•  » » 5 years ago, # ^ |   +8 Yeah. Unofficial participants cannot receive T-shirts, no matter how good their results are :P
 » 5 years ago, # |   0 Note : Problems not designed for Div.2, so have very people out of competition (Link)
•  » » 5 years ago, # ^ |   0 umm, but the post says that the contest will be rated even for unofficial participants.
•  » » 5 years ago, # ^ |   0 But the post not this.Are you sure?
 » 5 years ago, # |   +2 Good Luck :)
 » 5 years ago, # |   +49 Round 1 -> 3700 registrants Round 2 -> 1800 registrants It seems that the warning for hard problems is very scary and effective!
•  » » 5 years ago, # ^ |   +1 b.... it's because today in chine is ghost day. and it's begin in 1:00 to 4:00. so many people already sleep yet,like me haha...
•  » » 5 years ago, # ^ |   -8 You are wrong : Round 2 : Total: 1826 Contestants: 368 Out of competition: 1458 have only 368 contestants
 » 5 years ago, # |   -15 so sad..... can't understand what B said... so b.......
•  » » 5 years ago, # ^ |   0 thanks to Google translation....
•  » » » 5 years ago, # ^ |   0 don't you go to sleep... today i will translate in baidu translation... sad
•  » » » » 5 years ago, # ^ |   0 I think if I go to bed now, I won't wake up after 2 hours... And I will miss an important date.
•  » » » » » 5 years ago, # ^ |   0 …clock
 » 5 years ago, # |   +15 Legitimate warning . couldn't solve one !! and more sad is that , there will be no editorial !! :( :(
•  » » 5 years ago, # ^ |   +85 We will publish both editorials.
•  » » » 5 years ago, # ^ |   +9 When?
•  » » » 5 years ago, # ^ |   +7 when?
•  » » » 5 years ago, # ^ |   +1 When?
 » 5 years ago, # | ← Rev. 2 →   0 awefully hard contest :(btw I dont know the point of giving 6th problem when no one can solve that, I feel like that one problem is being wasted which could be used in other rounds ?
•  » » 5 years ago, # ^ |   +5 ACrush had 3 wrong submissions on 6th problem. Another day, may be, he could have solved it :)
•  » » 5 years ago, # ^ |   +5 And its called "An easy tree problem"
 » 5 years ago, # |   0 Problem B may have a greedy solution... Many people have passed the pretests, but I haven't. So sad Can you tell me any idea? :(
•  » » 5 years ago, # ^ |   0 mine: consider to construct all pairs between the most heavy i nodes from side A to all nodes from side B (cost: total of side B * i) and construct single pair from every other m-i lightest nodes from side A to any heavy nodes from side A (cost = m-i), choose the best i. Reverse for side B.
•  » » 5 years ago, # ^ |   0 But tourist hacked a lot on B, so it may have no greedy solution :)
•  » » » 5 years ago, # ^ |   +41 I guess those hacks were about integer overflow, not algorithm. The greedy solution is very easy to prove!
•  » » » 5 years ago, # ^ |   0 The system test will tell us the truth
•  » » » 5 years ago, # ^ |   +27 Results of intermediate calculations may overflow long long — one can receive ~(10^5)*(10^5)*(10^9). This number is bigger than 2^63, and it was easiest and most common way to hack B today.
•  » » » » 5 years ago, # ^ |   +14 Note however that the calculations (up to 1019) fit into unsigned 64-bit integer.
•  » » » » 5 years ago, # ^ |   0 So, does it need to use biginteger in java?
•  » » » » » 5 years ago, # ^ |   +6 One can use unsigned long long, as Gassa mentioned, or do some safe multiplication — if result is larger than some constant (1e18 for example) — return that constant. Actual answer is always not so big, so you may just don't care about these possibilities — is does not matter if it gives result of 1e18 or 1e19, if you know that answer will be <1e17:) And safe multiplication can be done this way: long long safe(long long a,long long b) { if (a==0||b==0)return 0; long long ii=1000000000ll; ii*=ii; if (ii/a<=b)return ii; return a*b; } 
•  » » » » 5 years ago, # ^ |   +5 Hope this test has been already included in system tests.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +6 Oh no :( didn't notice that Edit: I think my solution won't have this problem. (maybe?) If the light partition is smaller than the sum of the other side, copy it to the heaviest partition. Or copy all rows in the other side to it. This may guarentee the answer smaller than 2e14.
•  » » » » » 5 years ago, # ^ |   0 I agree.
•  » » » 5 years ago, # ^ |   +11 There was a problem. In one of the solutions overflow can happen (even for long long (10^5*10^5*10^9)). A lot of solutions were hacked because of that.
•  » » » » 5 years ago, # ^ |   -15 I think this kind of situations should be avoided by the authors. It is really annoying to have a good solution and fail because of that.
•  » » » » » 5 years ago, # ^ |   +49 It is generally expected that the person who solves the problem is responsible for avoiding integer overflows in his solutions :)
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +4 Thanks. Lesson learned...And congrats for the round ! I liked alot C.
•  » » » » » » 5 years ago, # ^ |   +3 The integer overflows made me lose a T-shirt... I will remember it very well
 » 5 years ago, # |   0 Forgot string.length() is unsigned, so can't go negative...cost me 500 points lol
 » 5 years ago, # |   +149 When can I expect system testing to start?
 » 5 years ago, # |   +28 I forget to judge the answer of D with 1e99............TAT....what a sad story!
•  » » 5 years ago, # ^ |   +4 Wow I found that my Chinese name pronounced the same as yours. XD
 » 5 years ago, # |   +88 How delayed will the results be? What I want to know is, should I wait or sleep?
•  » » 5 years ago, # ^ |   +3 It can take another hour or may be longer, so sleep might be a better option.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +9 is it done because onsite participants can be surprised by the results (like in ACM-ICPC)? i'm asking this because i noticed that access to /contest/457 (the onsite round) has been temporarily blocked.
•  » » » 5 years ago, # ^ |   +7 Seems like I didn't take your advice!!! Now the question is, do I wait for rating update too.
 » 5 years ago, # |   +13 Finally, testing has started.
 » 5 years ago, # |   +48 It's not really fair when one got only 4 participants in the room who's rating is less than 1900, and when there are more than a half of div2 participants in another room at the same time.
 » 5 years ago, # |   +5 Does the t-shirt prize apply to all participants or only to the ones that have qualified to this round ?
•  » » 5 years ago, # ^ |   0 "only to the ones that have qualified to this round"
 » 5 years ago, # |   +16 Any information on when will rating update happen?
 » 5 years ago, # |   +40 I just get rank 90 in this round, but i failed in the last round by getting rank 509.OH!! WHAT A PITY! :(leave me alone.I will count the prime number until i find the new Mersenne prime. :(
 » 5 years ago, # | ← Rev. 2 →   +8 petr solution of problem B become TLE because he uses primitive data type array instead of wrapper class Integer array. Same happened to Egor too or any user who submitted his/her solution using primitive data type. So unlucky:(
•  » » 5 years ago, # ^ |   0 I don't get it, maybe because I'm not fluent in java. It looks like O(n) and it's safe against overflow, what's the problem?
•  » » » 5 years ago, # ^ |   +11 Actually Arrays.sort() in java uses quicksort algorithm when uses on primitive data type but use O(nlogn) timsort for Object. It has nothing to do with their algorithm.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Quicksort is O(nlogn), you mean it doesn't use O(n) radix/counting sort? Ok, but plenty of solutions used sort and passed under 100ms. I still don't get the problem.Unless you mean it literally uses plain quicksort with worst-case time O(n^2), but I would be doubly amazed if that's the case (the library being that bad, and Petr not knowing that).
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +11 Quicksort is O(n^2) in worst case and Codeforces seems to have anti-quicksort test for Java-implemented quicksort
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   +3 It does perform O(nlogn) on many data sets but some special data set which increases randomisation overhead ,it becomes O(n^2) as it implemented in java library. It has happened previously, you can see here long comment
•  » » » » » 5 years ago, # ^ | ← Rev. 3 →   +13 I met a problem yesterday.I use a data structure called treap, which is a binary search tree with a expected depth O(logn), to solve 455D. Its depth is determined by a random process similar to quicksort. And then I got TLE by purely assigned rand() to each node's priority. The code is here: 7409879 (change the seed by srand didn't help.)Then I change the priority to rand()*(RAND_MAX+1)*rand() and got AC. But I thought it didn't make sense because 10^5 is not very large in comparison with RAND_MAX, so I tried rand()+rand()%2 and still got AC in 300ms, while the time limit is 4s. I still don't know why, maybe this is a similar issue?
•  » » » » » » 5 years ago, # ^ |   0 and what if you change rand seed?
•  » » » » » » » 5 years ago, # ^ |   0
•  » » » » » » » » 5 years ago, # ^ |   0 Oh, interesting, I don't understand how adding rand() % 2 may help. And it's even consistent between compilers. So, it's hardly an optimizer bug
•  » » » » » » » » » 5 years ago, # ^ |   0 Even this code got AC by generating a random number and doing nothing with it after each construction. 7410439 However this code got TLE if I only generate one random number after every two construction: 7410459
•  » » » » » » 5 years ago, # ^ |   +16 Possibly the test case uses some property of rand() which doesn't depend on the seed. If the function isn't rand(), there's no problem.
•  » » » » » » » 5 years ago, # ^ |   0 Hmm, I think this is the best possible explanation.
•  » » » » » » » 5 years ago, # ^ |   0 Oh wait, I think the shape of the largest bst is only related to the input size, and the size of other bst is not too big if the test case is uniformly distributed...
•  » » » » » » 5 years ago, # ^ | ← Rev. 2 →   +13 It seems that Codeforces' version of GCC has not so big RAND_MAX.http://codeforces.ru/contest/455/submission/7423378
•  » » » » » » » 5 years ago, # ^ |   0 Yeah I've tested this in custom invocation, but I thought it is large enough. May be I was wrong. :(
•  » » » » » » 5 years ago, # ^ |   +16 So if you have issues with rand you can try new pseudo-random number generators implemented in C++11 like mt19937 or ranlux24. Here is your code with ranlux24_base. But surely they are rather slow in comparision with (rand() << 16) ^ rand().
•  » » » » » » » 5 years ago, # ^ |   0 Surely (rand() << 16) ^ rand() is the best way to solve this problem, but I'm interested in why rand() was so slow. I thought testcase don't affect that much because the treap shape has nothing to do with key inside the node...
•  » » 5 years ago, # ^ |   0 are u talking about the anti-quicksort test?
•  » » » 5 years ago, # ^ |   0 yes
 » 5 years ago, # |   0 I am really surprised at how this code got accepted: http://codeforces.com/contest/458/submission/7419996 look at the calc function return value at the end when it calls itself
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 EDIT: Sorry, i misunderstood.
•  » » 5 years ago, # ^ |   0 This is undefined behavior, which, as we know, may do anything. This case shows that with some luck "anything" also includes "work correctly".This probably works like this: when the function does return a value, it stores it in a specific register according to the calling convention, say, R1. When it returns without return, R1 still has the value from the tail call and is interpreted as the return value from this invocation. So it magically works.
•  » » » 5 years ago, # ^ |   0 Looks like compiler automatically returns tail recursion result?! Amazing but that strongly rely on the compiler, maybe on Codeforces it works but not always work.
 » 5 years ago, # | ← Rev. 2 →   +9 Country wise ranking have been update. Easy to see how many of your country mates are getting Tshirts :)
 » 5 years ago, # |   +16 SnapDragon got +51 rating increase for 2610 pts while fura +152 for 2590 pts.
•  » » 5 years ago, # ^ |   -8 Last year rating was also calculated this way, separately for online and onsite contest:) Compare performance of Austeritas (MemSQL start[c]up Round 2 — online version, 1860 points, rating change 1988->2100) and zcg.cs60 (onsite contest, 1876 points, rating change 1927->1958). Comparing bottom part of standings — onsite contestants lost not so much rating like those who participated online; and in upper half we have opposite situation — they also gain less:)
•  » » 5 years ago, # ^ |   0 i think this maybe because SnapDragon participated onsite, but fura participated online.
•  » » 5 years ago, # ^ |   +5 Everybody in Ukraine knows that fura is damned cunning :)
 » 5 years ago, # |   +16 I got rank 111 in all participants, but rank 88 without unofficial. Will I get a t-shirt?
•  » » 5 years ago, # ^ |   +11 Luckily I am the same as you.Got rank 88 without unofficial.I think we will get t-shirt!
 » 5 years ago, # |   +8 got AC in B now just by changing long long to unsigned long long what a pity
 » 5 years ago, # | ← Rev. 2 →   0 Unfortunately my rating decreased in all two rounds. So sad :(
•  » » 5 years ago, # ^ |   +3 but i can see only one round you participate in :/
 » 5 years ago, # |   0 in 457A - Golden System is the length of each string not larger than 100000? because when i use an array of 100003 numbers my solution got runtime error but i got AC after switch to an array of 200003 numbers.
•  » » 5 years ago, # ^ |   0 The length of each string does not exceed 100000. So yes, the length of each string, not the sum of the lengths of the strings.
•  » » 5 years ago, # ^ |   +3 i:=2*length(x)-2; There's your problem.
•  » » » 5 years ago, # ^ |   0 fixed, thanks :)
 » 5 years ago, # |   0 Can someone explain problem C(elections)? I made each politician a vector, and sorted so that their cheapest voters are at the top. Then I found whether it is cheaper to get one bribe from the politician that has the most votes, or if it is cheaper to get two bribes from a politician that has less votes than you currently do, and to bribe either the one or the two people. You continue doing this until you win the election. I never could test this, as I ran out of time in the compiler but not on my computer. What was the correct solution?
•  » » 5 years ago, # ^ | ← Rev. 5 →   +6 1) Let's sort all votes (for other candidates) by their cost. Now we make a segment tree. Each node is a pair . To this tree we put each pair , cheapest on position 0, second cheapest on position 1 and so on.2) We make an array A of vectors, for each candidate there is a vector with costs of bribes. We sort each vector (by costs) and then the array (by number of votes). Let N be a number of candidates and .Ok, so these are data structures that we will use. Now the algorithm. Let's consider 2 cases: We buy more than H votes. Then it really doesn't matter which votes we buy. So we just take H + 1 cheapest votes. To take this number we can use our segment tree. We take X votes, where X ≤ H. First part: for each candidate with number of votes T, where T ≥ X we have to bribe some of them, at least T - X - 1. So for each such candidate we take this number of his cheapest votes. And here is the trick — we take these votes from vector associated with this candidate (take and remove from vector) and then we remove these votes from our segment tree. Second part: now each candidate has less than X votes, so we can proceed as we did in first case. To make this algorithm fast we need the most important observation — it's easy to find a result for X - 1 when we found a result for X. We just take a cheapest vote from all candidates who have currently X - 1 votes, than we remove these votes from vectors and segment tree and we are done.
•  » » 5 years ago, # ^ |   +10 Let us decide on how many votes the runner party gets at the most. I will call it x. Let us say we know optimal x. Now we need to buy candidates from parties which have more than x voters. It is optimal to by least cost voters from each such party. At this point all parties have atmost x voters. We have initialCount + BribedNow number of voters. We need x+1 voters for our party. If we have enough, then we are done. If we do not have x+1 voters, say we are short by y voters. Now we need to bribe y more voters. This voters can be from any party, so we take the least cost voters irrespective of party. Done. We know how to solve for a given x. Now we need to loop over all x and find the best answer. Loop over x from 10^5 down to 0. Let us sort the voters of each party before hand. So now in each step we might bribe some voters from some parties. And calculate y (still needed voters), then we need to answer what is the sum of least y voters from left out voters. We need a data structure to answer this in log N time. I used BIT. one BIT keeps track of "active or not", another keeps track of respective sum. We binary search for first index such that number of active voters <= that index is greater than equal to y. Once we get the index we need the sum of active voters <= that index which we can get from another BIT. This seems bit confusing, but take a look at my code.. See how query, update operations are made. Also when we remove voters from each party (due to <=x condition) we make those voters inactive and reduce respective sum.
•  » » » 5 years ago, # ^ |   +5 After looping over x from 0 to n-1 I noticed that the cost function is most likely convex and used ternary search, got AC.
 » 5 years ago, # |   +5 submission for A with biginteger 7420935 without any normalization xD -
 » 5 years ago, # |   +35 How to solve problem D?
•  » » 5 years ago, # ^ | ← Rev. 4 →   +88 Maybe not the easiest way to go, but still one.Let S be the set of all rows and columns. We're asked to compute exactly covered — no other rows and columns are covered.Now I state it's the same as (in this sum, we add a possibility that there are other covered rows/columns).Why? Consider all the situations when set A gets exactly covered. How many times will it be counted in the second sum? Of course, it's counted (only) for sets B which are subsets of A. It means each such situation will be counted exactly 2|A| times. Now we'll focus on computing the second sum.The second observation is obvious: let's say we choose r rows and c columns. Then the probability doesn't depend on which rows and columns we've chosen! It means we can compute all these situations at once: Now it's easy. We've already chosen r rows and c columns and now ask how many are there ways to cover them. Let fr, c = N(r + c) - rc — the number of cells that make these rows and columns. Then we need to choose fr, c numbers from K correct numbers and distribute them in any way; then we choose remaining N2 - fr, c numbers from remaining M - fr, c ones and again distribute them in any way we want. And how many bingo boards are there? Of course we choose any N2 numbers from M and distribute in any way. This all gives us the sum (where nPk are partial permutations, equal to ).It's of course the final result, but we may change it into a fraction of products of factorials (it looks ugly, but it's easy to put into the program and compute). Also note the factorials in the fracions may be huge, so it's a better option to make the computation on their logarithms.//Edit: the expanded equation is here: Of course, if any of factorial arguments in the fraction is less than 0 (K - fr, c can be), the fraction is equal to 0 (because then KPfr, c = 0).
•  » » » 5 years ago, # ^ |   +19 Great explanation, thanks!
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +17 after selecting r rows and c cols, there are m-f(r,c) left, we still have k-f(r,c) to choose, the total choosing method is C(m,k), so we have: which results the same in another way.
 » 5 years ago, # | ← Rev. 2 →   0 http://codeforces.com/contest/458/submission/7427428 here is my solution for problem c. When I want to get x votes, I get from everyone who has votes more than x. then if I still dont have x votes I pick the ones with lowest cost if they didnt get picked. And I assume that the the cost function f(x)(I want to get x votes. returns min cost) first increases and then decreases. So I binary search on it. I dont know if this is a true approach but I pass 53 test cases and get wrong answer on the 54th. Can you help?
•  » » 5 years ago, # ^ |   +5 If your assumption is true (f decreases and then increases) you have to do a ternary search instead of binary. Personally I've just calculated f for all possible x.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 it is like a ternary search. I take 2 values x and x+1 and check if f(x) is > f(x+1). If so I search for the left side, otherwise the right side. I have also done it with ternary search with the same code above but it didnt work. It gave wrong answer again in the 54th test case.
•  » » » » 5 years ago, # ^ |   0 what to do if f(x) == f(x+1)?btw my messy ternary search solution passed http://codeforces.com/contest/458/submission/7418801
•  » » » » » 5 years ago, # ^ |   0 If the function is not strictly increasing/decreasing, then ternary search also fails, so I suppose you shouldn't worry about that.
•  » » » » » » 5 years ago, # ^ |   0 I think f(x) should be non-increasing til some point and non-decreasing afterwards. So it may fail.
•  » » » » » » 5 years ago, # ^ |   +15 The function is actually convex, not just unimodal, so if f(x) == f(x+1) you're at a minimum anyway. Ternary search works.
•  » » 5 years ago, # ^ |   +1 Your ternary search may work, but problem is with this line (maybe on more places too)for(int i=0;i
•  » » » 5 years ago, # ^ | ← Rev. 3 →   0 Oh you are right. Thank you so much. :D Got AC when I changed every N I saw to 100000 :D.
 » 5 years ago, # |   +43 Here's a strong hint for problem E (my submission in the contest failed, but only due to missing a case).Instead of thinking about this as network flow, think about it as electrical flow from source to sink. Bandwidth becomes current, weight becomes resistance, and cost becomes power. Electricity flows to minimise total power (principle of least action), so the current flows will be the solution to the intern's problem.The standard way to solve current flow on a general graph (well, not quite this general), is to solve for the potential at each node, relative to some reference node. For each given link, you have the potential difference between the endpoints. The problem thus becomes to determine whether there is a set of potentials that is consistent with these differences, as well as enough extra links to make the network biconnected and satisfy the flow constraints.
•  » » 5 years ago, # ^ |   +5 May I ask you a question: why do you define your functions and global variables as static while there is only one file?
 » 5 years ago, # |   -43 give me '-' pls
 » 5 years ago, # |   +52 Still no editorial neither to Round 1 nor Round 2?
•  » » 5 years ago, # ^ |   +5 Still no results of this round.
 » 5 years ago, # |   0 Omg editorials pls?
 » 5 years ago, # |   +27 My guess is that editorials will be published when someone solves F. :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 http://codeforces.com/contest/457/submission/7687485 So, it is a time to finally publish the editorial :)
 » 5 years ago, # |   +1 omg still no editorial. People can't understand how to solve the questions they missed without a editorial; this is the importance of publishing one.
•  » » 5 years ago, # ^ |   0 They can look at other peoples' submissions.
•  » » » 5 years ago, # ^ |   +15 But they still can't understand how to solve problem F...
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 These are the advantages of editorials:1) Time efficient [you don't have to go through submissions looking for a good one and then read the code]; 2) Can present more than one way to solve a problem3) Like qwerty said, can help people solve unsolved problems.