By zxqfl, history, 3 years ago, ,

Hi Codeforces,

I'm excited to announce the Canada Cup, the first Codeforces contest to be sponsored by Diagram!

This is a rated Codeforces round (with T-shirts!) for both divisions which will take place on October 22 at 11:00am EDT.

Although the contest is organized in Canada, all competitors worldwide will be able to compete and win prizes.

The problems for this round were written me (zxqfl) and the Codeforces team. I'd like to thank:

• My coauthors for contributing great problems to the round
• GlebsHP for his help in preparation
• MikeMirzayanov for creating Codeforces and Polygon
• Tatiana_S for translation into Russian

I'd also like to thank Diagram for sponsoring the round. Diagram is interested in hiring software engineers, so please take a look at the information at the end of this post if you're interested. For anyone outside of Canada, they'd like me to let you know that Canada has friendly immigration policies for software engineers.

Both divisions will compete in the same contest, which will consist of 7 problems of the same difficulty level as a regular Codeforces round. The contest will last for 2.5 hours.

The score distribution will, of course, be announced later.

Here is some information from the round sponsor:

## Prizes

• The top 100 competitors will get a Diagram T-shirt.
• Local winners (Montreal): Dinner with Francois Lafortune (CEO, Diagram), founders of Dialogue, and other Montreal technologists
• Local winners (Toronto): Dinner with Karel Vuong (Director, Diagram), founders of Collage, and other Toronto technologists

Diagram is a venture launchpad building the next generation of Canadian-based global technology companies. By assembling teams of world-class founders pursuing big ideas for innovation in the financial and insurance industries, and surrounding them with capital, expertise, and infrastructure, they are betting big on their companies and equipping them with everything they need to innovate and build a better future.

Diagram’s investment portfolio includes the companies featured below and they all work with teams that leverage modern frameworks, cutting edge technology, and complex algorithms to deliver wellness and prosperity to all.

## Diagram's Investment Portfolio

Collage is re-inventing the way Canadian businesses manage HR, payroll, and benefits. By offering a 100% free and comprehensive platform, Collage automates paper-based and manual business processes and HR administration in ways that are efficient and secure at scale, enabling companies to spend their time on the more meaningful aspects of business.

Dialogue is the best part of your company's health plan. By offering a range of healthcare services for your team, Dialogue helps to keep them happy, healthy, and performing at their highest potential. Dialogue is using machine learning, natural language processing, and AI to process text conversations, video interactions, and imagery sent from patients to their chatbot in real-time to provide accurate diagnoses of physical and mental health concerns.

## Applying to Diagram

For those interested in an opportunity with Diagram or any our portfolio companies, please apply here.

UPD Scoring distribution is 500 — 1000 — 1500 — 2250 — 2500 — 3250 — 3500.

UPD The contest is over! Congratulations to the top 5:

If you won a prize, you'll be contacted soon.

UPD Editorial: http://codeforces.com/blog/entry/47974

Announcement of Canada Cup 2016

• +313

 » 3 years ago, # | ← Rev. 2 →   -23 "The top 100 competitors will get a Diagram T-shirt."Top 100 competitors in each division?
•  » » 3 years ago, # ^ |   +60 Are you joking?
•  » » 3 years ago, # ^ |   -10 My question too...Also in the contest page it's div1-div2 combined...
•  » » 3 years ago, # ^ |   +67 The post has been updated: now members of both divisions will participate in the same contest.
•  » » » 3 years ago, # ^ |   -27 I won't forgive you... :/Got down-votes cause of you :/
•  » » » » 3 years ago, # ^ |   +27 Someone want more downvotes... I read somewhere that downvote can have negative impact on behavior... Seems true.
•  » » 3 years ago, # ^ |   -6 Then all div1 users would create div2 fakes
 » 3 years ago, # |   +84 Does Diagram or your companies offer any internship opportunities for undergraduate students? If yes, how can I apply for it?
•  » » 3 years ago, # ^ | ← Rev. 2 →   -81 <3
•  » » 3 years ago, # ^ |   +68 I work with Diagram. Unfortunately, we aren't looking to offer internship opportunities to students outside of Canada at this time. It's fair game for Canadians though!This is the first content we've sponsored but plan to do so again. This will definitely be a consideration in the future.
 » 3 years ago, # |   -67 Is it rated?
