By ItsNear, 6 years ago, translation, ,

MemSQL is excited to announce Start[c]UP 2.0 – the second annual programming competition hosted by Codeforces with an onsite at MemSQL HQ in San Francisco, California.

Start[c]UP 2.0 consists of two rounds. Round 1 is online and takes place on July 27th at 10:00 AM PST. Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. There are no eligibility restrictions to participate in the round. The round will be 2.5 hours long, and will be rated.

Round 2 takes place on August 10th at 10:00 AM PST, consists of 6 problems, and uses regular Codeforces rules. The complexity of the problems is higher than a regular Codeforces round, the round will be 3 hours long, and will be rated. Only people who finished in the top 500 in Round 1 can participate. The top 100 in round 2 will receive a Start[c]UP 2.0 T-shirt.

For Silicon Valley residents, MemSQL will be hosting up to 25 people on-site during the second round. The winner of the on-site round will be awarded a special prize.

UPDATE: first round will feature 6 problems, not five as it was announced earlier.

• +592

 » 6 years ago, # |   +25 Note that July 26th is also the date of TCO round 3A — it'd be good to avoid collisions as early as possible.
•  » » 6 years ago, # ^ |   0 Yes, thank you for bringing it up. Round one will actually be on Sunday, July 27th. Original post had a wrong date.
•  » » 5 years ago, # ^ |   +11 Thank you for reminding me, that today will be TCO. If it weren't for you, I would probably forget :P (not that TopCoder should do that...)
 » 6 years ago, # |   -10 Round 1 follows regular Codeforces rules and consists of 5 problems. For this round, the complexity of the problems will be comparable to a regular Codeforces round. Division 1 or 2?
•  » » 6 years ago, # ^ |   +5 division 1 link
 » 6 years ago, # | ← Rev. 2 →   -37 Deleted.
 » 6 years ago, # |   0 sorry if this seems like a stupid question, but what does the [c] in Start[c]UP signify?
•  » » 6 years ago, # ^ |   +8 It would not be a "cUP" had it not been the "[c]".
•  » » 6 years ago, # ^ |   +37 This is rounded speed of light.
•  » » » 6 years ago, # ^ |   +23 Yes, MemSQL is famous for its fast.
•  » » 5 years ago, # ^ |   +7 if we remove "[c]", we have StartUP. I don't know if it is right or wrong.
•  » » » 5 years ago, # ^ |   -9 this is actually one of the things i wanted to know when i asked the question. :)
 » 6 years ago, # |   +9 "**The top 100 in round 2 will receive a Start[c]UP 2.0 T-shirt.**" I like it :)
 » 6 years ago, # |   0 No unofficial participation in round 2 for those who didn't finish in top 500 in round 1?
•  » » 6 years ago, # ^ |   +11 As far as I know Codeforces allows one to participate unofficially in any round (same as division one contestant can participate in division two rounds). We will not intentionally disable this functionality.
•  » » » 6 years ago, # ^ |   +24 Why do you set such strange top-500 restriction for online version of second round? For example I can't participate in first round, so you force me skip both rounds. It is very easy to reach top-500, so it is only about could you participate in the round or not.
•  » » » » 6 years ago, # ^ |   +36 It is very easy to reach top-500 i think this is disrespectful to the people who won't make it to the top 500
•  » » » » » 6 years ago, # ^ |   +16 Sorry if I offended anyone. And I am sure they want officially participate in the second round too.P.S. I changed my flight, so I can participate, but still don't understand logic of organizers. It is not gcj with huge amount of participants, and it doesn't affect onsite at all.
•  » » » » » » 6 years ago, # ^ |   +41 I changed my flight, so I can participate maybe u could add this to You know you are a programming competitions addict when ... ;)
•  » » » » » » » 6 years ago, # ^ |   +13 Contest wasn't main reason =)
•  » » » » » 5 years ago, # ^ |   +7 I'm sorry for whoever that stands in 501st place :/
•  » » » » » » 5 years ago, # ^ |   +5 so sad for terris and poopi. they missed out by just 4 and 6 points respectively. :(
•  » » » » » » » 5 years ago, # ^ | ← Rev. 3 →   +32 Oh, Thanks. I was very bad today, but really I prefer to be at 600th place or more instead of 502th :) It isn't nice but I'm hopeful that organizers find at least two cheater in places 1 to 501 :)
•  » » » » 5 years ago, # ^ |   +5 I hope I will be able to say "It is very easy to reach top-500" in the future.
•  » » » » 5 years ago, # ^ |   +11 I agree with the first statement of course. What's the point of the restriction of top 500? If the system can bear the load of 1st round then obviously it could bear the pressure if all are advanced so there is no point of top 500 thing from the point of system.But according to the 3rd sentence, if It is very easy to reach top-500, so it is only about could you participate in the round or not., then all the (1200 and counting) participants/registrants will reach top 500? Oh, but pigeonhole principle must disagree.
•  » » » » » 5 years ago, # ^ |   -14 then all the participants will reach top 500? Oh, but pigeonhole principle must disagree. what if 1000 participants all get same score, and all take the 500-th place? :D
•  » » » » » 5 years ago, # ^ |   0 maybe two pig on one hole :/
•  » » » 6 years ago, # ^ |   +12 I guess main point of question was about rated participation (not like unofficial participation for div1 contestants in div2 rounds). For example, Croc Champ 2013 — Round 2 was rated event both for guys who qualified from round 1 and for those who did not; moreover, there was also Croc Champ 2013 — Round 2 (Div. 2 Edition) — rated event for div2 users.
•  » » » 5 years ago, # ^ |   0 What happens to ratings when one participates unofficially though?I seem to recall that when VK-cup was on CF, unofficial participants still factored into the ratings pool. Will that be the case here?
•  » » » » 5 years ago, # ^ |   +8 Last year it was a regular CF round for all participants in terms of rating.
 » 6 years ago, # |   -37 where can i get the competition
 » 6 years ago, # |   -20 July 27th??!! That's the first day of NOI~~!!
 » 6 years ago, # |   0 Is it rated??
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 Yes, both rounds will be rated. I updated the post with this information.
 » 6 years ago, # |   +5 It is said that both round will follow regular Codeforces rules, while first will last 2,5h and second 3h, I think you should mention this in an announcement.
