Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

By BledDest, 9 months ago, ,

Hello Codeforces!

On March 06, 18:05 MSK Educational Codeforces Round 39 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This is a special Educational Round — Top three contestants among those who are eligible for participating in ACM ICPC will be invited to attend the Hello India x Russia Programming boot camp under the Codeforces + SDV banners, on a full team sponsorship.

Social Discovery Ventures (SDV) creates, develops and funds Internet projects specialising in communication platforms that enable people across the world to get closer and expand their social networks.

The winners will be fully sponsored with their boot camp participation fees, accomodation, and meals for the India location!

This round also has a special regional prize — the company Phaze Ventures, a platform founded to transform the region by unlocking the untapped potential of our youth, startups and corporates, will be sponsoring the top 3 participants of this round from Oman (also among those who are eligible for ACM ICPC) — further sharing the importance of supporting talented programmers and sending them to these types of events throughout the world.

The round will be rated for Div. 2. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 7 problems and 2 hours to solve them. Problem authors are PikMike, Vovuh and me.

Good luck to the participants! Hope you will enjoy the contest.

UPD: The tutorial has been published.

•
• +237
•

 » 9 months ago, # |   +97 It's not in the upcoming contests list?
 » 9 months ago, # |   -14 Will it be on Codeforces? Because it's not on the contest list of Codeforces.
•  » » 9 months ago, # ^ |   -32 Are you blind?
•  » » » 9 months ago, # ^ |   +4 Nope, but I think you need some memory refreshment as this contest was added in the list 1 day ago. My comment was before that time. Thank you.
 » 9 months ago, # |   +1 Wow, what a pleasant surprise.
 » 9 months ago, # |   -28 Acceptable start time for Chinese users:)Vote for the contest and it will appear on the HOME Page?
 » 9 months ago, # | ← Rev. 2 →   +69 Unfortunately, we cannot add the contest to the registration form right now, and when we will be able to do it, it might be too late for some participants.We've decided to postpone the round. It will start on March 06, 18:05 MSK (exactly 24 hours after initially announced time).
•  » » 9 months ago, # ^ |   +32 is it cause you forgot to thank mike
 » 9 months ago, # |   -54 Mandatory comment- "Hope the problem statements are as short as the announcement!".
•  » » 9 months ago, # ^ |   -16 take my mandatory downvote
•  » » 9 months ago, # ^ |   0
•  » » 9 months ago, # ^ |   0 It's actually long. So are you hoping long problem statements?
 » 9 months ago, # |   -14 Please rated for Div.1 and Div.2
•  » » 9 months ago, # ^ |   0 no, please, no
•  » » 9 months ago, # ^ |   +37 Maybe Div 1.5 (purples included)
•  » » 9 months ago, # ^ | ← Rev. 6 →   +56 http://codeforces.com/blog/entry/49826 (14 months ago)http://codeforces.com/blog/entry/58153#comment-418381I hope it will be rated personally for you and not to your fake accounts (http://codeforces.com/team/37327) .
•  » » » 9 months ago, # ^ |   -29 Stop crying dont be jeloussojfsijfops
•  » » » 9 months ago, # ^ |   0 gotem
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 Do you want to come back tip of Div.2?
 » 9 months ago, # | ← Rev. 2 →   -25 Удачи
 » 9 months ago, # | ← Rev. 3 →   +6 "Educational Round — Top three contestants among those who are eligible for participating in ACM ICPC will be invited to attend the Hello India x Russia Programming boot camp under the Codeforces + SDV banners, on a full team sponsorship. Social Discovery Ventures (SDV) creates, develops and funds Internet projects specialising in communication platforms that enable people across the world to get closer and expand their social networks."I have a question top winner are always top why you don't give a chance a pupil? they haven't anyy quality? Do a Randomly Winner.It will be help for him and her -_-
•  » » 9 months ago, # ^ |   -26 Losers are losers
•  » » » 9 months ago, # ^ |   0 But you are a pupil.. do you believe that you are a loser?
•  » » 9 months ago, # ^ |   +24 This is the bug of competetive programming — only the world best participants can win prizes, it is dissapointing -_-. A lot of newbies quickly lose interest -_-. In any other sports participants are divided according to their age/gender/rating etc. and it is possible to win the prizes in any competition, if you are good for it.
•  » » » 9 months ago, # ^ |   +5 Isn't that with many things? -_- gotem
 » 9 months ago, # |   -11 From where do we register for the contest??
 » 9 months ago, # |   +9 Clarification: everyone is eligible to win invitations or that is for div2 participants only?
 » 9 months ago, # |   -27 there is no contest on contests page..