•  » » 3 years ago, # ^ |   +38 Read the third line of post
•  » » » 3 years ago, # ^ |   +18 sponsored by Diagram!
•  » » » » 3 years ago, # ^ |   +5 So, read the 4th line. or hit ctrl+F and type rated and hit Enter. You will find the line stating that "This is a rated Codeforces round"
•  » » » » » 3 years ago, # ^ |   0 I'm sorry wut? "hit" ???
•  » » » » » 3 years ago, # ^ |   +3 Such a genius man you are! Why aren't you red?!
•  » » 3 years ago, # ^ |   +21 use your brain bro
 » 3 years ago, # |   +18 It is clashing with the online qualifying round for ACM-ICPC Regionals of all sites in India. Most of the Indian programmers will miss this. :/
 » 3 years ago, # |   +17 By the way, where is the announcement for Codeforces Round #377 ? It starts in a few hours...
•  » » 3 years ago, # ^ | ← Rev. 2 →   +23 It's here but apparently not in the front page yet.UPD : It's on front page now.
•  » » » 3 years ago, # ^ |   0 I see. Thanks!
 » 3 years ago, # |   -27 :D I wish I could change my rate +200 this contest :D
 » 3 years ago, # | ← Rev. 3 →   0 Edit: Duplicate.
 » 3 years ago, # |   -20 there is a tutorial for this contest ,right ?
•  » » 3 years ago, # ^ |   -15 i do it man
•  » » » 3 years ago, # ^ |   -7 I wrote this comment accidentally, I though it was the round 337 post. :"D
•  » » 3 years ago, # ^ |   0 yes
•  » » » 3 years ago, # ^ |   -10 I wrote this comment accidentally, I though it was the round 337 post. :"D
 » 3 years ago, # |   +1 Is there any separate registration for people residing in Canada ?
•  » » 3 years ago, # ^ |   +26 I work with Diagram. If you're already residing in Canada, just let us know in a "cover letter" via the application form or send me a note directly.
 » 3 years ago, # |   -25 This round is clashing with the online round of ACM-ICPC Regionals of all sites in India. So Most of the Indian programmers can't enjoy this.
 » 3 years ago, # |   -35 upvote me plz
 » 3 years ago, # | ← Rev. 2 →   +62 What's happened with CF? Cannot access some pages including "Main"
•  » » 3 years ago, # ^ |   +91 Someone posted blog entry http://codeforces.com/blog/entry/47858, which header includes malicious script What does this code do So in "Recent actions" we have this script executed.
•  » » » 3 years ago, # ^ |   +356
•  » » » 3 years ago, # ^ |   0 I can't open that blog entry. Why?
 » 3 years ago, # |   +3 The brand of this company is great.So I guess the T-shirt is great too.Hope my top 100 rank! To be a beautiful T-shirt's girl!
 » 3 years ago, # |   0 Too bad it conflicts with IEEE contest which happens on Saturday for 24 hours duration.
 » 3 years ago, # |   +4 How many people are qualified as being "local winners"? Is it just the number 1? Btw, you're the best Jacob
•  » » 3 years ago, # ^ |   +15 I work with Diagram. If any of the top 100 are local winners (Toronto or Montreal), we'll find some time to make this happen.
 » 3 years ago, # |   +29 Clashing with ACM ICPC India Regionals :(
 » 3 years ago, # | ← Rev. 2 →   -34 ...
 » 3 years ago, # |   +5 T Think There was Register option for this contest. But not now.
 » 3 years ago, # |   -24 hope to see good statements and new problems away of hacking :D
•  » » 3 years ago, # ^ |   -30 Congratulations you win the "Worst comment ever" prize keep up the good work.
 » 3 years ago, # | ← Rev. 2 →   -18 ­
 » 3 years ago, # |   +14 Has anyone noticed that the contest starts at 11am EDT instead of 11.05am EDT?
•  » » 3 years ago, # ^ |   +71 no problem....they will start with 5 min delay as usual :p
•  » » » 3 years ago, # ^ |   +9 OMG they delayed it.
 » 3 years ago, # |   +37 I just had some beer and feel a littie drunk, but I really don't want to miss this round, good luck to me.Does Anyone have this experience ?