•  » » 6 years ago, # ^ |   0 Updated the post, thanks for bringing this up.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +8 Note that with last two changes language versions became out of sync.
•  » » » » 6 years ago, # ^ |   +8 And with the very last change they are in sync again :o)
 » 5 years ago, # |   0 When is the final round? I wish if you can announce this as early as possible. I live near to San Francisco, and I was invited to the final last year but I couldn't make it because I was outside the US at the contest's time.
•  » » 5 years ago, # ^ |   +6 Round 2 is a final. And it's on 10th of August
•  » » » 5 years ago, # ^ |   +3 Thanks! Sorry, I missed that.
 » 5 years ago, # |   +21 So late in such countries as China or Japan... The previous rounds are interesting. What a pity!:(
 » 5 years ago, # |   +1 OMG! It is 1 a.m. Monday in China...:D end at 3:30... rating updated at about 4... then go to bed... And at 7 a.m I should go to the railway station and go to school. The train will cost me 8 hours... Monday is too busy for me to have a rest! Amazing Monday!
•  » » 5 years ago, # ^ |   0 Are you kidding? It's summer now — who's studying in July?
•  » » » 5 years ago, # ^ |   0 But according to my parents' opinion, if I want to grow taller, I should go to bed early... T_T
•  » » » » 5 years ago, # ^ |   +3 you can go to bed 2 hours earlier than usual, that means your sleep time of a whole day is the same.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 And when I fall asleep the clock will wake me up... Anyway it is an acceptable idea:)
•  » » » 5 years ago, # ^ |   +17 Because I feel boring staying at home in summer holiday. And at home I must cook dinner for myself owing to my parents always not coming back home for dinner. After friends and classmates of middle school meeting, I have nothing to do but training coding skills. Home is not a good place to train. I think I would better go to school.
•  » » » » 5 years ago, # ^ |   0 Which city are you from?
•  » » » 5 years ago, # ^ |   0 Chinese students are. TAT
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I don't know about China, but it's not so unusual that we still have class in July in Japan. My friends in Japan are now taking the final exams! (In Japan, school starts in April, and the first semester often ends in July.)
•  » » 5 years ago, # ^ |   +8 I catched math big god wow!
 » 5 years ago, # |   0 Oh No~ 10:00AM PST， 1:00AM BEIJING
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Yes ~~~(T.T)~~~~ and 7 p.m ~ 9 p.m.in Beijing Sunday,is the bestcoder round#2...in hdu
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Hey, are you both from China?
•  » » » » 5 years ago, # ^ |   0 Yep... there are a lot of Chinese acmers in Codeforces~
•  » » » » » 5 years ago, # ^ |   0 I'm from China, too.
•  » » » » » » 5 years ago, # ^ |   0 I guess too~, People's Republic of China Jiang Su Wang Tianyi...Nice to meet you~are you a middle school student? Or a university student?
•  » » » » » » » 5 years ago, # ^ |   0 Middle school, Nanjing Foreign Languages School.
•  » » » » » » » » 5 years ago, # ^ |   0 aha, so you are a noiper~
•  » » » » » » » » » 5 years ago, # ^ |   0 yeah
•  » » » » » » » » 5 years ago, # ^ |   0 Me too~I'll study in Nanjing Foreign Languages School soon~
•  » » » » » » » » » 5 years ago, # ^ |   0 Wow! Congratulations!
•  » » 5 years ago, # ^ |   +7 I am luckier a little. Converted TimeHanoi, Vietnam00:00 ICTMonday, 28 July 2014
 » 5 years ago, # | ← Rev. 2 →   0 Oh, it's 18:00 on Sunday in London, but 1:00 on Monday in Beijing!!!
 » 5 years ago, # |   0 What is the programming language I can use in this competion?
•  » » 5 years ago, # ^ |   +12 Any language CodeForces supports.
•  » » 5 years ago, # ^ |   +9 According to codeforces rules the list of supported languages is: С/С++ Delphi/Pascal Java С# Python Ruby PHP OCaml Haskell Perl Scala D Go
 » 5 years ago, # |   0 Wow I have always wanted a Start[c]UP 2.0 t-shirt! Very intriguing prize! Good luck to all participants as I am at camp and will not be able to participate.
 » 5 years ago, # |   0 the complexity of the problems will be comparable to a regular Codeforces roundRegular Div1 or regular Div2?
•  » » 5 years ago, # ^ |   -6 for all.
 » 5 years ago, # |   +1 Registration is running, but it's "Private Registration" !!! What's going on!?!??! :D
 » 5 years ago, # | ← Rev. 2 →   +1 When I try to register it says — "The contest does not allow self registrations". Edit: Thanks, it is fixed.
 » 5 years ago, # |   +1 Can people in div 2 participate in this contest and be qualified for round 2 if they come in top 500 ??
•  » » 5 years ago, # ^ |   +4 Yes, division does not matter for this event.
 » 5 years ago, # |   +3 Just noticed that logo of memsql is very similar to that of Mumbai Indians, one of the Indian Premier League teams.
 » 5 years ago, # |   0 Is this for DiV 1 or DiV 2 ?
•  » » 5 years ago, # ^ |   0 May be Div 1, becouse it create "Memsql"?
•  » » 5 years ago, # ^ |   0 "There are no eligibility restrictions to participate in the round". It is open to both the divisions.
•  » » » 5 years ago, # ^ |   0 I meant it difficult hardly for div2. I think.
•  » » » » 5 years ago, # ^ |   +3 if you think that it will be hard for you. you can not write it.
•  » » » » 5 years ago, # ^ |   +12 We believe that participants from Div2 will still enjoy the round.
•  » » » » » 5 years ago, # ^ |   +6 Thanks for morale boosting :D
•  » » » » » 5 years ago, # ^ |   +4 seriously? sir! :(
•  » » » » » 5 years ago, # ^ |   0 I believed the same, before the contest.
•  » » » » » » 5 years ago, # ^ |   0 That means you qualified for the second round. If that's really the case truly- Great spirits and congrats :).
•  » » » » » » » 5 years ago, # ^ |   0 I used the word "before", not "after".
 » 5 years ago, # |   +13 we are muslims we will be having breakfast as it is the last day in holy Ramadan :) 27th
