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
About Diagram
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.me/blog/entry/47974
"The top 100 competitors will get a Diagram T-shirt."
Top 100 competitors in each division?
Are you joking?
My question too...
Also in the contest page it's div1-div2 combined...
The post has been updated: now members of both divisions will participate in the same contest.
I won't forgive you... :/
Got down-votes cause of you :/
Someone want more downvotes... I read somewhere that downvote can have negative impact on behavior... Seems true.
Then all div1 users would create div2 fakes
Does Diagram or your companies offer any internship opportunities for undergraduate students? If yes, how can I apply for it?
<3
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.
Is it rated?
Read the third line of post
sponsored by Diagram!
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"
I'm sorry wut? "hit" ???
Such a genius man you are! Why aren't you red?!
use your brain bro
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. :/
By the way, where is the announcement for Codeforces Round #377 ? It starts in a few hours...
It's here but apparently not in the front page yet.
UPD : It's on front page now.
I see. Thanks!
Edit: Duplicate.
there is a tutorial for this contest ,right ?
i do it man
Is there any separate registration for people residing in Canada ?
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.
А условия будут только на английском?
Условия будут доступны как на русском так и английском языках.
What's happened with CF? Cannot access some pages including "Main"
Someone posted blog entry http://codeforces.me/blog/entry/47858, which header includes malicious script
So in "Recent actions" we have this script executed.
I can't open that blog entry. Why?
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!
Too bad it conflicts with IEEE contest which happens on Saturday for 24 hours duration.
How many people are qualified as being "local winners"? Is it just the number 1? Btw, you're the best Jacob
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.
Clashing with ACM ICPC India Regionals :(
...
T Think There was Register option for this contest. But not now.
hope to see good statements and new problems away of hacking :D
Congratulations you win the "Worst comment ever" prize keep up the good work.
Has anyone noticed that the contest starts at 11am EDT instead of 11.05am EDT?
no problem....they will start with 5 min delay as usual :p
OMG they delayed it.
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 ?
Not that good of an idea right? Tried that a couple times, never works out...
Yes, mind turned slower ...
I don't need a T-shirt ,, i need +200 and i'll be more happy ,thanks
I love combined rounds!
I love them too , because in combined rounds you will never see unrated accounts in top 100
i am being unable to register in the round..!! :/ anyone else facing the issue??!!
What is wrong?
Where is the contest registration link? Is it the application to Diagram?
No, just go on "Contests" page and click on "Register".
http://codeforces.me/contests/725
unfortunately, the contest will be delayed for 5 minutes :p
Score distribution?
Why there is no rng_58 in the leaderboard? :)
The leaderboard only shows members that took part in at least one contest in the last six months.
Number C : Poor statement. can't understand a single line.
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?
I think it is OK now.
Really nice contest and problems!
Thanks, author(s)!
solution for problem E please
My brain is burning
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
And since there're at most sqrt(T) unique numbers in the solution of greedy algorithms
What numbers are you talking about?
The coins
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).
Thank you, got it.
your implementation is actually
since you query Fenwick tree in binary search
Yes, you're right.
You can reduce it to
by using a BST like the built in order statistics tree.
http://codeforces.me/contest/725/submission/21696740
std::setsolution runs slower than yours :(I guess it's because Fenwick tree operations' constant factors are much smaller compare to those of BST.
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)Can you give me a hint of how to prove that?
Spoiler.
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
Is greedy correct for problem D?
yes
I think it's binary search
How did you use binary search?
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.
I believe I did this and failed system test T_T (probably did something wrong)
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).
OMG you're right T_T
Forgot that I'm adding lots of numbers of that magnitude T_T
T-shirt + Rating => Gone
Yes, I've limited sums by 2**62. It's ok since there is no subtraction. 21684744
nice approach!
21682840. Here is my code.
how to solve D?
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!
oh, I wish I thought of using a heap! I used a map<int,int> with the second int counting the number of instances of the first.
Oh, i think your solution is better!
What about multimap?
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.
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.
Wow, I never realized that... Thanks for pointing out :) Perhaps the implementation is keeping an internal pointer to make this possible in constant time.
Extracting in heap is log n (**peeking** is constant). Same as in map.
I could have used a multiset, but than erasing a single instance of an element is even less elegant.
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-usand another forworse-than-usand simple while-loop to put from one to the other to optimize current placement.Nice approach thanks
I really like D. Why don't you make B's input simpler by having a space?
It's simple enough with scanf. scanf("%I64d%c", &x, &c);
It adds a bit of personality to the task if u ask me.
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.
It is already simple. Isn't it?
I didn't know that works, Thanks.
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.
.
First time for everything man :D
Well, this time I would get D if there were 2 seconds more...
Me too...
How to solve C?
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).
will be there only one repetead character?
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?
yes, only one. Because length of iven string equals to 27 and all English letters occurs at least once. So 27-26=1
What if there are 2 different repeating characters for example? love the drawing btw
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
missed that part... thanks a lot
Me too. :(
there are exactly 27 characters and each English letter will appear at least once
so there is exactly one repeated letter
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
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
Are Codeforces problems getting harder recently? I was surprised to see this as a div1 A.
From my last experience, such problem is normal for Div2C/Div1A.
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.me/contest/725/submission/21678250
Nice solution!
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
Or even simpler: 21694212
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:
My submission here.
sorry for my bad English
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.
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...
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."
Oh, it is my fault then. I think that this kind of problem should have examples covering all corner cases though...
Sadness is when you pass E but failed C and D T_T
Sadness is the contest ends just before you click submit to an accepted solution :(
Solve E and gain 1090 points. I love this game but not rating! :)
And hello Div.2. :)
sad... Failed System Test on B&C
Can someone explain the solution for C ? Thanks.
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" + s3
I got AC by constructing the matrix like this:
3333333A222
111111111222
It'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.
look at this comment
How did my solution for E pass system tests =)))))) I'm pretty sure it would get TLE tho xD
this one
No upsolving or something wrong with me? :)
Not only you, no one can submit.
:)
Why we can't submit for practice ?
Is it just me or no one can see others' solutions? :/
Not yet. It often only gets enabled after the ratings update.
ok! :) Just have to wait then!
worst problems ever no idea just code
I agree with you.
:(
Tough luck
Is F a greedy? I cannot submit now，plz someone who got F accepted tell me，thank you！
(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.
Yep. It can be done greedily if you regard the value of a card as
a+bsince the scores that the two players get area,0and0,bin both cases, where the difference would beaand-brespectively. So you can set this value for each card and greedily select the pictures.Of course you still have to handle some other cases :)
Hey, could you please explain they way you derived this strategy ?
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.
Hey, could you explain the idea of your solution?
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+y<xx+yy.In this condition,one will definitely get profits(as x>yy 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.
almost got jcvb
what a pity
I don't believe it.
Yes believe it!
Do you remember me, my friend?
Wow! You have -296!
when I will be able to submit my solution for problem C. When problems will be added to problemset
Why did my submissions get ignored!? I'm 100% sure that I have written ALL of the code MYSELF. What's wrong!?
did u use ideone or any other public online compiler?
Not really. I compiled all my programs with g++ (Codeblocks IDE) on my local PC...
why cant i practice now
cute problems :)
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 :)
http://codeforces.me/contest/725/submission/21684455 what is 7th testcase,why its showing wrong answer for 7th testcase please help
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.
thanks
please .. why all my submissions skipped after the contests ?? .. during the contest I changed my laptob and IP is that relative ?
wrote 26 instead of 27 in problem C, dropped ~350 rank
Rating is calculated separately for divisions?
WA:
for (int i = 0; i < 12; i++)AC:for (int i = 0; i < 13; i++)Lesson well learnt. :''DI 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.
I dont think it is a typo at all
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)
can D be solved using Segment tree ?
Yes but you can use simpler structures. For example heaps or sets.
Are editorials coming ?
Editorial always comes 'soon' enough.
Moose!
It's like Canadian cattle eh?
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 (๑•̀ㅂ•́)و✧
I forgot to write "+1" in my D submission so I got a WA. I won't forgive myself...
I did something like that except it was in C. T_T
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?
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.
Thanks for pointing it out. =]
Problem E:
100
1
5
What is the answer?
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.
Problem D:
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!
Final rankings:
1, 72 100
2, 66 72
3, 42 52
4, 32 56
4, 32 65 (UPD: Dang it formatting)
6, 5 29
7, (4-2) 70
8, 0 55
I 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."
When will the problems be available for practice?
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.
Will the editorials be published?
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?
Congratulations!!
Thank ^^"
Any news about the prize??
Not yet. I received some messages from other contestants, and they also said that there hadn't been any news since then.
When will be editorial???
Editorial please.
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.
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. :(