•  » » 3 years ago, # ^ |   0 Not that good of an idea right? Tried that a couple times, never works out...
•  » » » 3 years ago, # ^ |   +8 Yes, mind turned slower ...
 » 3 years ago, # |   +26 I don't need a T-shirt ,, i need +200 and i'll be more happy ,thanks
 » 3 years ago, # |   0 I love combined rounds!
•  » » 3 years ago, # ^ | ← Rev. 2 →   +18 I love them too , because in combined rounds you will never see unrated accounts in top 100
 » 3 years ago, # |   +9 i am being unable to register in the round..!! :/ anyone else facing the issue??!!
•  » » 3 years ago, # ^ |   +30 What is wrong?
 » 3 years ago, # |   0 Where is the contest registration link? Is it the application to Diagram?
•  » » 3 years ago, # ^ |   +6 No, just go on "Contests" page and click on "Register".http://codeforces.com/contests/725
 » 3 years ago, # |   0 Delayed 5 min -.-
 » 3 years ago, # |   0 I wonder if div2 guys even have a shot at getting an interview call for that job opportunity, because I won't finish in top 200 (most probably).
 » 3 years ago, # |   0 unfortunately, the contest will be delayed for 5 minutes :p
 » 3 years ago, # |   +9 Score distribution?
 » 3 years ago, # |   +1 Why there is no rng_58 in the leaderboard? :)
•  » » 3 years ago, # ^ |   +5 The leaderboard only shows members that took part in at least one contest in the last six months.
 » 3 years ago, # |   -12 I couldn't access the site for half an hour or so.
 » 3 years ago, # |   -30 Number C : Poor statement. can't understand a single line.
 » 3 years ago, # |   0 My submission for C is running forever on test 2, where submissions made after my submissions are already judged. If I resubmit, I would lose points. Could you please look into it?
•  » » 3 years ago, # ^ |   +10 I think it is OK now.
 » 3 years ago, # |   +6 Really nice contest and problems!Thanks, author(s)!
 » 3 years ago, # |   +45 solution for problem E please My brain is burning
•  » » 3 years ago, # ^ | ← Rev. 2 →   +35 Key abeservation is:If you can make the greedy algorithm fail, you can do it by add just one coin. Prove it yourself. :)So we can try all the C possibilities. And since there're at most unique numbers in the solution of greedy algorithms, you can use a fenwick tree to find the largest number which can be used in greedy algorithm. This method works in .21687779
•  » » » 3 years ago, # ^ |   +3 And since there're at most sqrt(T) unique numbers in the solution of greedy algorithmsWhat numbers are you talking about?
•  » » » » 3 years ago, # ^ |   0 The coins
•  » » » » 3 years ago, # ^ |   +5 If you contract the occurrences of the numbers, and only iterate on each unique coin x1..xn then their sum(occurence*sum) <= C. Since each unique coin need to be distinct, taking 1..sqrt(C) gives the most number of coins since sum(1..sqrt(C)) ~ O(C).
•  » » » » » 3 years ago, # ^ |   0 Thank you, got it.
•  » » » 3 years ago, # ^ |   0 your implementation is actually since you query Fenwick tree in binary search
•  » » » » 3 years ago, # ^ |   0 Yes, you're right.
•  » » » » » 3 years ago, # ^ |   +3 You can reduce it to by using a BST like the built in order statistics tree.
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   0 http://codeforces.com/contest/725/submission/21696740 std::set solution runs slower than yours :(I guess it's because Fenwick tree operations' constant factors are much smaller compare to those of BST.
•  » » » » » 3 years ago, # ^ | ← Rev. 2 →   +5 Instead of using set, you can store largest value less than any number from 1 to C, then your solutions will be reduced to C * sqrt(C)
•  » » » 3 years ago, # ^ |   0 Can you give me a hint of how to prove that?
•  » » » » 3 years ago, # ^ | ← Rev. 2 →   +8 Spoiler.
•  » » 3 years ago, # ^ | ← Rev. 2 →   +14 you can iterate all the value from 1 to C, consider it the value of the coin you give to Alfred, and with each value just do brute force, the time brute force running is no more than sqrt(C), so the total complexity is C * sqrt(C), i didn't realize the second part in the contest. My friend's code : http://ideone.com/56lb0F
 » 3 years ago, # |   +9 Is greedy correct for problem D?