•  » » 5 years ago, # ^ | ← Rev. 5 →   +8 Yeah , this contest will start exactly at our iftar time in Syria. however , I still want to participate.BTW, happy feast tomorrow to you and all muslims!
•  » » » 5 years ago, # ^ |   0 thank u and happy feast to you too i participate in it but after nearly one hour after beginning
 » 5 years ago, # |   0 i like the logo ^_^
 » 5 years ago, # |   +1 The contest will be rated for both div1 and div2 participants?
•  » » 5 years ago, # ^ |   0 Yes it would be rated for both .
 » 5 years ago, # |   0 Good luck everybody!
 » 5 years ago, # |   0 Anyone can tell score of problems?
 » 5 years ago, # |   +18 This contest start at the same time of (Iftar) It will add another 2.5 hour to 16 hour without eating :D :D
•  » » 5 years ago, # ^ |   +12 I'll do the same :'D this must be added to "You know you are a competitive programmer when .." :D
 » 5 years ago, # |   -12 I don't think will have ocasion to continue with round 2
 » 5 years ago, # |   0 contest is not simple !
 » 5 years ago, # |   +4 How was problem C to be solved?
 » 5 years ago, # |   +18 How to solve problems B, C, D, E, F ?
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 For B, most probably the zig zag pattern made by (0,1) (n,m) (0,0) and (n,m-1) was the 4th one to be checked. The other 3 were only X-axis, only Y-axis and the 2 diagonal-one maximum side pattern. This passed pretests. Not sure though. System tests would tell us better. --- Nope, failed systests -- The method is right. Mine failed because of a typo :P
 » 5 years ago, # |   0 Pretests were very weak again! Lots of solutions on B, C, D will fail.........:SS
•  » » 5 years ago, # ^ |   +12 I see this as good thing. I love to hack! :D
 » 5 years ago, # |   +53 Contest finished! But personally, I didn't like the idea of putting the arrays of names in problem A in sample test explanation place; because I think many people (including myself) do not check the explanation when they understand the statement. Maybe it was better if they were higher.
 » 5 years ago, # |   0 Cmon, place your bets! Who thinks this solution will pass the final tests? Hurry up!7269849
•  » » 5 years ago, # ^ |   0 Not allowed to view the submission yet.
 » 5 years ago, # | ← Rev. 2 →   +6 I got a kind of stupid solution at B and got hacked. I passed the hack 3 seconds before end of constest. :)) I hope it passed.Edit: It passed. :)) Thanks to the hacker.
 » 5 years ago, # |   0 I scared I will get down rating !
 » 5 years ago, # |   0 Is there any particularly tricky corner case for problem B?I see many successful hacks, but I can't come up with any special case.
 » 5 years ago, # |   +8 Running java programs with -Xmx512m and ML 256m is evil. I've spent most of the contest trying to make sure that my E fits in ML regardless of GC behavior :(
•  » » 5 years ago, # ^ |   0 Why not use "Off heap" memory? No GC, smaller memory footprint.
•  » » » 5 years ago, # ^ |   +12 I don't know much about off-heap memory, but I actually need GC functionality. The problem is as follows. With an implementation of suffix trees which I use (nice, readable and object-oriented, not the horror from e-maxx), total memory which is really used is pretty close to ML. Since there is Xmx512m option, theoretically nothing prevents java from growing it (by a constant factor) above ML (it thinks that it has 512m available, so it can decide to allocate a bit more in advance).So I decided to use an optimization: instead of Node[alphabetSize] store list of pairs (char, Node) until it grows to some constant, and then free it and use full-sized array. However, my calculations show that if GC does not reuse the memory which was freed, theoretically it is again possible to go dangerously close to ML (on logarithmic scale).Anyway experiments show that even my first submission passes all tests with "memory used" 188400 Kb. Maybe I'm overly paranoid, but I want my solution to be guaranteed to pass, not just pass by luck. And IMO setting "Xmx" to match actual ML would be a very good idea.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   0 Some time ago, i experimented with some off-heap technics on CF and Timus and found that it's possible significantly to speedup program and reduce memory usage (some times to zero KB, may be it is fail of judge ML check system) with thousands of objects without full rejection of OOP-code style.I even had a desire to write an article about it :-)
 » 5 years ago, # |   0 contest really hard, hard and very hard (with me)
 » 5 years ago, # | ← Rev. 3 →   -77 Difficulty of problems, my impression:A,B — div2 AC,D — div1 B (I find D easier than C)E,F — div1 D-EYet another situation (after Zepto Code Rush) where the problems are split into easy and hard ones, and time is the main tiebreaker on the easy ones. Although I don't know how many pretests there are, so I can fail on any of B,C,D during the systest.I can write it in bold caps: MY IMPRESSION. Also, before systest.
