### allllekssssa's blog

By allllekssssa, history, 6 years ago,

Hello Codeforces community !

I am glad to announce Codeforces Round 307 (Div. 2) on 12th of June at 19:30 MSK. Authors of this contest are Nikola Mandic (nikola12345) and Aleksa Plavsic (allllekssssa). This is our first round and we really tried to make interesting and solvable problems. Traditionally Div.1 participants can take part out of the competition ( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes ). This is the first Serbian round and we want to invite our friends from Serbia to take part in this round and maybe prepare some of next rounds.

The main character of this round is gonna be GukiZ ( our proffesor of computer science ). He really helps us to become better people and developers !

We want to thank Zlobober for help in preparing contest and great advices, Delinur for translating problems statements into Russian and MikeMirzayanov for fantastic Codeforces and Polygon platform !

We wish you great fun, a lot of Successful hacks, Accepted solutions and high rating !

UPD: Scoring distribution: 500 — 1250 — 1750 — 2000 — 2500.

UPD2: Due to technical reasons round was delayed by 10 minutes. Stay tuned!

UPD3: +5 minutes. Thanks for your patience!

UPD4: System testing is complete, but the rating update won't be that fast since we are working on improving our cheater catching system. Thanks for your understanding!

Congratulations to winners!

DIV 1:
1.MrDindows

DIV 2:
1.hrzhrz_hrzhrz

2.slo

3.wangjing

Thanks to all participants. We hope you have a good time and learn something new.

• +323

 » 6 years ago, # |   -33 Okay, let's be finally realistic here: This time I will either jump into Div.1, or I will not.
•  » » 6 years ago, # ^ |   +11 You are in the "danger zone", good luck!
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 [user:Ghassan.Khazaal,2015-06-12] is the closest one to Div 1 :)
•  » » » 6 years ago, # ^ |   -35 nope, i am closer because i will win the round
•  » » » » 6 years ago, # ^ |   -30 nice joke :)
•  » » » » 6 years ago, # ^ |   -26 next joke please <3
•  » » » » 6 years ago, # ^ |   -8 U lied, mister.
•  » » » » » 6 years ago, # ^ |   0 Was that a joke as well?
•  » » » » » » 6 years ago, # ^ |   0 He said that he's going to win the round. As mentioned above — he did not.
•  » » » 6 years ago, # ^ |   +2 1699.999999999 -> 1700 :) nice mention.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +2 actually 1699.999999999 -> 1699.999999999and 1699.(9) = 1700 -> 1700and 1699 + sum(9*10^(-k)) for k = 1..n -> 1700 (n -> inf)
•  » » 6 years ago, # ^ |   -26 Next Bet Please
 » 6 years ago, # | ← Rev. 2 →   +12 I wish good luck to all participants.;)
•  » » 6 years ago, # ^ |   0 and all of them same points :)) such a welcome comment
 » 6 years ago, # |   -13 It clashes with Codechef Snackdown is it possible to shift it ?.http://snackdown.codechef.com/schedule
•  » » 6 years ago, # ^ |   +33 if you prefer a codechef round to a codeforces round I think...
•  » » » 6 years ago, # ^ |   -20 I wonder whether I_love_Codechef prefer codechef or codeforces round...
•  » » 6 years ago, # ^ |   +244 dont worry codechef will be loading while this contest happens :)
•  » » » 6 years ago, # ^ | ← Rev. 2 →   -37 my homour > INF
•  » » » 6 years ago, # ^ |   0 That's why I have decided to participate in both :p
•  » » 6 years ago, # ^ |   0 Too bad you can't do both.
•  » » » 6 years ago, # ^ |   +3 I will still try to participate in both
•  » » » » 6 years ago, # ^ |   0 Not a good idea according to me, but then maybe YOU can :)
•  » » » » 6 years ago, # ^ |   0 I think you should also teach others how to perform well in both at the same time :P
•  » » » » 6 years ago, # ^ |   +2 I am such a fool that I waited for codechef snackdown elimination mirror to start till 11 pm, but didn't noticed that official elimination round had already started at 9:30 pm. I noticed it only when I was not able to submit any solution in mirrored contest. This big mistake has costed me 3+ hours of penalty time due to which my rank went beyond 700. If I hadn't made this mistake, my rank would be under 300 and our team would have got T-shirt and would have qualified for finals.
•  » » » » » 6 years ago, # ^ |   0 Life can seriously betray you sometimes like this.
 » 6 years ago, # |   0 i might not be red but i can host a contest and i will do it .... best of luck
 » 6 years ago, # |   0 It looks like we will have harder division 2 contest than usual. Hopefully it will be not too hard ;)
 » 6 years ago, # |   +9 Congratulations on your first round! Zelim sve najbolje
 » 6 years ago, # |   0 it is ur first round i wish it will be the first round to me to make the rate high :3
 » 6 years ago, # |   +45 ( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes ) May I shout out tourist and run away?
 » 6 years ago, # |   -30 I think 3 problems will be Brute Force and logically.
 » 6 years ago, # |   +4 Really look forward for this contest! allllekssssa helped me a lot to understand problem's editorial with his solution (back when I used to only know Pascal).
 » 6 years ago, # |   -8 First Serbian round! Congratulations setters. :)One day, we'll have an Indian round too. And I'm looking forward to that day with excitement. Hope it comes soon.