•  » » 9 months ago, # ^ |   -16 Believe me, you are really blind!
•  » » » 9 months ago, # ^ |   +8 I know man. That's why I'm sometimes confusing your mom with my girlfriend.
 » 9 months ago, # |   0 I feel like educational rounds are kinda easier than regular CF rounds. Is that true?
•  » » 9 months ago, # ^ |   -10 "Educational"Of course they are supposed to be easier
•  » » » 9 months ago, # ^ |   +18 Educational doesn't mean easy. It is better to upsolve.
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +2 Indeed, it's always better to upsolve.
 » 9 months ago, # |   +1 The contest starts in 23 minutes, but I can not sign up...
•  » » 9 months ago, # ^ |   +3 Contest will start on Tuesday
 » 9 months ago, # |   +4 when can I register?
•  » » 9 months ago, # ^ |   -8 Before system testing!
 » 9 months ago, # |   -22 Hope the problem statements are not as long as the announcement
 » 9 months ago, # |   -8 I wish everyone hacks himself!
 » 9 months ago, # |   -32 please hit the like button of my comment
•  » » 9 months ago, # ^ |   -18 thanks all !
•  » » 9 months ago, # ^ |   0 This is not Facebook
•  » » » 9 months ago, # ^ |   0 I wanted to change my Contribution. 0 to anything.
 » 9 months ago, # | ← Rev. 2 →   -6 School 23:00 lights out,but the content begin in 23:05.so I urgently hope to 2 hours ahead of the game
 » 9 months ago, # | ← Rev. 3 →   0 “Top three contestants among those who are eligible for participating in ACM ICPC will be invited to attend the Hello India x Russia Programming boot camp under the Codeforces + SDV banners, on a full team sponsorship.”Are the finalists meant? Or any contestant who can participate in next ACM ICPC is eligible for the invitation?
•  » » 9 months ago, # ^ |   +11 Any of seasons 2017-2018 or 2018-2019.
•  » » » 9 months ago, # ^ |   0 Is it guaranteed?
 » 9 months ago, # | ← Rev. 3 →   +5 Russian translation states that it is possible to hack your own solution, while english original doesn't. Is this true and how would doing it affect your score?
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 It is "Educational" you don't take any score for hacks!
 » 9 months ago, # |   +16 What if someone has already paid for this? Can we get a reimbursement?
•  » » 9 months ago, # ^ |   +28 Hi evil666man!Let's discuss this after the results of this round.
 » 9 months ago, # |   +5 rating predictor is not working!!
•  » » 9 months ago, # ^ |   0 Now it does. Too late
 » 9 months ago, # |   +7 Extremely bad experience on problem C. 13 wa on problem C. Maybe I should go to sleep...
•  » » 9 months ago, # ^ |   +2 same here :(. wasted more than 40 minutes!
 » 9 months ago, # |   +4 How to solve D?