•  » » 3 years ago, # ^ |   +6 yes
•  » » 3 years ago, # ^ |   +3 I think it's binary search
•  » » » 3 years ago, # ^ |   0 How did you use binary search?
•  » » » » 3 years ago, # ^ |   0 I used the following (overcomplicated) approach:Sort by score, process from highest score: calculate how many balls you can spend so that you still have at least the same score as current participant. Then use binary search + two Fenwick trees to find how many participants you can delete, update answer if needed. Then add current participant's deletion cost to the trees and continue.
•  » » » » » 3 years ago, # ^ |   +3 I believe I did this and failed system test T_T (probably did something wrong)
•  » » » » » » 3 years ago, # ^ |   +13 Maybe overflow? You can't compute the sum of all numbers. Anyway, I used three BITs to avoid this (long long and double for the same thing).
•  » » » » » » » 3 years ago, # ^ |   +3 OMG you're right T_TForgot that I'm adding lots of numbers of that magnitude T_TT-shirt + Rating => Gone
•  » » » » » » » 3 years ago, # ^ |   0 Yes, I've limited sums by 2**62. It's ok since there is no subtraction. 21684744
•  » » » » » » » » 3 years ago, # ^ |   0 nice approach!
•  » » » » 3 years ago, # ^ |   0 21682840. Here is my code.
 » 3 years ago, # |   +7 how to solve D?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +12 I used heap+sort! First of all, Let's sort ballons! Then, Let's insert everybody better,than us! Then, pop the people with minimum(weight-ballons+1)! Repeat it, until we can! Sorry for my english!
•  » » » 3 years ago, # ^ |   +7 oh, I wish I thought of using a heap! I used a map with the second int counting the number of instances of the first.
•  » » » » 3 years ago, # ^ |   0 Oh, i think your solution is better!
•  » » » » 3 years ago, # ^ |   0 What about multimap?
•  » » » » » 3 years ago, # ^ |   +1 Extracting the minimum element will cost logarithmic time with both maps and multimaps, and constant time with heaps. So generally speaking a heap will be the fastest of three, but all of them will work within the time limit.
•  » » » » » » 3 years ago, # ^ | ← Rev. 2 →   0 map.begin() gets you the min element in constant time. source: http://www.cplusplus.com/reference/map/map/begin/ Edit: it is still probably slower due to map's logarithmic operations being slower, but the main benefit for heap would be it's simplicity.
•  » » » » » » » 3 years ago, # ^ |   0 Wow, I never realized that... Thanks for pointing out :) Perhaps the implementation is keeping an internal pointer to make this possible in constant time.
•  » » » » » » 3 years ago, # ^ |   0 Extracting in heap is log n (**peeking** is constant). Same as in map.
•  » » » » » 3 years ago, # ^ |   0 I could have used a multiset, but than erasing a single instance of an element is even less elegant.
•  » » » 3 years ago, # ^ |   +3 I wish I was as smart as you during the contest :) Really like your idea! I went further after contest: just use two heaps: one for better-than-us and another for worse-than-us and simple while-loop to put from one to the other to optimize current placement.
•  » » » 3 years ago, # ^ |   0 Nice approach thanks
 » 3 years ago, # |   +3 I really like D. Why don't you make B's input simpler by having a space?
•  » » 3 years ago, # ^ |   +3 It's simple enough with scanf. scanf("%I64d%c", &x, &c);It adds a bit of personality to the task if u ask me.
•  » » » 3 years ago, # ^ |   +3 That's what I did, but it took me a while to remember how to read long longs with scanf. Also, removing the ios::sync_with_stdio(false); had me resubmitting D and loosing 50 points.
•  » » 3 years ago, # ^ |   +18 It is already simple. Isn't it? long long row; char column; cin >> row >> column; 
•  » » » 3 years ago, # ^ |   0 I didn't know that works, Thanks.
•  » » » » 3 years ago, # ^ |   0 that's nice , but you must be very careful about it. note that if 'row' be double , this input '12e' will fail because 'e' is a scientific numbers notation.
•  » » 3 years ago, # ^ |   0 Just cin>>n>>s. Correct me if I'm wrong but I don't see any problem with that.
 » 3 years ago, # | ← Rev. 2 →   0 .