•  » » 5 years ago, # ^ |   0 What was the approach for problem B ?
•  » » » 5 years ago, # ^ | ← Rev. 4 →   -10 I can't believe it -.-I got AC after contest ended. Two lines of code and it was fixed!There is a little 'hack' that I like to use. Watch others submissions AC's and how much system resources they use... When I saw some solutions using a lot of memory then I figured out it MIGHT not be an easy one line solution.My approach: Fix two points (0,0) and (n,m). You can see that it must be included in the optimal solution. Then you have two points to select among 4000. It's not wise to choose a point inside the rectangle... So choose two distinct points that lies in the border (that's up to 4000 points!). So you can run O(4000^2) to pick those points. For each set of 4 points you still have to select the best order, that is, assing p1, p2, p3, and p4 and compute the length. Pick the best, and you are done! (m==0 || n==0 you can solve by hand)
•  » » 5 years ago, # ^ |   +13 F is far from div1 E and... how to solve B -_-?
•  » » » 5 years ago, # ^ |   0 I just tried all the possible 4-tuples of what I considered "important points". This passed pretests. I hope also system tests (((7262613
•  » » 5 years ago, # ^ |   -11 saw a lot of hacks to B, so doubt it's div2 A level
•  » » 5 years ago, # ^ |   0 I find C easier than B.
•  » » » 5 years ago, # ^ |   0 How did you solve C?
•  » » » » 5 years ago, # ^ |   +14 Well, this formula 1/n + (n - 1)/n * (m - 1)/(mn-1) is a solution.
•  » » » » » 5 years ago, # ^ |   +9 I need explanation !
•  » » » » » » 5 years ago, # ^ |   +84 Well, There two possibilities to get the same card. 1) One card was chosen twice. Probability here is 1/n 2) Different cards were choosen. Probability of that is (n — 1)/n. Let's see on all cards that was not chosen first time, All they ahve the same probability to be chosen. There are m — 1 out of mn — 1 cards that equal to first one.
•  » » » » » 5 years ago, # ^ |   +1 magic..
•  » » » » » 5 years ago, # ^ |   0 Found the same formula but didn't check when n=m=1...and got a WA
•  » » 5 years ago, # ^ |   +60 B = Div2 A? Nice joke :)
•  » » » 5 years ago, # ^ |   -41 First, I wrote this before systest. Second, it's B. Third, there were a LOT of passed pretests, and there are still a lot of passed systests.Right now, I'd say that B is div(-1) stupidproblemIdontwanttocompete.Your comment is just as biased as mine.
•  » » » » 5 years ago, # ^ |   0 Did I miss any announcement of some special prize that will be served if this guy (Xellos) gets a certain number of down vote? A man with +122 contribution to this community is getting down vote even without using slang, or native language! Come on, he just shared his feelings with you guys. Anyway I "donate" my +23 contribution to you,down voters . Please take it!
•  » » 5 years ago, # ^ |   +19 For me, B and C were much harder than E.
•  » » » 5 years ago, # ^ |   -14 I didn't really try to solve them, and this was before systest. As I wrote, "my impression".
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +5 Sorry, but stupid bruteforce + obvious combinatorics can't be harder for noone than some fancy algorithm on LCP xd.
•  » » » » 5 years ago, # ^ |   +16 Obvious combinatorics is not that obvious for some people(like me =)). And no fancy algorithm on LCP is actually required in E, there is a well-known solution with suffix automaton for these type of string problems which is simple to understand and implement if you have seen it before.
•  » » » » 5 years ago, # ^ |   0 Did you say harder? If it's true I couldn't understand your reply.
•  » » » » » 5 years ago, # ^ |   0 Lol, of course :D. Thanks for pointing that out :P.
•  » » » » » » 5 years ago, # ^ |   +3 You're welcome :)
•  » » » » 5 years ago, # ^ |   +8 Just take a look at performance of kb.:)
•  » » 5 years ago, # ^ |   -7 B can not be compared to any div2 A. You can see number of Submitted Solutions and number of Passed Solutions.
•  » » 5 years ago, # ^ |   +22 You failed div2 A systest :)
•  » » » 5 years ago, # ^ |   -44 Nothing unusual for any problem with weak pretests, a lot of special cases, and considering I'm the one solving. Nearly everyone I see in my Friends tab failed B, even, so the last part can probably be extended.I can write it in bold caps for you, too: MY IMPRESSION.
•  » » » » 5 years ago, # ^ |   +1 Your impression is wrong.
•  » » » » » 5 years ago, # ^ |   -59 Your head is wrong, see this comment.
•  » » » » » » 5 years ago, # ^ |   +55 You try too hard.
•  » » » » » » » 5 years ago, # ^ |   -13 I see nothing wrong with trying to find where I made a mistake, and neither with having opinions.But I try too hard at anything, it's better than the opposite extreme :D
 » 5 years ago, # |   0 Yeah ! I accepted only once problems A
 » 5 years ago, # |   -10 why my solution for problem A skipped?
•  » » 5 years ago, # ^ |   0 mb you cheated at contest? I you not, you can ask to MikeMirzayanov
•  » » » 5 years ago, # ^ |   0 I didn't cheat in contest!
•  » » 5 years ago, # ^ |   +3 If you submit a problem multiple times, only the last one will be judged. The rest will be skipped.
 » 5 years ago, # |   +23 very fast system testing! :) thank you very much! :)
 » 5 years ago, # |   +1 congratulations sevenkplus !
•  » » 5 years ago, # ^ |   +67 yeah , he got 7k+ points... :)
 » 5 years ago, # |   +5 Wow very fast systest (considering this is a special round with a lot of participants).Anyway, why problem C has the same point as B? I think problem C is much harder....
•  » » 5 years ago, # ^ |   0 It's just depend on the participant if it's harder or not. For those who likes such problems as me it was easier than B. So equal points is quite a good idea.
•  » » 5 years ago, # ^ |   +19 Answer to C: (n = m = 1 is a special case). Doesn't look very hard.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Ah I miss this simple solution. No wonder....Anyway, this euphoria is over. I think I will back to yellow :'(
•  » » » 5 years ago, # ^ |   +3 Can you explain how you obtained that expression?
•  » » » » 5 years ago, # ^ |   +38 I considered two cases. The first case is when Alex chooses exactly the same card as you do. The probability of this is . Otherwise, you and Alex choose two different cards, and any pair of different cards is equiprobable (so, the fact that they are chosen from a random subset of size n is irrelevant). In this case, the total number of choices is , and the number of choices that result in the cards being of the same type is . By properly combining all these numbers, you get the answer.
•  » » » » » 5 years ago, # ^ | ← Rev. 2 →   0 nvm, got it.
•  » » » 5 years ago, # ^ |   0 how do you reach this formula ?
•  » » » » 5 years ago, # ^ |   0 here it's explained by another guy
 » 5 years ago, # |   0 Will you be providing the editorial?
 » 5 years ago, # |   +68 Sorry, I didn't like any of problems from A to D at all, can't say anythig about E and F though. And seriously, how is D being D? It is much much easier than B and C!