•  » » 6 years ago, # ^ |   +7 There have been at least two Indian rounds as far as i know :P
•  » » » 6 years ago, # ^ |   0 Yes I know, but unfortunately I did not start coding when the rounds were held. I want to personally take part in an Indian round as a participant, it'll be a whole new feeling.
 » 6 years ago, # |   +2 Thanks guys ! I hope that we will justify expectations !We have solutions in Pascal and after contest we will put it in Editorial.
•  » » 6 years ago, # ^ |   0 I hope you also have solutions in C++ and Java, to prevent the TL (java) or naive solution due to your time constraints P.S. Today in Russian Federation celebrates the Day of Russia :)
 » 6 years ago, # |   +6 Challenge for tourist: Solve all problems in 20 mins
•  » » 6 years ago, # ^ |   +31 I talked with him ! He can't do competition, but he can do virtual contest anytime. Also same chellange can be for Petr, vepifanov and other top participants...
 » 6 years ago, # |   0 If the problems are so hard, how do you expect div 2 participants to enjoy the round?
•  » » 6 years ago, # ^ |   +3 If a Div 1 participants can't solve all problems in 20 minutes, it doesn't mean that it is hard
•  » » » 6 years ago, # ^ |   +35 I wonder if there exist a past div2 contest where a div1 contestant managed to solve all the problems in 20 minutes.for me total time needed to read and understand all five problems is more than 20 minutes
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   -7 Ignore this comment :)
•  » » » » 6 years ago, # ^ |   +18 I found one here. tourist solved all problems within 16 minutes.
•  » » » » » 6 years ago, # ^ |   +13 There is nothing that tourist can't do.
•  » » » » » 6 years ago, # ^ |   +31 This round number is 16. tourist Solved this problems in 16 mins.
•  » » » » » 6 years ago, # ^ |   -10 Its funny tourist even bothers with div 2 sometimes. Give others a chance to win tourist :)
 » 6 years ago, # |   0 I hope that the problems will be on different topics ...
•  » » 6 years ago, # ^ |   -15 Next Bet please
 » 6 years ago, # |   0 hope to see some easy problems :D
 » 6 years ago, # |   +5 "a lot of Successful hacks" :/ I guess this line is not pleasant for me. every-time I saw it on the round announcement, one of my sol got hacked just before the contest end. and when I try to hack someone else's sol I fail.
•  » » 6 years ago, # ^ |   0 Then you should be more careful :)
 » 6 years ago, # |   0 Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).
 » 6 years ago, # |   -16 "( personally I believe that the problems are worth to Div 1 participants, and nobody can solve everything in 20 minutes )"it appears that problem statements will be lengthy and (especially) problems A and B will be implementation problems with lot of cases and variables to handle, that may make these problems, easy but time taking problems.
 » 6 years ago, # |   +5 the earliest scoring distribution ever .
 » 6 years ago, # |   +1 Hi, this is the first time I will participate out of competition. I want to know if my rating will be affected.