•  » » 9 months ago, # ^ |   0 we can use dp. dp states are dp[i][j] --> number of minimum hours he has to stay in the college if he skips 'j' lectures till the ith day!
•  » » 9 months ago, # ^ | ← Rev. 3 →   +17 Calculate pre[i][j] = Minimum time spent in university on i'th day after using j skips on this day.Then calculate dp[i][j] = Minimum time spent in first i days after using j skips.Answer is dp[n][k].Transition is dp[i][j]=dp[i-1][z] + pre[i][j-z]. 0<= z<= j
•  » » » 9 months ago, # ^ |   0 how to get pre[i][j] ?
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 spend time in university = r — l + 1; we can calculate cost[i'th day][spend time in university] = skip time then pre[i][skip time] = spend time in university
•  » » » » 9 months ago, # ^ |   +3 Observe that its useless to skip any lecture which is not at the beginning or the end.So, we should always skip some prefix and suffix of lectures.Let x be number of skipped prefix lectures and y be number of skipped suffix lectures.Try all x,y such that x+y<= k .pre[i][x+y]=min(pre[i][x+y], val)(pre[i][x+y] is initialised to inf)
•  » » » » » 9 months ago, # ^ |   0 So calculating pre[i][j] is a n^3 operation?
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +3 Both Pre-calculation and main DP are O(nk^2)
•  » » » » » 9 months ago, # ^ |   0 What's val in the above expression?
•  » » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 The time spent after skipping first 'x' classes and last 'y' classes.It can be calculated in O(1) if you store all lecture times in a vector.Let size of vector be vs.val= 0 if x+y>=vsval= v[vs-y-1]-v[x]+1
•  » » 9 months ago, # ^ |   +1 You may have an initial greedy idea to skip classes on endpoints of a day if skipping that class saves you the most number of hours. Unfortunately, this does not work because of the case2 8 2 10111101 11000011Greedy solution would skip first and last class on first day, but optimal solution is to skip first and second class on second day.We can make sets si for each day i that contain the hours that have classes. Then, for each day, we can calculate the minimum number of hours to attend class that day if we skip j classes on that day, and calculate this number for all j such that 0 ≤ j ≤ min(k, |si|).Once we have that, we do a simple dp, where our dp array has n rows and k + 1 columns. dpij will contain the minimum number of hours to attend class after day i while still having j days left to skip. Then, for the first row, we fill it up with the values we calculated in the last paragraph (i.e. dp[0][k] will be total number of hours of day 0, dp[0][k-1] will be minimum number of hours on day 0 if we skip 1 class, dp[0][k-2] will be minimum number of hours on day 0 if we skip 2 classes, etc.). For rows i > 0, we just test the possibility of skipping 0 ≤ j ≤ min(k, |si|) days from each point in the previous row.Then the answer will be the minimum number in our last row.
 » 9 months ago, # |   0 any idea what is test 16 for D?
•  » » 9 months ago, # ^ |   +6 Totally random test with n = m = k = 500
•  » » » 9 months ago, # ^ |   0 Shouldn't it be prefix/sufix calculation for each row then dp? I couldn't figure why my solutions fails for over an hour :D
•  » » » » 9 months ago, # ^ |   0 It should not, it can be arbitrary substring in a day
•  » » 9 months ago, # ^ | ← Rev. 3 →   +4 i think the test 16 is something like when we skip on ith day some starting lectures and some lectures from last for an optimal solution. e.g 2 6 2 101101 000000 ans=2
•  » » » 9 months ago, # ^ |   0 Very probable, as I made the same mistake of not including that case :c
•  » » » 9 months ago, # ^ | ← Rev. 2 →   0 Yes exactly !! I forgot to consider that case when some prefix as well as suffix is skipped
•  » » 9 months ago, # ^ |   0 I also got WA on test 16, mostly it would be the case of having some prefix and some suffix skipped on a particular day, as I was considering either of them on one day not both.
 » 9 months ago, # |   -6 D is harder than usual
 » 9 months ago, # | ← Rev. 2 →   0 Well, I solved E in about 15 minutes, and still wondering how could so many people solved D successfully.Can anyone give me a hint? ;)
•  » » 9 months ago, # ^ |   0 http://codeforces.com/blog/entry/58155?#comment-418680Btw can you please explain your approach to E?
•  » » » 9 months ago, # ^ | ← Rev. 3 →   +27 First of all, here is my submission (36014589), in case my explanations are unclear. ;)With each test, provided that the number in the input is guaranteed to have an answer, we are sure that there is an answer with (|S| - 2) '9' digits (perhaps not the most optimal one, just get moving on).Now to find an answer with |S| length.First, we can use an array to store the number of appearances of each digit. Along with that, we will know the number of digits that has an odd appearance count.For example, with 28923845, we have count(2) = count(8) = 2 and count(3) = count(4) = count(5) = count(9) = 1.Since the answer is strictly lower than the given number, we can iterate the string from right to left. With each digit position, we can do the following: If an answer has been found before, terminate all iterations. If not, iterate all digits lower than the current one in a decreasing order. This time, all digits to the right of the digit we're iterating can be arbitrarily large without violating the "strictly-lower" criterion, therefore, an answer will be found if: There are enough digits to the right to compensate with the current number of digits with odd appearance count. If 1 is satisfied, the remaining digits to the right (after excluding the one used for compensation in step 1) must be an even number (to not creating another odd appearance count again). If both are satisfied, then an answer is found: which is all digits to the left of the iterating one (order remained the same), the value we're working on with that digit, and the digits to the right, which are modified according to the above criteria to keep the number "beautiful" and make it as large as possible.Taken the example of input 28923845 again.Starting at digit 5. As we're not working with this digit any more, decrease count(5) by 1, i.e. count(5) = 0 now.Since we still have 3 distinct digits with odd appearance count (3, 4 and 9), it is certain that we can't find an answer here. So we move on to digit 4.Again, we have to decrease count(4) by 1, i.e. count(4) = 0.Let's replace that digit with '3'. So, count(3) will be increased by 1, i.e. count(3) = 2.Now, only digit 9 has an odd appearance count, and we have exactly one digit to the right to spare, so we will set the value of that digit to '9', so all digits will have even appearance count. The answer is 28923839.P/s: What if the input is 44400000?Since no digit is lower than 0, we will surely start at the rightmost 4.Let's replace it by 3. Of course, we can replace a digit on the right by 3 to compensate, and there are 4 digits left un-handled. Since it is an even number of digits, we can safely replace all 4 of them with 9.The answer is constructed by the following: first two 4 digits on the leftmost (their states don't change at all), the digit 3 (replaced from the initial rightmost 4), and on the right, we have four 9s and one 3. We will write them from left to right in a descending order to make sure the number's value is largest possible.The answer for this input should be 44399993.Hope that this help you! ;)
•  » » » » 9 months ago, # ^ |   +1 The answer for 2892384500 should be 2892384493, not so?
•  » » » » » 9 months ago, # ^ | ← Rev. 2 →   +1 Ouch, my bad :-P trying to clarify the case with exceeded digits but looked like I used a wrong case.Will fix it soon enough ;)UPD: I have fixed it! :D
•  » » » » 9 months ago, # ^ |   +4 thanks a lot mate :)
•  » » » » 9 months ago, # ^ |   +4 Many thanx to you!After reading your explanation  —  ez-AC :)
•  » » » 9 months ago, # ^ |   0 Also, thanks for the hint for D ;)I got stuck with greedy for about 30 minutes, and after solving E, for some reasons my mind just froze and couldn't visualize a clear DP approach for it :-P
•  » » » » 9 months ago, # ^ | ← Rev. 2 →   +3 Didn't solved it but seen the same type before usually solved by DP+Bit
 » 9 months ago, # |   +1 C is very easier than usual and D is harder than usual...
 » 9 months ago, # |   0 Was D meant to be a solved in a Knapsack Problem way?
 » 9 months ago, # |   +4 Damn Codeforces, it became too slow towards the end
 » 9 months ago, # | ← Rev. 3 →   +13 I am not a grammer nazi, but this — If you can gen the string that will be obtained from the given string and will be contain english alphabet as a subsequence, print it.UPD: It's fixed.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +1 Hoyl, why did nobody tell us this during the contest!? Sorry, it should be fixed now, statement will get updated in a couple of minutes.
 » 9 months ago, # | ← Rev. 3 →   +1 How to solve C if we are asked to find the minimum number of operations (for any string s and t)
•  » » 9 months ago, # ^ | ← Rev. 2 →   +6 DP[i][j] indicates the minimum way to solve the suffix ending at index i, with j as the letter we are currently trying to assign (starts at 0, goes to 25), S is the input stringDP[i][j] = Min(S[i]-j + DP[i+1][j+1], DP[i+1][j]) — if S[i] <= jDP[i][j] = DP[i+1][j] ------------------------------------ if S[i] > jO(N*Alphabet)
•  » » » 9 months ago, # ^ |   0 I think cases should be swapped, but the idea is same. Thank you
•  » » » » 9 months ago, # ^ |   0 Oh, right, thanks I'll fix it.
 » 9 months ago, # |   +61 is there anyone else who cannot see others solution to hack!!!??
•  » » 9 months ago, # ^ |   +17 Same issue
•  » » » 9 months ago, # ^ |   +1 same issue, I am also not able to see solutions to hack!!
•  » » » » 9 months ago, # ^ |   0 Same here...
•  » » 9 months ago, # ^ | ← Rev. 2 →   +18 I'm investigating it. Thanks. Fixed!
•  » » » 9 months ago, # ^ |   0 How come some are hacking and some of us are not able to see the solutions..
•  » » » » 9 months ago, # ^ |   +3 Up until now, people are only hacking their own solutions (the only solutions they can see right now).
•  » » » » » 9 months ago, # ^ |   0 yup got it, in fact the problem has been fixed now
 » 9 months ago, # |   +4 How to solve problem E?
 » 9 months ago, # |   0 How can i hack others solution ?
 » 9 months ago, # |   +13 It's sad that my F couldn't get accepted because I didn't initialize 2fib0 and 2fib1 :(
 » 9 months ago, # |   +4 So I ended up writing a dp solution for problem C which finds the minimal number of moves. And after the contest I noticed in the problem statement "Your target is to make some number of moves (not necessary minimal)..." :|
 » 9 months ago, # |   0 Implementation issues in D :( Good problem, though, finally a DP problem I was close to solving.
 » 9 months ago, # |   0 Is it possible to view other's solution ?
 » 9 months ago, # |   +23 seems most of them are hacking them self!lol XDXDXDonly a few who hacked others!! haha
•  » » 9 months ago, # ^ |   0 Still, i am not able to see any other solution to problems. Ha Ha HaHack to other solution how possible without a see code.
•  » » 9 months ago, # ^ | ← Rev. 2 →   +1 What is the test hack for problem C? I understand now.You are allowed to do multiple replacements for the same position of the string.
 » 9 months ago, # |   +5 For the last question. maintaining prefix LIS and suffix LIS in same segtree and function as sum of both.(we subtract i from each a[i] initially and coordinate compress the array) Can we do something like doing rollbacks on a segment tree in one direction and normal lazy updates in another direction. Does this work?
•  » » 9 months ago, # ^ |   0 I'm not sure whether we can do it using only one segment tree, but model solution uses two segment trees with almost the same approach.
•  » » 9 months ago, # ^ |   0 I have used one segment tree. There was no need of rollbacks, lazy updates, dynamic segment tree whatsoever. Only range query and point updates.Solution
 » 9 months ago, # |   0 How decreasing memory to solve D.
 » 9 months ago, # |   0 http://codeforces.com/contest/946/submission/36016554 can anyone provide a test for which this fails?
•  » » 9 months ago, # ^ |   0 Not allowed to view request page :/ Pastebin/Ideone?
•  » » 9 months ago, # ^ |   +8 4 16 11 1111011101111111 0111110111111111 0011101111011000 0000010000001000 Yours : 31 Jury : 30 
•  » » » 9 months ago, # ^ |   0 thank you
 » 9 months ago, # | ← Rev. 3 →   0 I had like a minute left and read problem G and BS'd an answer that was basically copy-paste from LIS template.Threw it together in <30 seconds and submitted without compiling, WA on test 20 lol 36021949EDIT: I realize the error and I'm surprised it made it as far as test 20.
 » 9 months ago, # |   +20 In Berland students study in the university 500 days a week
 » 9 months ago, # |   0 How did http://codeforces.com/profile/assbb solve D and E but not the first 3? Seems a bit curious to me.
 » 9 months ago, # | ← Rev. 2 →   +54 How this output is ok for problem C? UPD: Fixed and this solution got hacked.
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 Because the output is not "-1" maybe.
•  » » 9 months ago, # ^ |   -11 "You are allowed to do multiple replacements for the same position of the string."
•  » » 9 months ago, # ^ |   +8 We are investigating the issue.
 » 9 months ago, # | ← Rev. 3 →   -13 Why do so many people have weird barely readable aliases in their solutions, even for simple problems? Like this, for example.
•  » » 9 months ago, # ^ |   0 So that hackers stay away?
•  » » » 9 months ago, # ^ |   0 Extract from CF Contest Rules"It is forbidden to obfuscate the solution code as well as create obstacles for its reading and understanding. That is, it is forbidden to use any special techniques aimed at making the code difficult to read and understand the principle of its work."
•  » » » » 9 months ago, # ^ |   0 & I think nobody follows this
•  » » » » 9 months ago, # ^ |   0 I guess these short alias namings just a bit quicker to write
 » 9 months ago, # |   0 Did someone solve E using Binary Search by fixing the length of the prefix then generate the appropriate suffix?
•  » » 9 months ago, # ^ |   +6 Yes, I did.36015253
 » 9 months ago, # |   +8 I've just been hacked on problem A, Actually I discovered that I understood it wrong ... but my solution passed during the contest. I don't think that you should put so weak tests like those so solution for another problem pass!!!Hacking is for some tricky case or clever case that makes the solution wrong but not for making absolutely wrong solutions pass during the contest and then hack them after the contest. I really think you should rethink about that.
•  » » 9 months ago, # ^ |   -16 The tests are not final. All the solutions will be re-tested on successful hacks after the hacking finishes. One of the points of competitive programming is that you should test your solutions better yourself.
•  » » » 9 months ago, # ^ |   +10 I said I understood the problem wrong ... is it logical for a solution of a problem pass another one!! That's my point, I'm not saying that they should put all the tests, but totally wrong solutions shouldn't pass!!
•  » » » » 9 months ago, # ^ |   +9 Yes, actually I too wanted to raise the same issue, the testcases should not be so weak that it passes absolutely wrong solution, like at least it should cover all the basic cases.
 » 9 months ago, # |   -10 Test: #1, time: 15 ms., memory: 1908 KB, exit code: 0, checker exit code: 0, verdict: OKInputaacceeggiikkmmooqqssuuwwyyOutputaacceeggiikkmmooqqssuuwwyyAnswerabcdefghijklmnopqrstuvwxyzChecker Logok Okwhy checker log is ok ok? for problem A this submission
•  » » 9 months ago, # ^ |   0 really weird.
•  » » 9 months ago, # ^ |   0 this comment also says the same. It seems like a lot of them would be hacked
•  » » » 9 months ago, # ^ |   +3 If the judge status were correct then the contestant could have a second chance.
•  » » 9 months ago, # ^ |   0 Same thing happened to me in C.SUBMISSION LINK:http://codeforces.com/contest/946/submission/36018053It got accepted during the contest but now the same solution is giving "Wrong answer on test 1."
 » 9 months ago, # |   0 how to approach B. My solution gives wrong answer for large test cases.
•  » » 9 months ago, # ^ |   0 brute force. take mod while a>=2*b and b>=2*a
•  » » 9 months ago, # ^ |   0 There is an "else if" missing in Line 15 in your code, without this "else if" the while loop breaks if the condition on Line 15 is not satisfied, however, your code won't pass even if you fixed this line because of the input constraints (10^18) and will give you TLE.The right approach is to subtract the quotient of the division of a by 2*b from a and subtract the quotient of b by 2*a from b while you can instead of subtraction.My AC Submission : Link
 » 9 months ago, # |   +3 What is the solution for F?
•  » » 9 months ago, # ^ |   0 I did not solve it incontest and nor have I submitted it later, but pretty sure this is the solution (Confirmed by comparing it with accepted codes).Basically notice that when you make the ith fibonacci string you already have a concatentation of F(1)...F(i-1) present so its F(i)...F(i-1)F(i-2)F(i-1)An important intuition is that the number of occurences of the string s in F(1)...F(i) can be broken as number of occurences of some prefix of s in F(1)...F(i-1) and number of occurences of the remaining part of s in F(i). [We multiply these].To do this, we maintain 2 types of DP. till[i][l][r] stores the number of ways to get s[l...r] as a subsequence till the ith fibonacci string. curr[i][l][r] stores the number of ways to get s[l...r] as a subsequence in the ith fibonacci string. Notice that for each way in till[i-1][l][m] we can match it with a way in curr[i][m+1][r]. Thus we multiply these. We apply a similar logic for the transition of curr. In simple terms these events are independent so they're multiplied.Transition: 1. curr[i][l][r]+=curr[i-2][l][m]*curr[i-1][m+1][r] for all m in [l, r) 2. till[i][l][r]+=till[i-1][l][n]*curr[i][n+1][r] for all n in [l, r)The final answer is till[x-1][0][n-1] if fibonacci index = x and length = n (0 based indexing)
•  » » 9 months ago, # ^ |   0 Firstly, for every subsequence that is exactly the pattern, it will appear in 2^(positions free to the left) * 2^(positions free to the right).left[i][l][r] = sum of 2^(positions free to the left) for every subsequence that contains exactly characters [l, r[ in the patternright[i][l][r] = sum of 2^(positions free to the right) for every subsequence that contains exactly characters [l, r[ in the patternsub[i][l][r] = number of subsequences that contains exactly characters [l, r[ in the patternsub[i][l][r] = (sum l <= m <= r of sub[i — 1][l][m] * sub[i — 2][m][r]) + sub[i — 1][l][r] + sub[i — 2][l][r]left[i][l][r] = (sum l <= m <= r of left[i — 1][l][m] * sub[i — 2][m][r]) + 2^(size of f(i — 1)) * left[i — 2][l][r] + left[i — 1][l][r]right[i][l][r] = (sum l <= m <= r of sub[i — 1][l][m] * right[i — 2][m][r]) + 2^(size of f(i — 2)) * right[i — 1][l][r] + right[i — 2][l][r]The subsequence either has parts in f(i — 1) and f(i — 2) (the summation part) or is completely inside f(i — 1) or f(i — 2) (the rest). But this isn't the complete answer because it has 2^(one side). So the answer comes either from f(i — 1) and f(i — 2) or from one of them so:ans[i] = ans[i — 1] * 2^(size of f(i — 2)) + ans[i — 2] * 2^(size of f(i — 1)) + (sum 0 < m < n of left[i — 1][0][m] * right[i — 2][m][n])
•  » » 9 months ago, # ^ |   0 This was 2012 ACM ICPC World Finals problem D. A thorough explanation can be found at:https://www.youtube.com/watch?v=dPFq4OLc-_Q
 » 9 months ago, # |   +8 Did the image change just now?
 » 9 months ago, # |   0 In D, how could O(n*m²) solutions run in less than 100ms for some people?
•  » » 9 months ago, # ^ |   +11 n = 500 with o(n ^ 3) just so fast. Btw, for O(n ^ 2), if the operations are not complicated, it works for n = 10000.
 » 9 months ago, # | ← Rev. 3 →   0 On problem A ,I think the statement was very confusing. What was meant by "You may partition this sequence into two sequences"?? It seems the sequence should be partitioned into two contiguous part. Here 'partition' and 'sequence' have created confusion. The author should chose words carefully. I misunderstood it. Unfortunately the test cases was so weak that they passed for my wrong solution. Who always read explanation of test cases on A !!
•  » » 9 months ago, # ^ |   +1 I wasted 10 minutes on this problem and got a penalty of 20 minutes because in my first submission i thought that I must maintain the order of the input and build a prefix sum array to know the best position of splitting :\
 » 9 months ago, # |   0 Problem A was written in a very bad way that I didn't know whether should I treat the input as a contiguous sequence or 2 subsequences after splitting and that cost me 30 penalty points.Problem C test data was soooo weak and that resulted in hacking a lot of submissions including mineI hope you consider these 2 issues in the next round, the weak test data and the bad problem formulation
•  » » 9 months ago, # ^ |   +3 It says "in two sequences". I think this is pretty clear. They would say subsegment if they meant contiguous numbers
 » 9 months ago, # | ← Rev. 6 →   -11 SERIOUS BUG !!!!!!( DO READ THIS)/*InputaacceeggiikkmmooqqssuuwwyyParticipant's outputabcdefghijklmnopqrstuvwxyyJury's answerabcdefghijklmnopqrstuvwxyzChecker commentok Ok*/How did my solution for C got accepted verdict? It's not giving correct answer even for the 1st testcase.Here's the link to my accepted solution(during the contest, it got hacked now): http://codeforces.com/contest/946/submission/36018053Another thing, now if you try to submit the same solution, it gives "wrong answer on test 1".As you can see it clearly gave wrong answer for the test case but the verdict is "ok,ok" :(. Can you please fix this? this is a real serious bug. Btw, it really screwed my contest. Now,I am literally inventing ways to screw a contest :(./*InputaacceeggiikkmmooqqssuuwwyyParticipant's outputabcdefghijklmnopqrstuvwxyyJury's answerabcdefghijklmnopqrstuvwxyzChecker commentok Ok*/Thanks!
•  » » 9 months ago, # ^ |   +25 There was an issue in the checker, for some tests it returned OK instead of WA. It is really unfortunate but it is not a dramatic issue because you can always assume that there weren't such tests during a contest. Obviously, this argument can't be applied to wa1, though our estimated number of people affected is not that great. The participant can literally check his output for the sample case himself. We are still really sorry about it, the checker is fixed now and we will do our best in the following rounds to eliminate the possibility of similar mistakes.
•  » » » 9 months ago, # ^ |   -26 Hi VovuhShouldn't this round be made unrated for all the users who experienced the same problem?Thanks!
 » 9 months ago, # |   +3 Subsequence of the string is the string that is obtained by deleting characters at some positionsDid this note mean any thing to the solution in problem C ?because it mean we can just print abcdefghijklmnopqrstuvwxyz or im wrong ?
•  » » 9 months ago, # ^ |   +3 For example, see this test case (note the z at the 2nd position)azbcdefghijklmnopqrstuvwxyzThere is a subsequence valid if we delete the first z, but we didn't use any change operation so the correct output is:azbcdefghijklmnopqrstuvwxyzThe output must contain the changes you made for the string to be ok, but deleting a character is not a "change".Hope this helps you!
•  » » » 9 months ago, # ^ |   0 But he didnot say that i must made a change he just need the final subsequence
•  » » » » 9 months ago, # ^ |   +3 Actually it says "You need to print the string that will be obtained from the given string and will be contain english alphabet as a subsequence" and "If you can get a string that can be obtained from the given string and will contain english alphabet as a subsequence, print it."It says to print the changed string that contains the alphabet as subsequence, it does not say to print the subsequence. I agree that it could not be 100% clear at first sight :p
 » 9 months ago, # | ← Rev. 2 →   +11 Please put stronger pretests in futur contests, We really don't want this awesome website to turn to Hackforces instead of Codeforces, this is really bad I mean I understand that this whole pretests thing is necessary due to huge number of participants but really try to make sure you put some strong pretests (sometimes a completely wrong solution can pass pretests... ) . In addition to that the hacks idea is really good but I think the hacks should not be very easy like they are now ( some people don't even read the code they just try limit input data and see if they get lucky hacking the solution )
 » 9 months ago, # |   +9 After doing 108 successful hacks and then later know that it doesn't give you points in educational rounds..
•  » » 9 months ago, # ^ |   +3 its doesnot give you point but if your rank is 300 and you hacked user with rank 299 you will be 299 so its good to hack
•  » » 9 months ago, # ^ |   0 I was thinking to send a message to inform you but I said maybe he do it for a purpose.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +1 I enjoyed it :D, hacked many div1 users.
 » 9 months ago, # |   +17 When should rankings for div 2 update?
 » 9 months ago, # |   +1 How is penalty calculated in educational rounds?
•  » » 9 months ago, # ^ |   +4 Sum of 1)Time taken for all questions from start of question to accepted solution 2)20*no. of wrong submission
•  » » » 9 months ago, # ^ |   +1 Oh thanks for that. 20 seems quite high tho, considering around 1000 people solve 3 in 30 mins.
•  » » » » 9 months ago, # ^ |   +3 Yes, in my opinion in should be lowered, as it is blown out of proportion against time penalty in educational rounds.
 » 9 months ago, # |   +2 Why during system test of ACM-style contest pending runs are shown with -x instead of ?x`? And API also says that result is final, but some submits are pending
 » 9 months ago, # |   +40 Why the rating has not changed so far ?
 » 9 months ago, # |   +5 BledDestThis is with regard to question C 946C - String Transformation. I have solved the question C but after system testing i got TLE.But to my surprise when i resubmitted the same code after the system testing it got accepted . I am posting the links of 2 submissions here one with TLE and other with Accepted.one with TLE — 36008794one with Accepted — 36055044and both solutions are same , you can check yourself by comparing diff(they have no diff)Can you please see this issue?
 » 9 months ago, # |   0 These are my hacking testcases.. I did 108 hacks with them for B:3 10000000000000000001000000000000000000 4999999999999999949999999999999999 11 1000000000000000000
 » 9 months ago, # |   +16 When rating update will happen for div 2 :(
•  » » 9 months ago, # ^ |   +1 So u were waiting :D You became specialist. Congrats (Y). I became green :D
•  » » » 9 months ago, # ^ |   0 thank you <3 good luck next contest
•  » » » » 9 months ago, # ^ |   0 thank you <3 good luck next contest
 » 9 months ago, # | ← Rev. 2 →   0 My cf predictor shows my rating will increase by 125(it has not been wrong yet) . This result was shown to me just after finishing the system testings. As cf rating changes has not been updated yet, may i assume that cf will use a new formula this time to calculate new ratings? Some of the results by cf predictors looked unfair to me. So new formula won't be bad if authority approves.
 » 9 months ago, # |   +12 When rating update will happen for div 2 ^_^
•  » » 9 months ago, # ^ | ← Rev. 3 →   0 do you copy past codes like comments? so .. you are just green :/ my_comment
•  » » » 9 months ago, # ^ |   0 i just saved my comments_copy_rights c.
•  » » » 9 months ago, # ^ |   0 no i write my code ,but i too lazy to write comments when it written already
 » 9 months ago, # |   +5 I think that the reason that the rating is not updated yet is because of the error in the previous test of problem C.
 » 9 months ago, # |   0 rating has just updated now wow ;)
 » 9 months ago, # | ← Rev. 2 →   0 nvm
 » 9 months ago, # |   0 Who won the special prizes?