•  » » 5 years ago, # ^ |   +24 Agree that any of problems A-D was interesting at all...
 » 5 years ago, # |   0 Till when can we get the editorials??
 » 5 years ago, # | ← Rev. 4 →   0 My answer is correct for problem B, pretest 1, submission #7269214 1 1 0 0 1 0 0 1 But verdict is wrong output format Unexpected end of file — int32 expected 
•  » » 5 years ago, # ^ |   0 A possible reason is that you output newline as '\n' rather than endl. Remember that test machines are running Windows, which uses "\r\n" as line separator.
•  » » » 5 years ago, # ^ |   +26 I have always used '\n', never had this error before.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +9 I don't think that's a problem. When you print '\n' it automatically converted to '#13#10'
•  » » 5 years ago, # ^ |   +26 Your output is empty. And you've shown the right answer
•  » » » 5 years ago, # ^ |   0 Ah, yes. How stupid of me! But the reason I got confused is because my compiler was producing correct output. I found the problem to be compiler specific, in my machine the code outputs different but correct answer: 0 0 1 1 0 1 1 0 My compiler info: >>> g++ -v Using built-in specs. Target: x86_64-linux-gnu Configured with: ../src/configure -v --with-pkgversion='Ubuntu/Linaro 4.4.7-8ubuntu1' --with-bugurl=file:///usr/share/doc/gcc-4.4/README.Bugs --enable-languages=c,c++,fortran --prefix=/usr --program-suffix=-4.4 --enable-shared --enable-linker-build-id --with-system-zlib --libexecdir=/usr/lib --without-included-gettext --enable-threads=posix --with-gxx-include-dir=/usr/include/c++/4.4 --libdir=/usr/lib --enable-nls --with-sysroot=/ --enable-clocale=gnu --enable-libstdcxx-debug --disable-libmudflap --disable-werror --with-arch-32=i686 --with-tune=generic --enable-checking=release --build=x86_64-linux-gnu --host=x86_64-linux-gnu --target=x86_64-linux-gnu Thread model: posix gcc version 4.4.7 (Ubuntu/Linaro 4.4.7-8ubuntu1) I used direct comparison between doubles (a == b), which failed in judge compiler.
•  » » 5 years ago, # ^ |   0 I changed double in your solution to long double and it got AC
 » 5 years ago, # | ← Rev. 2 →   0 First of all , problems were awsome. B was harder than expected and D and E were interesting. C was maths , but I liked it.On the other side , I think the pretests at C were weak. I put m instead of n in one place ( in a for ) and because of that it didn't passed. I think that pretests are made for this kind of situations.
 » 5 years ago, # |   0 Thank you for tasks E and F. Looking forward to reading the solutions to those.I didn't like the rest of the tasks though. A and B were "let's see who forgets to code one if". Disliking C is my personal opinion — but I heavily dislike N <= 1000 when there is O(1) solution. As for D, I only have to say that I haven't even read the part "Moreover, after a piece of laundry is washed, it needs to be immediately moved into a drying machine, and after it is dried, it needs to be immediately moved into a folding machine", and my "solution" still was accepted.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +7 A: A is to guarantee that most contestants get at least one AC.B: Apparently B has a better solution than a bunch of if's.D: Perhaps the two problems have exactly the same answer. Who knows? Can you construct a counterexample?
•  » » » 5 years ago, # ^ |   0 about D: I think he meant that it was not reasonable to include it to the statement at all.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +1 D: No, I can't. If there is an easier approach, which can be written by accident or in wrong belief that it's the correct one; then it's authors' job to differentiate two approaches. If they haven't foreseen this approach, well, it happens sometimes. Still doesn't make it a good task. If they have known about this solution (but just couldn't find a counter-example), then this task shouldn't even be given, or that extra text should have been removed and the task should be given with less points.
•  » » » » 5 years ago, # ^ |   +16 The problems are equivalent I think. There is no difference between having a piece of laundry wait before it goes into the first dryer or having it wait in between consecutive dryers.
•  » » 5 years ago, # ^ |   +45 In my honest opinion, not having the restrictions hint to the complexity of the solution adds to the difficulty of the problem. I couldn't figure out problem C for some reason. But I bet I would have had better chances if the author had written N <= 10^9. Then, my brain would have been focused on finding a formula, not all over the place thinking about DPs and such.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 I did it with DP in O(N^2), so I think it whould have been harder with a formula. ( maybe worth more points )
•  » » 5 years ago, # ^ |   0 Well, If you code ifs in A or B they solved their task to diferrentiate people who will write and debug tons of ifs and those who will write 5-lines solutions where one can't have bug.
 » 5 years ago, # |   0 Problems were very interesting...!! Thanks to authors... Nice contest...!!!
 » 5 years ago, # |   +29 How to create a good test for problem F?I accepted the following flawed solution consisting of two steps. A naive approach would be: for each number x in the permutation, for all possible deltas y, check whether x - y and x + y are on different sides of the x. A partial solution is to check only the MAX first and MAX last values of y in this approach. In my solution, MAX = 60. Another naive approach reduced to a partial solution is: for each position t in the permutation, look at values at positions s from t - MAX to t + MAX, check if p[t] is between p[s] and 2*p[t] - p[s]. Again, MAX = 60. Looks like random test with only one valid pair (a, b) as an answer would make this solution fail with a good probability. So, is it possible to create such a test? If it is possible, how to do it?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +13 Test with only one valid pair can be constructed in this way. If you know a permutation p1...pn which has no valid pair then 2*p1-1,...,2*pn-1, 2*p1,...,2*pn will also have no valid pair for example 1 9 5 13 3 11 7 15 2 10 6 14 4 12 8 16 . Now if you will move for example leftmost even number to the left of the rightmost odd less than n/2 then you will have one valid pair in the example 1 9 5 13 3 11 2 7 15 10 6 14 4 12 8 16