•  » » 6 years ago, # ^ |   +4 no, your rating will not be affected
•  » » » 6 years ago, # ^ |   +2 thanks, mate
 » 6 years ago, # |   +7 I'm surprised by the scoring! It seems that we're gonna have a harder B than usual... :)Good Luck
 » 6 years ago, # |   -9 I want to get out of the green zone towards blue and purple .
 » 6 years ago, # | ← Rev. 2 →   0 In last contest I was flying too high...now it's time to come to the ground.... :/
 » 6 years ago, # |   0 will, I wish to get accepted as possible because I got enough of digging in the newbie area ..
•  » » 6 years ago, # ^ |   +5 Once I was also deep in newbie, but through regular practice I have managed to participate 5-6 times in Div — 1 (candidate master). One day you will also enter Div — 1 by learning DS and algo, regular practice and by making, "up-solving", your habit.
 » 6 years ago, # |   0 Seen 5000+ (and still counting) registrants for the first time in Div 2 only contest.
•  » » 6 years ago, # ^ |   +2 There is 4532 Participants actually, all others are participating unofficial
 » 6 years ago, # |   +19 And its delayed....
•  » » 6 years ago, # ^ |   +19 And I hate delay
•  » » » 6 years ago, # ^ |   0 And again. -_-
•  » » 6 years ago, # ^ |   -12 Lets see how many problems I can solve in first 50 minutes (also participating in codechef snackdown)
•  » » » 6 years ago, # ^ |   0 How many did u solve? I already got the 2 easy ones...
•  » » » » 6 years ago, # ^ |   0 Don't lie, you only solved 1
•  » » » » » 6 years ago, # ^ |   0 I meant in snackdown... lol :)
 » 6 years ago, # |   0 The best option : Switch back to Snackdown... :)
 » 6 years ago, # |   +16 Damn I hate Delays
•  » » 6 years ago, # ^ |   +15 Come on! 5 more minutes?! I have a chemistry exam tomorrow.
 » 6 years ago, # |   0 ~800 unrated participants :3
•  » » 6 years ago, # ^ |   +5 At least they're fair enough to participate with their real account (^_^)
•  » » 6 years ago, # ^ |   +8 5578 — 800 = 4778~4778 rated participants Oh My God I'm very Clever
•  » » » 6 years ago, # ^ |   -8 this is more correct 5500 — 800 = 4700
•  » » » » 6 years ago, # ^ |   +8 why is this more correct? :p
 » 6 years ago, # |   +9 Great. People, we have yet another delay (+5min this time) :(
•  » » 6 years ago, # ^ |   +2 And I love delay ):
•  » » » 6 years ago, # ^ |   0 yes me too,especially when you are writing snackdown contest parallel with it
 » 6 years ago, # |   -12 In Russian, please.
 » 6 years ago, # |   0 Good luck have fun.
 » 6 years ago, # |   -15 What The Fuck happened?? why these delays??
•  » » 6 years ago, # ^ |   +3 no need to swear
•  » » 6 years ago, # ^ |   0 for fun
 » 6 years ago, # |   -8 Wow, all profiles are blocked.
 » 6 years ago, # |   +27 Soon contest announcements will have "due to technical reasons, round will actually start on time. Thank you for your understanding!"
 » 6 years ago, # |   0 No more delay please :)
 » 6 years ago, # |   0 seriously another 5 minutes !!! -_-
 » 6 years ago, # |   0 Really this last delay?
 » 6 years ago, # |   +29 heeyy , you are not codechef
 » 6 years ago, # |   +25 10 + 5 + 2.5 + ... it's gonna be 20 mins...
 » 6 years ago, # |   +9 It's 1:41 a.m. here in Korea.. Delay means less sleep to me T_T
 » 6 years ago, # |   0 00100011 00100110 00010000 00010011 00010011 00010000 00100100 00100011
 » 6 years ago, # |   0 4859 rated contest registration !!! I this its a new record For Div — 2 :D
 » 6 years ago, # | ← Rev. 2 →   -15 c
 » 6 years ago, # |   +31 Are you sure it's for DIV 2 ???
 » 6 years ago, # |   +35 Remove problem A, and it becomes Div1 Only