•  » » 3 years ago, # ^ |   +4 First time for everything man :D
 » 3 years ago, # |   +16 Well, this time I would get D if there were 2 seconds more...
•  » » 3 years ago, # ^ | ← Rev. 2 →   +37 Me too...
 » 3 years ago, # |   +5 How to solve C?
•  » » 3 years ago, # ^ |   +67 We find the repeating character. Find two indices where this character is placed: i1, i2. Find the number of characters between the repeating character: dist = i2 - i1 - 1. If number of characters between them is 0 print "Impossible", otherwise it is possible and we proceed. I look at the sequence in the following way: So, basically, in the next steps I lay the loop (which is red in the picture) on the right side. The starting and ending characters I put on the left side (starting characters — on top and ending characters on bottom).
•  » » » 3 years ago, # ^ |   +1 will be there only one repetead character?
•  » » » » 3 years ago, # ^ |   +1 Imagine that we are given a sequence of 26 characters and all english letters are in that sequence. How many repeated characters that sequence must have?
•  » » » » » 3 years ago, # ^ |   0 That was my problem. I was writing some cases with more than one repeated char, so thanks for ur explanation
•  » » » » 3 years ago, # ^ |   0 yes, only one. Because length of iven string equals to 27 and all English letters occurs at least once. So 27-26=1
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 What if there are 2 different repeating characters for example? love the drawing btw
•  » » » » 3 years ago, # ^ |   +1 read the problem statement carefully :D Each English letter occurs at least once and the input is 27 letter so we have only one repeated character
•  » » » » » 3 years ago, # ^ |   +1 missed that part... thanks a lot
•  » » » » » » 3 years ago, # ^ |   0 Me too. :(
•  » » » » 3 years ago, # ^ |   0 there are exactly 27 characters and each English letter will appear at least onceso there is exactly one repeated letter
•  » » » » 3 years ago, # ^ | ← Rev. 3 →   +5 You’re given a string s which consists of 27 upper-case English letters. Each English letter occurs at least once in s.The English alphabet has 26 letters, they tell us that every letter is going to appear at least once, then 27 — 26 = 1 letter can appear twice
•  » » » » 3 years ago, # ^ |   0 read the problem statement carefully! It says that there will be 27 characters in the input string and all 26 letters will be present there! So only one character can be repeated
•  » » » 3 years ago, # ^ |   +52 Are Codeforces problems getting harder recently? I was surprised to see this as a div1 A.
•  » » » » 3 years ago, # ^ |   +5 From my last experience, such problem is normal for Div2C/Div1A.
•  » » » 3 years ago, # ^ | ← Rev. 2 →   +13 I came up with the same solution, but you can make the implementation easier by noticing that this configuration is just the original string looped around the board (without repeating the character that appears twice). So you can just test all loops and see if there's a configuration that works: http://codeforces.com/contest/725/submission/21678250
•  » » » » 3 years ago, # ^ |   +5 Nice solution!
•  » » » » 3 years ago, # ^ |   +13 The right position in the loop is easy to calculate. Basically you put the first repeating character in the first row in the position 13-len(mid)/2, where mid is the part between two repeating characters.21674772
•  » » » » » 3 years ago, # ^ |   +13 Or even simpler: 21694212 i = s.index(c) j = i + 1 + s[i+1:].index(c) if i + 1 == j: die("Impossible") s = s.replace(c, "", 1)*3 mid = 13+(i+j)/2 print s[mid-13:mid] print s[mid:mid+13][::-1] 
•  » » » 3 years ago, # ^ | ← Rev. 2 →   0 Thank you! after contest, I implemented Problem C with this idea.and get AC.Source Code
•  » » 3 years ago, # ^ | ← Rev. 2 →   +4 First calculate the distance between the two repeated letter. Then put the letters snake-shaped.For example, if the distance is 5, then the rightmost part should be this:  -> A -> x -> x /| | / | v <- y x <- x <- x My submission here.sorry for my bad English
 » 3 years ago, # |   +13 spent too much time on C and didn't have enough time for D, didn't find an easy wa to handle the tie cases.
 » 3 years ago, # |   0 I think the statement for problem G was ambiguous : what to do when a node receive messages from its parent and one of its children at the same time ? I had WA on test 4 even with the slow code I was using to test the fast code...
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 There is the statement about this situation in the problem:"If some copy of Alice receives messages from children nodes and also receives the answer she is waiting for at the same instant, then Alice first processes the answer, then immediately continue as normal with the incoming messages."
•  » » » 3 years ago, # ^ |   0 Oh, it is my fault then. I think that this kind of problem should have examples covering all corner cases though...
 » 3 years ago, # |   +34 Sadness is when you pass E but failed C and D T_T