•  » » » 5 years ago, # ^ |   +5 In general, if you take a permutation without valid pairs and swap two adjacent elements, you would get at most two such pairs. And with a good probability, you get only one.
•  » » » 5 years ago, # ^ |   0 Thank you, this construction seems to do the trick.By the way, the problem's test set catches me if I try using only the first part of the solution above, but lets me pass if I use only the second one.
•  » » » 5 years ago, # ^ |   0 While the test you provided is what I literally asked, it does not break the second partial solution. In your example, 2 and 7 end up being too close. If we move 2 further to the left, more valid pairs will appear, such as 2 4 with 3 between them. Similarly, moving 7 further to the right soon produces the pair 13 7 with 10 between them. The problem seems to persist if we build a larger example following the same procedure.So, how to break that partial solution, too? It would help to insert some "garbage" between 2 and 7 in the example, but we don't have any "garbage" left if we follow the procedure.
•  » » » » 5 years ago, # ^ | ← Rev. 4 →   +3 Look at this permutation a = { 1 5 2 6 3 8 7 4 }. For each pair (i,j) index of (a[i]+a[j])/2 is not i+1 and is not j-1. This means that in each valid triple no two are adjacent. Valid triples are 1 2 3 , 5 6 7, 2 3 4. Now consider we have the permutation [1 9][5 13][3 11][7 15][2 10][6 14][4 12][8 16] in each bracket the numbers give the same remainder when divided by 8. Now replace in permutation a[] whith this brackets according to their remainder. You will get [1 9][5 13][2 10][6 14][3 11][8 16][7 15][4 12] in this permutation the valid pairs can be only with the same remainders as in permutation a[]. i.e. from group [1 9]-[2 10]-[3 11] can be choosen respectively triples and each member of the triple can be from its respective group for example 9 10 11 are choosen from the first second and third brackets. Now imagine you have constructed a big permutation as before and replaced all brackets according to their place in a[] then in each valid triple members will be far from each other because in a[] in each triple the distance of each two is at least 2.
 » 5 years ago, # |   0 I enjoyed problem C very much as it has a very small and smart solution. And I am really eager to know how B can be solved without the use of more than 6 or 7 if. I can't solve B but any solution i see use more than 10 if !
•  » » 5 years ago, # ^ |   0 any solution i see use more than 10 if ! 7271199 — here, i solved it (in practice) using eight if.
•  » » 5 years ago, # ^ | ← Rev. 2 →   +22 My solution:n/m = 0 how to handle is given in the test case n,m>0: looks like only four casessol: http://codeforces.com/contest/452/submission/7267559 7 ifs with two from predefined functions
•  » » » 5 years ago, # ^ |   +3 i think when (n>0)and(m>0) we only need to compare 2 of them. if n>m, the first way is obviously longer than the second, and the fourth is longer than the third. so we only need to consider the 1st and the 4th. if n<=m, we only need to compare the 2nd and the 3rd.my code:7273175
•  » » 5 years ago, # ^ |   0 Like this.This version of my solution is a bit messy! I'll rewrite it to be a bit easier to read.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 --ignore--
•  » » » 5 years ago, # ^ |   0 if(nowDist > maxDist) what about this one? :D
•  » » 5 years ago, # ^ |   0 How about using brute forces, we can search (0,0) (0,1) (1,0) (1,1) (0,m) (n,0) (n-1,m) (n,m-1) (n-1,m-1) by dfs.
 » 5 years ago, # |   +5 In problem A I failed this test case 6 ......but I assumed that there must be at least one letter in the input from the problem's statement "you already know some letters" and "fits the length and the letters given"
 » 5 years ago, # |   -22 I had thought accepted problems F with randomize (YES or NO)
•  » » 5 years ago, # ^ |   +3 You should really improve on your English, I cannot understand most of your comment!
•  » » » 5 years ago, # ^ |   -11 Thanks you note me
•  » » » 5 years ago, # ^ |   -25 You should really improve on your English, you cannot understand most of my comment!
•  » » » » 5 years ago, # ^ |   +3 comments*
•  » » » » 5 years ago, # ^ |   0 you're so predictable
•  » » » » 5 years ago, # ^ |   +34
 » 5 years ago, # |   -79 I now see why I failed B. One line that I forgot to remove from an older solution: if(N > M) swap(N,M);. I got AC after removing it. (submission during the contest: 7262088, after the contest: 7271312)Therefore, my opinion that it's div2 A level holds.My solution was: we either use the strategy from sample 1 (diagonal, vertical/horizontal line, diagonal) or the first obvious greedy (longest non-diagonal starting in a corner, diagonal, longest non-diagonal starting in the other corner). Special cases N = 0 or M = 0.
•  » » 5 years ago, # ^ |   0 Pretests on B were very weak.  x=make_pair(0,0); y=make_pair(N,M); z=make_pair(0,0); t=make_pair(N,M-1); I failed B because I mistyped the points for one "case", yet I still passed the pretests.
 » 5 years ago, # |   +25 When will the contest be rated usually in codeforces?
 » 5 years ago, # |   +29 Why is rating update taking so long?
•  » » 5 years ago, # ^ |   +6 I always wonder why system test is faster than rating update!
•  » » » 5 years ago, # ^ |   +1 Generally the rating the updated with in half an hour of the system testing, but today i don't know what is it that they are taking so much time.
 » 5 years ago, # |   +51 Country wise rankings for this contest has been updated. (link)
•  » » 5 years ago, # ^ |   +29 thanks! feels so good to see myself topping my country, Alhamdulillah! :D
•  » » » 5 years ago, # ^ |   +7 Alhamdulillah :)
•  » » » 5 years ago, # ^ |   +7 I think you deserve it sister. Your performance in CodeChef is also same as far I noticed! Congratulations! :)
 » 5 years ago, # |   +31 When will Ratings be updated ?
 » 5 years ago, # |   +9 waiting for the editorial :)
 » 5 years ago, # |   0 For problem C many got wrong ans on test case 8 who used DP sol state-dp[i,j]-prob of getting j similar cards of a particular type till picking i carks from the set why is this wrong ?
 » 5 years ago, # |   +9 Ratings are updated!
•  » » 5 years ago, # ^ |   +14 Oh! At last having the test of being purple for the first time! Alhamdulillah. :)
 » 5 years ago, # |   +3 Still Div1!