•  » » 6 years ago, # ^ |   0 B was probably too easy for Div1 too, but others are ok.Spent last 70 minutes on D, almost come to the solution, but lacks of knowledge in combinatorics. Also can't get how to do fast 2^(bignumber) mod 10^9+7.I've came up to formula: 2^(n * total_bits — 2 * (bits1pos1 + bits1posn) — 3 * (bits1pos2 + ... bits1posn-1)) for each combination of bits1pos1 ... bits1posn-1 where thier sum = amount of bits with value 1 in K.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 2^N mod 10^9+7 is actually quite simple, and can be done in O(logN). All you have to do is exploit these two properties, 1) (a*b) mod m = ((a mod m) * (b mod m)) mod m. 2) For an even b, (a ^ b) = (a ^ (b/2) ) * (a ^ (b/2)), and for an odd b, (a^b) = a * (a ^ ((b-1) / 2)) * (a ^ ((b-1) / 2)) 
•  » » » » 6 years ago, # ^ |   0 Ah thanks! So its just usual fast power but with mod addition... So easy :)
•  » » » » » 6 years ago, # ^ |   0 yup
 » 6 years ago, # |   -28 This contest was too easy
•  » » 6 years ago, # ^ |   +6 u know that there are total 5 problems in the contest ri8 and not one !! :p
•  » » » 6 years ago, # ^ |   -18 don't argue with me it was pretty easy (Face with sunglasses)
•  » » 6 years ago, # ^ |   0 maybe no body understands sarcasm that's why i decided to leave a post here for u guys to know that i'm obviously being sarcastic ...
•  » » 6 years ago, # ^ |   +2 Was this serously a div 2 contest? 130 accepts on C 50 Accepts on D and 25 Accepts on E
•  » » » 6 years ago, # ^ |   0 Even div1 users solve in 1 : 30 hour
•  » » » 6 years ago, # ^ |   0 Possibly you have seen "unofficial" standings. In official Div 2 standings stats are like this:A->2622 B->416 C->43 D->4 E->6so I think it was slightly harder Div 2 contest
 » 6 years ago, # |   0 Thank you for this great round! (no sarcasm here) I've never thought that Div2 rounds may be that tough ;)
 » 6 years ago, # |   +3 Both announcements were so obvious and useless.
 » 6 years ago, # |   0 in top 20 there are 10 unrated participants ... it is very nice if they are participating in codeforces for the first time :) and hope those are not fake handles of rated ones :)
 » 6 years ago, # |   0 How can we solve problem C??was it a DP?
•  » » 6 years ago, # ^ |   +2 It can be solved using binary search. If we fix time, we can use greedy to put students from left to right and then compare it to M to check, whether it's possible to make it with this time
•  » » » 6 years ago, # ^ |   +1 That is a great idea but could you explain the greedy part in more detail?
 » 6 years ago, # |   +5 What could be pretest 12 for B?