•  » » 3 years ago, # ^ |   0 Sadness is the contest ends just before you click submit to an accepted solution :(
 » 3 years ago, # | ← Rev. 4 →   +63 Solve E and gain 1090 points. I love this game but not rating! :) And hello Div.2. :)
 » 3 years ago, # |   0 sad... Failed System Test on B&C
 » 3 years ago, # |   +2 Can someone explain the solution for C ? Thanks.
•  » » 3 years ago, # ^ | ← Rev. 3 →   +2 It's only impossible if there are two of the same letters next to each other. Also it's easily understandable that there will be exactly one letter that appears twice in the input string, since each letter must appear at least once and there's only one extra letter.Let's say that this was the letter 'A'. Then the string looks like this:s1 + "A" + s2 + "A" + s3I got AC by constructing the matrix like this:3333333A222111111111222It's always possible to get the input string by starting at the left start of the 1s, going right, taking 'A', getting the 2s by going right then down then left then back to 'A', then going left (and maybe down and right) to take all 3s.Of course, s1 and s3 are of varied length and can even be empty, but then simply make the one that's too long "spill" into the row above or below. Also you have to be careful to write the string s1 in reverse order.
•  » » 3 years ago, # ^ |   0 look at this comment
 » 3 years ago, # |   -14 How did my solution for E pass system tests =)))))) I'm pretty sure it would get TLE tho xDthis one
 » 3 years ago, # |   0 Why can't we see others solution? or is it just me?
 » 3 years ago, # |   +3 No upsolving or something wrong with me? :)
•  » » 3 years ago, # ^ |   0 Not only you, no one can submit.
•  » » 3 years ago, # ^ |   0 Maybe after the rating updated ?
 » 3 years ago, # |   +25 :)
•  » » 3 years ago, # ^ |   0 feelsbadman
 » 3 years ago, # |   +3 Why we can't submit for practice ?
•  » » 3 years ago, # ^ |   -10 I think they are still preparing for that to be for practicing.
 » 3 years ago, # |   0 Is it just me or no one can see others' solutions? :/
•  » » 3 years ago, # ^ |   0 Not yet. It often only gets enabled after the ratings update.
•  » » » 3 years ago, # ^ |   0 ok! :) Just have to wait then!
 » 3 years ago, # |   0 worst problems ever no idea just code
•  » » 3 years ago, # ^ |   0 I agree with you.
 » 3 years ago, # |   +127 :(
•  » » 3 years ago, # ^ |   0 Tough luck
 » 3 years ago, # |   0 Is F a greedy? I cannot submit now，plz someone who got F accepted tell me，thank you！
•  » » 3 years ago, # ^ | ← Rev. 2 →   0 (I didn't AC it)I think it is: always take the photo with the biggest sum of A and B. But the tricky part is to, at each point in time, check if it's possible that both players want to pass their turns, ending the game early. I'm pretty sure I've got the DP for this down, but I couldn't complete it during contest.
•  » » 3 years ago, # ^ |   +15 Yep. It can be done greedily if you regard the value of a card as a+b since the scores that the two players get are a,0 and 0,b in both cases, where the difference would be a and -b respectively. So you can set this value for each card and greedily select the pictures.Of course you still have to handle some other cases :)
•  » » » 3 years ago, # ^ |   0 Hey, could you please explain they way you derived this strategy ?
•  » » » 3 years ago, # ^ |   0 Thank you,I've got F passed.From my point of view,the game is a little bit like the go chess,because both sides need to correctly calculate every step's value and choose the most valuable one.
•  » » » » 3 years ago, # ^ |   0 Hey, could you explain the idea of your solution?
•  » » » » » 3 years ago, # ^ |   +3 consider a quadruple x,y,xx,yy mentioned in the description,there are three condition: 1.x<=yy&&y<=xx. In this contion,the one who goes first suffers losses.So no one goes first,and this condition makes no sense. 2.doesn't satisfy the 1st contion,but satisfy x+yyy or y>xx),but he will get more profits only if he goes second,but the opponent will just let it be .And if the one who is to get profits want to "cash his check",he has to offer to go first.As is explained above, ans+=x-yy(or xx-y). 3.other conditions. We can assume the value as x+y(if the first is done,xx+yy),and apply a greedy strategy that obviously choosing the most valuable one from all the 3rd contions(if this one is the first then add the second into the priority_queue)one by one,using a priority_queue. Sorry for my poor English and wish you can get AC.
 » 3 years ago, # | ← Rev. 3 →   +20 almost got jcvb