•  » » 5 years ago, # ^ |   0 I'm surprised that I added rating. I decided two tasks are not particularly slowly. (Google Translate).
 » 5 years ago, # | ← Rev. 3 →   +24 I solved F using pretty weird observation:If answer is NO, then parities of elements in our sequence look sth like:0000000000010001111111111111 / 1111111111100110000000000.I mean, almost all odd numbers are before almost all even numbers or the other way around. Some inversion are possible, but only a small amount of them. Does anyone can provide appropriate bound for numer of those inversions? I bruteforced small cases and for n=10, there were at most 4 inversion, for n=13 at most 6, so I assumed that n + 10 is a safe bound and it passed. I checked manually whether those inversions are a part of a bad triple and later call recursively for odd and for even numbers which resulted in a O(n log n) solution. But I still don't know why it is correct :P.Unfortunately I got one integer overflow in my solution and it wasn't accepted :(. After adding "1ll * " it passed ;/.
•  » » 5 years ago, # ^ | ← Rev. 4 →   +16 During contest I found a paper that said that if n>11 then the parity of the first floor(n/2)-6 was the same and the parity of the last floor(n/2)-6 was also the same. However, I didn't come up with your solution; nice one!Edit: paper
•  » » » 5 years ago, # ^ |   0 Why those papers are always so long :(? How have you managed to prove that observation? I don't feel like reading those 15 pages xd.
•  » » » » 5 years ago, # ^ |   0 I actually just skimmed the paper to see if I could find ideas for a probabilistic algorithm. Without having read it in detail it seemed to me that a great part of those 15 pages were devoted to prove this, so I think it mustn't be easy to prove. One think that bothers me though is that if I understand the theorem correctly the correct structure would be more similar to: 00000000000/11111111111 or 1111111111/00000000000 since we can't have 0s at both sides (we would have 2*(n/2-6)>n/2) though this is not true for n<24Would your algorithm still work with this 'structure'?
•  » » » » » 5 years ago, # ^ |   +5 Um, sorry, I somehow understood that you proved that observation, but you wrote that you found it on a paper :P.And that sign "/" was meant to be "or". Those were 2 separate sequences :P.
•  » » » » » » 5 years ago, # ^ |   +8 We both read each other's comment wrong then!It all makes sense now :)
 » 5 years ago, # |   +10
 » 5 years ago, # |   0 please anyone explain how to solve D?
•  » » 5 years ago, # ^ |   +2 Straight forward implementation.We will simulate the process second by second.For each machine, keep a list of pieces inside the machine right now and for each piece save its entrance time.Every second, remove from machine(3) the pieces whose entrance_time + t3 == current_time. Do the same for machine(2) moving pieces to machine(3). Same for machine(1)Now at the end of each second, try to put as much new pieces in machine(1) as possible.You need to check that there is an empty place in machine(1) right now and that there will be an empty place in machine(2) after current_time+t1 and in machine(3) after current_time+t1+t2.
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 Need to find a time when every thing is finished. Thing can start washing (drying or ironing) if the machine is free. That is if i - n[j] >= 0 then T[i] (beginning the process) = max( T[i - n[j]], T[i] ) else T[i], j is number process, i is number thing. End process is T[i] = max( T[i - n[j]], T[i] ) + t[j] or T[i] += t[j].Necessary to calculate the time after completion of each process. Answer is T[k].Source code: 7271703.
 » 5 years ago, # |   +1 I'm waiting for the editorial,it's so sad that I couldn't solve any problem last night TAT
 » 5 years ago, # |   +1 I'm sorry to ask this, but when the editorial will be published? Since i'm a newbie in competitive programming i can't understand most of the problems. It would be very helpful for people like me if you publish an editorial on the contest. Thanks in advance :)
 » 5 years ago, # |   0 Contestant thank you for good contest.
 » 5 years ago, # |   +6 Can we expect an editorial here?
 » 5 years ago, # |   0 In problem C, Some of the tops I see have used something like a log table. Can someone explain what log array has to do with this?
•  » » 5 years ago, # ^ |   +25 I had logs in my solution, just to prevent floating-point overflow. I was handling probabilities by counting the number of ways of choosing cards under certain conditions, and dividing at the end by ALL the possible ways. But these numbers (1000000! / 999000!) are far too large for doubles. So I worked with their logs instead. You don't lose too much precision.
•  » » » 5 years ago, # ^ |   +14 Since every binomial in the solution has k ≤ 1000, another trick is to multiply and divide at the same time at most k times: double r = 1; for(int j = 0; j < k; j++) { r *= n-j; r /= j+1; } 
•  » » » 5 years ago, # ^ |   0 I used the formula , and it worked in this task as well: double ncr[1111][1111] = {0}; for (int j = 1; j <= n; j++) ncr[0][j] = 0; ncr[0][0] = 1; for (int i = 1; i <= n; i++) { ncr[i][0] = 1; for (int j = 1; j <= n; j++) { ncr[i][j] = ncr[i-1][j]+ncr[i-1][j-1]; } } 
•  » » » » 5 years ago, # ^ |   0 I'll take a look at your solution, it is something interesting) You need just C(n,n) — while naive combinatorical one uses C(n*m,n) (number of ways to generate deck and other stuff like that), which is too much for Pascal's triangle.Or could you please explain it by yourself? :)
•  » » » » » 5 years ago, # ^ |   +8 I calculate for k = 1, 2, ..., n the probability that the first chosen card appears exactly k times in the final deck and the first chosen card matches the second chosen card. The sum of these probabilities is the answer for the problem.Thanks for asking this, I didn't notice the other method that uses larger binomial coefficients. :)
 » 5 years ago, # |   0 @Mike Mirzayanov i have submitted my code for Problem A : Eevee during contest and it was accepted after the contest i saw in the Verdict tab writes skipped and my submisson have no score then i send again the same code after contest and it was accepted :( why this happens?