•  » » 6 years ago, # ^ |   0 I could provide a tricky case that let me pass pretest 12input: aaabbbcd ab bcd output: abababcd here the maximum is 3 which is ab, ab, ab 3 times not bcd..this implies when you the possibility of adding string b as well as string c, choose the one with minimum len.
•  » » » 6 years ago, # ^ |   +2 My solution passes this test case, but failed #12 on pretests. I don't think they are related.
•  » » » » 6 years ago, # ^ |   0 Try: aaaaaabbbbbb aba bab
•  » » » 6 years ago, # ^ |   0 I am getting "bcdababa". Why is it wrong?
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 when u get bcdababab u are first including string with larger length that is string c, and adding the rest afterwards, while you need to first focus on adding the strings with smaller length if you have the opportunity to add any of them( either b or c). this works as a tie breaker.UPD: and as a result will increase answer by a significant amount.
•  » » » 6 years ago, # ^ |   0 I've got fault on test 12 too and I used that idea about minimum length. And input strings for this test is too long and all I can see is that an optimal solution maximum is 133 and my 129...
•  » » » 6 years ago, # ^ |   +6 This is wrong, actually.Consider a = "aefaefaef" (3 times aef), b = "aa", c = "aef". If you make the shorter string while you can you'll get 1 "aa" and then you'll have just one "a" to make one "aef". So you'll have one "aa" and one "aef" in total. It can be easily seen that one can make "aef" 3 times, though.I made the same mistake at first but then figured out it's not always true :). Unfortunately couldn't debug on time the other solution I came up with.
•  » » » » 6 years ago, # ^ |   0 hey u are absolutely correct..actually breaking tie on length is the 2nd tie breaker.first you need to add the string one time which can be repeated max number of times. if in this both the strings can be repeated same number of times then you need to break tie on length of strings.See my submission 11550880
•  » » » 6 years ago, # ^ |   0 My solution also passes this case(same output as you)!! But it can't pass case 12!!
•  » » 6 years ago, # ^ |   0 I don't know, but try these testcases: ==> in <== ababc bc ba ==> in2 <== ababac abac ba ==> in3 <== abaabaabacc aba ca 
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Answers?I am getting: 1 — babac 2 — abacba 3 — cacaabaababDo I have anything wrong?Thanks in advance!!!UPD: No idea why my solution is failing!
•  » » » » 6 years ago, # ^ |   0 Your output looks correct to me.
•  » » » » 6 years ago, # ^ |   0 Your answers seems correct.My own solution passes the #12 pretest (have no problems with it), but failed with runtime error on #23. Yet haven't find the error, but probably it caused by bad i/o, haven't read such a long strings before, not sure about that.
•  » » » » » 6 years ago, # ^ |   +5 Huh, found error. Its when neither of b and c is substring of a. In my code it was uninitialized result, so it failed on print.
•  » » » 6 years ago, # ^ |   0 For your second test i get: babaac and it have 'ba'+'ba'+ac = 2. And the answer for deinier was abacba and it is 'abac'+'ba' = 2. what is the criteria in tie case? My solution can't pass test case 12.
•  » » » » 6 years ago, # ^ |   0 Solved with Brute Force :DHere is my solution: 11559149
•  » » 6 years ago, # ^ |   0 Passed all suggested inputs but still fail pretest 12. Any suggestions? I can't even get full string to debug locally.
•  » » 6 years ago, # ^ |   0 Input: aaaaaabbbbbb aba babOutput: abaabababbab
 » 6 years ago, # |   +41 Looks allllekssssa is fan of PrinceOfPersia
 » 6 years ago, # |   0 I have solved 2 problems A and B :))))
 » 6 years ago, # |   +53 These cases with L=0&M=1 for D which are not included in pretests... Pure cruelty :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Have to agree with you. I feel lucky that at least there was a pretest in which K >= 2^L. It was then that I realized that there were special cases (including those you mentioned above) :P.
•  » » » 6 years ago, # ^ |   +5 I am not as fortunate as you. That was the only corner case I handled :'( I though I had it in the bag but missed 2-3 corner cases :'(
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I've got one more personal rule: never use constants without MOD inside modular arithmetics code.
 » 6 years ago, # |   0 Am I the only one who had to use a proxy to use Codeforces?
 » 6 years ago, # |   +5 What's behing B's pretest 12 ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +5 Maybe something similar to this..Input: aaaaaabbbbbb aba babOutput: abaabababbab
•  » » » 6 years ago, # ^ |   0 yes!!! that great!! Thanks!
•  » » » 6 years ago, # ^ |   0 Thanks. I am failing on that!
 » 6 years ago, # |   0 How to solve D?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +1 you just need to calculate how many binary numbers with length l,where no 2 1bits together.this all is fib(n+1)*x+(2^l-fib(n+1))*y,where x=number of 1 bits in binary representation of k and y=number of 0.
•  » » » 6 years ago, # ^ |   +8 Not sum, but product, I think, no?Fn + 1x(2N - Fn + 1)l - x
•  » » » » 6 years ago, # ^ |   0 How you find this formula?
•  » » » » 6 years ago, # ^ |   0 hey how did you come up with this formula involving Fibonacci numbers.Is it some less common standard formula or something else?Thanks in advance. :)
•  » » » » » 6 years ago, # ^ | ← Rev. 4 →   0 To create digit 0 from N numbers we will start with the first one it can be either 0 or 1 in this digit. The next one can also be 1 if and only if the first is 0, and can be 0 in any case. Now we have three case:0 -> 1 : the third must be 0;0 -> 0 : the third can be 0 or 1;1 -> 0 : the third can be 0 or 1;The number of the allowed zeros equals the number of all cases in the previous number.The number of allowed 1 equals the number of allowed zeros in the previous number so it equals the number of all cases in the number before the previous number.So the number of ways to construct zero is a Fibonacci sequence: 2, 3, 5, 8, 13, etc;
•  » » » » » 6 years ago, # ^ |   0 There is log(N) code for precise Fibonacci numbers. It is discussed here in Russian. See my submission 11558240
•  » » » » 6 years ago, # ^ |   0 yes right,you should write dp solution and you will find formula yourself
•  » » » » » 6 years ago, # ^ |   0 okay the recurrence is the key.. which I believe would resemble the Fibonacci recurrence.thanks for replying :)
 » 6 years ago, # | ← Rev. 2 →   0 .