•  » » 3 years ago, # ^ |   +7 what a pity
•  » » 3 years ago, # ^ |   0 Off night :D (It's night for me)
•  » » 3 years ago, # ^ |   0 I don't believe it.
•  » » » 3 years ago, # ^ |   +90 Yes believe it!
•  » » » » 3 years ago, # ^ |   0 Do you remember me, my friend?
•  » » » » 3 years ago, # ^ |   +23 Wow! You have -296!
•  » » 3 years ago, # ^ |   +181
 » 3 years ago, # |   +3 when I will be able to submit my solution for problem C. When problems will be added to problemset
 » 3 years ago, # |   0 Yes...I'm back to Specialist :)
 » 3 years ago, # |   +3 Why did my submissions get ignored!? I'm 100% sure that I have written ALL of the code MYSELF. What's wrong!?
•  » » 3 years ago, # ^ |   +5 did u use ideone or any other public online compiler?
•  » » » 3 years ago, # ^ |   0 Not really. I compiled all my programs with g++ (Codeblocks IDE) on my local PC...
 » 3 years ago, # |   +10 why cant i practice now
 » 3 years ago, # |   0 cute problems :)
 » 3 years ago, # | ← Rev. 2 →   +10 Why so delay ? Why we can't submit the solution till now ? When the problems will be added to problemset ? Why till now, we can't see other's code ? Is there any reason for this ?Update: Now it's ok :)
 » 3 years ago, # | ← Rev. 2 →   +1 http://codeforces.com/contest/725/submission/21684455 what is 7th testcase,why its showing wrong answer for 7th testcase please help
•  » » 3 years ago, # ^ |   0 I didn't actually read your code. Just tested it. time for 1st attendant and time for 2nd attendant should be the equal. For example you got 6e=25 so that 8e=25 but your output is 31.
•  » » » 3 years ago, # ^ |   +1 thanks
•  » » » » 3 years ago, # ^ |   0 You're welcome :)
 » 3 years ago, # | ← Rev. 3 →   +13 please .. why all my submissions skipped after the contests ?? .. during the contest I changed my laptob and IP is that relative ?
 » 3 years ago, # |   +29 wrote 26 instead of 27 in problem C, dropped ~350 rank
•  » » 3 years ago, # ^ |   0 Poor you :)
 » 3 years ago, # | ← Rev. 2 →   0 Rating is calculated separately for divisions?
 » 3 years ago, # |   +8 WA: for (int i = 0; i < 12; i++) AC: for (int i = 0; i < 13; i++) Lesson well learnt. :''D
 » 3 years ago, # |   0 I don't understand problem A, can someone tell me, how this statement make sense?"In the second sample, any starting position will result in the ball falling from the field."I'm still under the impression that is a typo, where it should say, any starting position will not result in the ball falling from the field.
•  » » 3 years ago, # ^ |   +8 I dont think it is a typo at all
•  » » 3 years ago, # ^ |   +1 In that particular example, since the field is >>>>>, the ball will always fall from the field, no matter where it initially starts (will always go to the right)
•  » » 3 years ago, # ^ |   0 I don't think this matter anymore, but I just realized that the 2nd problem was >>>>> while I thought it was the >><<.
 » 3 years ago, # | ← Rev. 3 →   0 can D be solved using Segment tree ?
•  » » 3 years ago, # ^ |   0 Yes but you can use simpler structures. For example heaps or sets.
 » 3 years ago, # |   +25 Are editorials coming ?