•  » » 5 years ago, # ^ |   -8 Maybe you cheated :P
•  » » » 5 years ago, # ^ |   0 :))) yok arkadaşım
 » 5 years ago, # |   0 Can anyone explain sol of C without the observation of O(1);
 » 5 years ago, # |   +3 can I expect editorials!
 » 5 years ago, # |   +16 http://main.edu.pl/pl/archive/ilocamp/2011/art — here you can submit F in a version when you have to count number of those pairs, not just state whether it's 0 or more :P.
•  » » 5 years ago, # ^ |   +16 It is also said that you can assume that the result will never exceed 1,000,000. I think it is quite important.
•  » » » 5 years ago, # ^ |   +3 I was thinking about counting number of the pairs faster than in O(number number of them * log^2), but didn't manage to find a solution. Not sure if it is possible.
•  » » » » 5 years ago, # ^ |   0 Hmm, I believe my solution can be extended to count them in O((N + #pairs) * log(N)), but it's quite tricky, I'm kind of "cheating" using polynomial hashing, and that's not much of an improvement. :)
•  » » » » » 5 years ago, # ^ |   0 Yes, my solution is also tricking around polynomial hashing (using binary search and information about previous differing characters positions to determine next one), but it has log^2 factor due to segment tree using. It's an interesting question how to avoid quadratic #pairs factor.
•  » » » » » » 5 years ago, # ^ |   0 It sounds like we have the same algorithm. But it looks like I was mistaken. I thought I could avoid a log factor using amortized constant-time segment tree queries, but that requires making O(N) queries, whereas we're only doing O(log N) queries. So the log^2 factor won't go away. D'oh!
•  » » » » 5 years ago, # ^ |   -10 My solution ( http://codeforces.com/blog/entry/13095#comment-180008 ) clearly can be extended to counting by generating all inversion and checking them all, but I don't know how to properly estimate complexity. For F mentioned paper states sth which implies that if there are >36 inversions, then there is at least one good pair (a, b). Maybe there is a constant such that if there are > M * k inversion then there are at least k good pairs (a, b)? If this will be the case, then overall complexity will be O(n log n + result), but there's a large constant next to result. There also a possibility that such constant doesn't exist :D. But maybe it can be at least proven that we can replace M by something growing slower than log^2 k :D. That means that following statement will be true:if there are > M * f(k) * k inversion then there are at least k good pairs (a, b) (where f(k) / log^2 k -> 0)If so, we will get better solution : p. But until something here will be proven this is some kind of meaningless considerations :P. But on a contest I will give it a try :P.
 » 5 years ago, # |   +48 If not full editorial, please at least put the editorial for problem E and F. Editorials of other problems can be posted as comments of discussion in the blog.
 » 5 years ago, # |   -12 I think best solition for problem B is this . best means that code is easy to read
•  » » 5 years ago, # ^ |   -12 And what do you think?
•  » » » 5 years ago, # ^ |   0 Copy-paste shouldn't be your friend (though it was mine in this problem xd)
•  » » » » 5 years ago, # ^ |   0 I trying understand this solution -- when I can't solve problem I analyze another's solution.
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   +16 there is a lot of DUPAs in your code, which sounds funny if I've understood it correctly :-)
•  » » » » » 5 years ago, # ^ |   0 As I said, my code for this problem is one of the worst codes I have ever written :P.
•  » » » » » 5 years ago, # ^ |   -8 It's not my code
 » 5 years ago, # |   0 Does this mean from now to 8.10 ,there won't be any other CF round ?
 » 5 years ago, # |   +8 Can anybody explain the solution of problem E ?
•  » » 5 years ago, # ^ |   +8 Problem is easily solvable with suffix automaton. We can use modification of algorithm from e-maxx for finding largest common substring of many strings. Firstly we concatenate strings like a#b&c%. Then we build automaton. For each state we should calculate number of paths from it ending with character '#', '\$', '%' in variables f,s,t. It can be done with dfs. It will be amount of rightmost positions of current state in first, second and third string. Then we can simply iterate over the states and increase the answer by f[i]*s[i]*t[i] where i is a number of state for all different lengths of substrings that are compressed in the state. I.e. for the segment (len(link(i));len(i)]You can check my solution for better understanding: 7265940
 » 5 years ago, # |   +15 Who's in?yarrr, Igor_Kudryashov and Goofy57 definitely are.
•  » » 5 years ago, # ^ |   +18 Me. -XraY-, I think. ACRush?
•  » » 5 years ago, # ^ | ← Rev. 2 →   +20
•  » » 5 years ago, # ^ |   +18 I was invited as well. Also, I believe Alex_2oo8 will be able to participate onsite.
•  » » 5 years ago, # ^ |   +16 I will participate.
•  » » 5 years ago, # ^ |   +16 +Me :)
•  » » 5 years ago, # ^ |   +21 -Me
•  » » » 5 years ago, # ^ |   0 EXCUSE ME! Can i take part in this contest and will i be rated?
•  » » » » 5 years ago, # ^ | ← Rev. 8 →   +16 Yes. Even if you were not top 500 on round 1, you can still participate unofficially. It will be rated for both official and unofficial participants.
 » 5 years ago, # |   +3 I can't register to contest. When I click "Register now" I receive notification "The contest does not allow self registration"
•  » » 5 years ago, # ^ |   +8 Did you choose the correct contest (online round)?
•  » » » 5 years ago, # ^ |   0 guy, do i can be rated in contest(online round)? :D
•  » » » 5 years ago, # ^ |   +3 Um, sorry, you're right, thanks :P.
•  » » 5 years ago, # ^ |   -41 The comment removed because of Codeforces rules violation
•  » » » 5 years ago, # ^ |   +19 I already took a place in top 500 (such a great achievement xd) and I don't have time to come up with creative answers, so simply shut up retard.
•  » » » » 5 years ago, # ^ |   +8 sorry! maybe error system, :d
•  » » » 5 years ago, # ^ |   +29 > rude post
 » 5 years ago, # |   +13 I hope they give editorials this time.
 » 5 years ago, # |   0 will people who not finished in the top 500 in Round 1 be rated ?
 » 5 years ago, # |   +14 It's been 2 months now since the contest...and the promised editorial has not come out. Are there still plans to release this?If not, maybe we can compile all the relevant comments together to form what we already have.