•  » » 6 years ago, # ^ |   +8 It is a usual problem of last 5 minutes. Live with it.
 » 6 years ago, # | ← Rev. 2 →   +8 Very disapointed because of lags on the site at the end of the contest. Was not able to submit my D problem in time because of too long response of site.
 » 6 years ago, # |   0 the contest ended before time i couldn't submit in last 5 mins constantly got cf is unavailable :(
 » 6 years ago, # |   0 The A problem gave me the inspiration to continue but the next ones...
 » 6 years ago, # | ← Rev. 3 →   +6 On this contest I've intentionally solved A in C++ and D in Java to get the achievement "Polyglot" on this site (there was a blog post about it). Now my only hope to get it is to have A && D passed systests :)UPD NOOOOOO, my D solution has failed system tests :(
 » 6 years ago, # |   0 What is "cheater catching" ? I mean what actions are treated as "Cheating" ?
 » 6 years ago, # |   0 Nice Round :)
 » 6 years ago, # |   -32 Worst contest in CF history.
•  » » 6 years ago, # ^ |   +23 Be positive.Tasks was interesting, tests was ok. Maybe a bit hard for Div2, but definitely not bad contest.
•  » » » 6 years ago, # ^ |   -6 When there are 761 out of contest (div1) competitors and only 160 correct solutions for C there is something badly wrong... Definitely crosses from good to bad.
•  » » 6 years ago, # ^ | ← Rev. 2 →   +31 Writer with lower rating (like purple) tends to underestimate the difficulties of the problems, having fear to be regarded as too easy by contestants, and the problems actually become harder than usual.
•  » » » 6 years ago, # ^ |   0 Maybe so, but we have Zlobober for such problems :)
 » 6 years ago, # |   +65 Test cases of Problem B are fun to read. For eg.
•  » » 6 years ago, # ^ |   0 Lol good eyes.
•  » » 6 years ago, # ^ |   0 epic one :D
 » 6 years ago, # |   0 I have totally misunderstood B, I was searching for maximum length of concatenated substrings instead of maximum number of substrings and besides that I have passed 12 pretests :D
 » 6 years ago, # |   0 I hate this contest because this contest Ever not Normal and very hard ):
 » 6 years ago, # |   0 which data structure needs to E?
•  » » 6 years ago, # ^ |   0 sqrt decomposition
 » 6 years ago, # |   0 when will the ratings be updated. Please give the time
 » 6 years ago, # | ← Rev. 4 →   0 Why O(|a| * 26) solutions on problem B gets TL54?UPD.Answer here
 » 6 years ago, # |   -57 What a shit contest , fucking aweful :) allllekssssa dont creat contests anymore
 » 6 years ago, # |   +5 It was quiet contest for Div.2 participants.
 » 6 years ago, # |   0 Prob C : Is this a valid test case 4 1 2 3 0 0 Ans : 8 If so should be a good hack !
 » 6 years ago, # | ← Rev. 20 →   0 Rating should be given too much late. Follow topcoder's Rating system.
 » 6 years ago, # |   +30 Thanks to authors for good problemset!