•  » » 3 years ago, # ^ |   +2 Editorial always comes 'soon' enough.
 » 3 years ago, # |   +8 Moose!It's like Canadian cattle eh?
 » 3 years ago, # |   0 Pretests of B cover all cases except for where n = 4k + 3, leaving opportunities for hacking and necessity for system test, while maintaining a reasonbly strong testset. +1 for this setting (๑•̀ㅂ•́)و✧
 » 3 years ago, # |   +3 I forgot to write "+1" in my D submission so I got a WA. I won't forgive myself...
•  » » 3 years ago, # ^ |   0 I did something like that except it was in C. T_T
 » 3 years ago, # | ← Rev. 2 →   0 I am thinking of solving problem G in this way, but I am not sure if this is correct. Build the heavy-light decomposition chains. O(N) Sort query by increasing pair(time+depth[initiator], initiator_id). O(MlogM) Upon query, ask the expected time that you will reach Bob, use the segment trees to binary search for the position you will get answer from. Each takes O((logN)^3) Update the segment trees, set the value of each node on the path to (time of response + depth[Node]), which is a geometric sequence(*Edit: arithematic sequence). Each takes O((logN)^2)? I have heard that it is possible to use lazy propagation and keeping other values to maintain geotric sequences in a segment tree but I have never implemented it... Any thoughts?
•  » » 3 years ago, # ^ |   0 1,2 are correct. 3 and 4 can both be done in O((log n)²) by keeping the right information in the segment tree. It is an arithmetic sequence, not a geometric one.
•  » » » 3 years ago, # ^ |   0 Thanks for pointing it out. =]
 » 3 years ago, # | ← Rev. 3 →   0 Problem E:10015What is the answer?
•  » » 3 years ago, # ^ |   0 You can assume that the answer, if it exists, is positive. In other words, Alfred's algorithm will work if Bob doesn't give him any coins.The sets are guaranteed to have an answer if nothing is added.
 » 3 years ago, # |   0 Where to find the answer of the problems for this contest?
 » 3 years ago, # | ← Rev. 2 →   0 Problem D: 9 4 70 32 56 32 65 77 78 5 29 72 100 0 55 42 52 66 72 Can anyone explain this to me,why this test is 7 but we can give 77 78 2 balloons right? So it should be 6. Thank you!
•  » » 3 years ago, # ^ | ← Rev. 4 →   +4 Final rankings:1, 72 1002, 66 723, 42 524, 32 564, 32 65 (UPD: Dang it formatting)6, 5 297, (4-2) 708, 0 55I think you misunderstood the statement and ranked 6~8 incorrectly, note that "It means that one's place is equal to the number of teams with more balloons, increased by 1."
•  » » » 3 years ago, # ^ |   0 I thought 32 56 and 32 65 are tied so they are at the same ranked 4 @_@.
•  » » » » 3 years ago, # ^ |   0 I got it! thank you :D
 » 3 years ago, # |   0 When will the problems be available for practice?
•  » » 3 years ago, # ^ |   0 They should be right now, but I am not sure if that's an issue for some participants. I have also had this issue before, after a day it should resolve itself.
 » 3 years ago, # |   +19 Will the editorials be published?
 » 3 years ago, # |   +20 This is the first time I win a prize on Codeforces, so I want to ask people here a few things. How long after the contest will the sponsor contact me? And how long does it usually take until I can receive my prize?
•  » » 3 years ago, # ^ | ← Rev. 3 →   +9 Congratulations!!
•  » » » 3 years ago, # ^ |   0 Thank ^^"
•  » » 3 years ago, # ^ |   +8 Any news about the prize??
•  » » » 3 years ago, # ^ |   +8 Not yet. I received some messages from other contestants, and they also said that there hadn't been any news since then.
 » 3 years ago, # |   +12 When will be editorial???
 » 3 years ago, # |   +11 Editorial please.
 » 3 years ago, # |   +5 How is this possible that points drain was not adjusted? This is by far not the first contest coordinated by GlebsHP with longer duration and few of them already had adjusted drain. Not adjusted drain is complete cancer, adjusting drain should have already became a habit without any exceptions.
 » 3 years ago, # |   +15 Did anyone receive the T-shirt? As the last line of the blog mentioned, I have been contacted (multiple times) but the T-shirt has still not arrived. :(