•  » » 6 years ago, # ^ |   -9 It's good only for div1 not div2.Bcoz it was rated only for div2 and most of the contestant don't solve problem more than 1. problem A and problem B are huge difference.
•  » » » 6 years ago, # ^ |   +12 So, do you want to stay in Div2 forever? You should be able to solve problems like this to get higher in ranks, imo. And this contest was the one, where speed was really important, for example if you managed to solve A only. The problems were quite nice, looking forward for such challenging round further on.
 » 6 years ago, # |   +41 Thanks for the nice problems. Best Div-2 only contest in a while.
 » 6 years ago, # |   +1 Can somebody help me out here? My submission 11555558 for B gives MLE.I have no idea why.I use O(|a|) memory according to me.And now problemset wouldn't open to check.
 » 6 years ago, # | ← Rev. 2 →   -20 I think problem statement's are shit!!What is the approach for B ??I tried to find as many of string b as possible and then as many string c, and i tried c then b and printed the one with max non-overlaping substr and didn't work.this is my code
•  » » 6 years ago, # ^ |   0 I did the same and it passed. Ok I am joking,it didnt :). I am really curious to explain us a better programmer the reason.
•  » » 6 years ago, # ^ |   +2 Brute force solution: try all possible counts of b and calculate count for c. Find the case with max sum of counts for b and c.11550107
•  » » » 6 years ago, # ^ |   0 I had troubles solving B, but even had an idea like this, but thought that it is going to TL. Your solution seems clear to me, thanks alot for explaining!
•  » » 6 years ago, # ^ |   0 Did exactly the same. I believe there might be a case that fails it, but I couldn't come up with it during the contest, so submitted, and got wa on #12.It's a very long pre-test, so it's hard to see where your solution goes wrong, I hope the author can explain why this approach fails. ( or someone else).
•  » » » 6 years ago, # ^ |   0 Maybe something similar to this.. Input: aaaaaabbbbbb aba bab Output: abaabababbabHere I found it from a user above in the comments. Here we fail :P
•  » » 6 years ago, # ^ |   0 Binary search:Let N be a number of non-overlapping substrings in string a, that are equal to b or c. We want to maximize this number.Here is the main idea lo = 0 // the answer should be at least 0 hi = a.length()+1 // the answer can't be larger than a.length() while (hi - lo > 1) N = (hi + lo) / 2 doesThisNWork = false for each numberOfStringBinA = 0 ... N let numberOfStringCinA = N - numberOfStringBinA good = true for each character ch = 'a' ... 'z' if ( (number of ch in string a) < numberOfStringBinA * (number of ch in string b) + numberOfStringCinA * (number of ch in string c) ) good = false if good // we found a way to make numberOfStringBinA b's and // numberOfStringCinA c's in string a. doesThisNWork = true if doesThisNWork lo = N else hi = N 
•  » » 6 years ago, # ^ |   0 Ya I did the same But it will not contain all the case example aaaaaabbbbbb aab abb If you go by your approach then the answer would be B: 3 & C: 0 then C: 3 & B:0 which will both give you 3 as final answer whereas the final answer would be 4 B:2 C:2 So you have to take cases like this in consideration
 » 6 years ago, # |   +5 Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).
 » 6 years ago, # |   +2 most rating will be decided by how fast we solve problem A
 » 6 years ago, # | ← Rev. 2 →   +7 If you have TL54 in B, check int values.You should use long long. Maybe you have such lines with mistake:  for(int i = 0; i <= sz(a); i++){ bool ok = true; for(int j = 0; j < 26; j++) if(tmp[j] - i * usedB[j] >= 0) tmp[j] -= i * usedB[j]; You have i <= 1e5 and usedB[j] <=1e5. i * usedB[j] <= 1e10.
•  » » 6 years ago, # ^ |   0 Thanks a lot ! Finally i understood where i went wrong !
 » 6 years ago, # | ← Rev. 2 →   -12 very nice problems . tanks lot!
 » 6 years ago, # |   0 Can anyone tell me why my code was too slow for problem B? http://codeforces.com/contest/551/submission/11556052
•  » » 6 years ago, # ^ |   0 wow its so complex...
 » 6 years ago, # |   0 Why is my position changing to down after contest finish? After contest finish I was 1429, in this second I am 1446
•  » » 6 years ago, # ^ |   0 1448 :) Thank you for contest! Very intresting problems!
 » 6 years ago, # |   +4 First time reading C, D, E...
 » 6 years ago, # |   +19 What is the expected complexity for problem E? Tell me it's better that ...!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 Can be solved in O(Q*√N) using a hash map.
 » 6 years ago, # | ← Rev. 3 →   0 For the problem B i used this idea: Let a,b,c the input strings Let x the amount of only strings b in a. ans = 0 Now we can: iterate for i=[0..x] substract i strings from a. let j = the amount of string c in the remain string. if (i+j) > ans //save results print ans; I think this is the same that A >= i*(B)+j*(C) where A,B,C are column vectors (from string a,b,c) (sorry if it was incorrect. I am not good in maths) and we want the maximum value of: (i+j) How solve this math problem? thanks in advance
•  » » 6 years ago, # ^ |   0 Thanks for your comment, it helped me to develop a solution and understand it clearly.
 » 6 years ago, # |   0 This is my first time using C++ in a contest, and I'm having the following issue.The code for problem D runs correctly on my machine, but when I do the custom invocation, the answer always returns 0.Any ideas why? Thanks.
 » 6 years ago, # |   0 Auto comment: topic has been updated by allllekssssa (previous revision, new revision, compare).
 » 6 years ago, # |   +13 Thanks to all participants. We hope you have a good time and learn something new. Yes,those who are complaining dont want to learn anything and just want good ratings and easy problems
 » 6 years ago, # |   +6 Obviously this contest was harder than usual. Specially B seemed to suit for C and C for D. Whatever, still great contest due to the beauty of the problems.
 » 6 years ago, # |   +6 This contest was great! Many thanks to the authors.
 » 6 years ago, # |   +29 Congratulations to the real winners!Real Div.2 winners:
•  » » 6 years ago, # ^ |   0 Indeed. I believe it's better to ignore unrated Div-1 participants while announcing the round winners. It just gives them more motivation.
 » 6 years ago, # | ← Rev. 2 →   +22 Just noticed the dreamoon_love_AA test case in B. hahaha
 » 6 years ago, # | ← Rev. 3 →   +20 There are more funny tests. Like this:
•  » » 6 years ago, # ^ | ← Rev. 2 →   +13 I wrote all the funny testcases. My friend has nothing to do with it :)Also I have a lot of funny comments on Serbian ( some comments are about my friend, teachers, or my 'good' english ). I hope nobody feels hurt. I relly hadn't bad intention with testcases !
•  » » » 6 years ago, # ^ |   +3 Is that typo on test #45? I don't know the correct one between grandpa or she. Btw, I'm looking forward for your Pascal solution as you mentioned :)
•  » » » » 6 years ago, # ^ |   0 Zlobober sumbited my Pascal solutions ! Do you see it ?
•  » » 6 years ago, # ^ |   +1 I like testcase with Egor and tourist :)
 » 6 years ago, # |   +6 Admins , I just wanted to say one thing that all these people who participate in their first contests and get into top 5 or top 10 must be banned ! These discourages others who are working to get in top 5 because of these genius div1 players who make fake profiles to just see where they stand in div 2 . For instance in this contest 4 out of top 5 players are those who are playing in their first match and now voila these geniuses are in top 5 :/
•  » » 6 years ago, # ^ | ← Rev. 3 →   -7 Should Petr or ACMonster or vepifanov or rowdark or dreamoon_love_AA be banned? Codeforces isn't the only Online Judge in the world.People can practice in other Online Judges and then particpate in CF.UPD:In case of misunderstanding,I didn't say multi accounts shouldn't be banned(and I think unrated Div.2 winners in this round is from Div.1).All I say is banning all unrated Div.2 winners is not a good way to prevent multi accounts,I think.
 » 6 years ago, # |   0 It was a good contest.but I don't know why my B was not accepted. :\ :D good luck!
•  » » 6 years ago, # ^ |   0 As per previous comments above, your code won't pass the following test case:Input: aaaaaabbbbbb aba bab Output: abaabababbabIt assumes that the maximum answer will occur when string b is taken out fully before string c, but the maximum can occur for 'interior' solutions where b and c are not fully removed.Fix: Find max number of times b can be removed, then iterate through removing 1 to max b's (and any remaining c's per case) and find the instance with largest sum of b and c removed.
 » 6 years ago, # |   0 I have no idea why this submission gets runtime error on codeforces but runs fine on my local ide and codechef. http://codeforces.com/contest/551/submission/12304739. Please check.