### Endagorion's blog

By Endagorion, 6 years ago, translation,

Hello, Codeforces!

On March, 2nd at 10:00 MSK Codeforces Round #295 will be held in both divisions.

The round will be held at the same time with Winter Computer Camp olympiad, the problemsets will be highly similar. The problems are by me (Endagorion) and Evgeny Savinov (savinov). The problems are prepared by members of the Winter Computer Camp technical committee: Georgy Chebanov (gchebanov), Filipp Rukhovich (DPR-pavlin), Alexander Mashrabov (map), Sergey Kiyan (sokian), Konstantin Semenov (zemen), Kinan Alsarmini (Sarkin).

Big thanks to Max Akhmedov (Zlobober) for his help with preparing the problems, Maria Belova (Delinur) for translating the statements in English, and Mike Mirzayanov (MikeMirzayanov) for creating Codeforces and Polygon systems.

The scoring is standard for both divisions: 500-1000-1500-2000-2500.

Please note that the Winter Computing Camp olympiad is scheduled to finish later than the Codeforces round. Thus, we ask you not to discuss the problems and solutions in the comments until 14:10 MSK. Also, viewing of other participants' solutions will be closed until that time. The editorial will also be published later.

UPD: you are free to discuss the problems now.

UPD2: the editorial is finally up! Sorry for the delay.

Also, grats to our Div.1 winners:

Special respect goes to Petr and rng_58 for solving the hardest problem E!

• +468

 » 6 years ago, # |   +133 Holy shit!!! There is eight Grandmaster and one International Grandmaster...
•  » » 6 years ago, # ^ |   +117 Red Alert! :P
•  » » » 6 years ago, # ^ |   +27 And there is some MikeMirzayanov !!!
•  » » » » 6 years ago, # ^ |   -45 when i saw your comment i just had to make this
 » 6 years ago, # |   +14 It's gonna be LEGEN wait for it DARY!!!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +17
 » 6 years ago, # |   -47 artofproblemsolving
 » 6 years ago, # | ← Rev. 3 →   +4 I even had to write my homework at Roumanian, which was pretty hard to do for being able to compete, so I hope it is going to be a round with very nice problems :)
 » 6 years ago, # |   +299 Div1 participants be like
•  » » 6 years ago, # ^ |   0 funny
 » 6 years ago, # |   +6 I am scared!
 » 6 years ago, # |   +30 Feeling unfortunate for not able to participate in such a "red hot" contest due to exams. :(
 » 6 years ago, # |   +9 It's good that I have school just in the afternoon :D(on the other hand, will I wake up so early?)
•  » » 6 years ago, # ^ |   +8 Oh, come on, 5 hours till the contest, why sleeping at all?
•  » » » 6 years ago, # ^ |   +3 Because I'd be sleeping at lectures otherwise (again) and it's not very nice to lecturers to always sleep through everything :D
 » 6 years ago, # |   -10 To sleep or not to sleep...
•  » » 6 years ago, # ^ |   +8 I always hated English class -_-.
•  » » » 6 years ago, # ^ |   0 ditto! but my English is poor!
 » 6 years ago, # |   -28 Such a beautiful day on most places in planet earth, would love to get some minus from the awesome people in codeforces.
•  » » 6 years ago, # ^ |   -13 challenge accepted:))
 » 6 years ago, # |   -13 wish you all best luck
•  » » 6 years ago, # ^ |   -22 Thanks. I love you
 » 6 years ago, # | ← Rev. 2 →   0 Is it possible to unregister for the contest now ?I registered earlier but just realized that I can't participate due to some reasons... I just don't want my rating to be screwed up because of such a mistake of mine...
•  » » 6 years ago, # ^ |   +22 if you don't submit anything your rating will not be changed, also you can unregister by finding your name in the list and then clicking on the X sign
•  » » 6 years ago, # ^ |   +3 If you don't submit anything , your ratings will not be screwed
 » 6 years ago, # |   0 want to enjoy this contest and hope rating increases :P
 » 6 years ago, # |   0 The contest is very bad time in IRAN
 » 6 years ago, # |   +4 where's the score ditribution ??
 » 6 years ago, # | ← Rev. 2 →   +120 7 Problems and 10 Red problem setters...
•  » » 6 years ago, # ^ |   0 Not everyone in the list is a problem setter :)
 » 6 years ago, # |   +7 I have missed my academic Classes and waiting for Codeforces Round 295.
 » 6 years ago, # | ← Rev. 2 →   +12 No rooms???Edit: Fixed
 » 6 years ago, # |   +12 where is rooms?
 » 6 years ago, # |   +5 :'(
 » 6 years ago, # |   +121 nice modulo used, first time 1000000007, second 1000000009, third 1000000007
•  » » 6 years ago, # ^ |   +29 Yeah.I got a wrong answer because that.It's stupid.At least, they could put it in statement description in this form, not 10^9 + 9...
•  » » » 6 years ago, # ^ |   +3 Yyyy, is 1000000009 clearer than 10^9 + 9 ; d? But I agree that those modulos were pretty stupid...
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +24 You can copy-paste 1000000009, which removes some room for error.
•  » » » » » 6 years ago, # ^ |   0 Yes, that's what I wanted to say.If you read 10^9 + 9 and type one more 0, your program will get WA and you'll never know why :))
•  » » » » » » 6 years ago, # ^ |   0 Cause of this I write mod = (int)1e9+9;
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 ModInt.h: template class ModInt I always use my template like it, so I'll write code such as "ModInt<>", rather than "ModInt<1000000009>", because of stupid habit.
•  » » 6 years ago, # ^ |   0 Unpredictability.
•  » » 6 years ago, # ^ |   0 Now I know what was wrong with my code :(Single change of line gets acc :/
 » 6 years ago, # |   +50 See more on Know Your Meme.
 » 6 years ago, # | ← Rev. 2 →   +13 Were there any successful hacks during this round?!Edit: Xellos beat me to it :)
•  » » 6 years ago, # ^ |   0 A pretty solid amount. If we're talking both divisions obviously.
 » 6 years ago, # | ← Rev. 2 →   -8 I almost solved E in Div.2 I think I've got right answer for (1 <= n <= 15) But how can I get n Combination k when (n,k > 15)?
•  » » 6 years ago, # ^ |   +14 Good! Today you have answer for n,k<=15,tommorow to n,k<=30 ... after around 7500 days you certainly have correct solution :D
•  » » » 6 years ago, # ^ |   -8 So I have to wait for 20 years.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 Or you could copy some of it(answers) and buy yourself some years :)
•  » » » 6 years ago, # ^ |   0 I finally got AC. 29 hours......
 » 6 years ago, # |   0 mogityantt testebi da amocanebii,meore amocanis 4 testis shemdgenels movutyann suyvelaperiiiiii ( :) <3 best wishes!!! )
 » 6 years ago, # |   +5 Problems were fantastic, I LOVED this contest. It was more think-based than algo-based.
•  » » 6 years ago, # ^ |   0 shen chemi dzma gemeixede aqett O_o mogityann azrovnebaa ,ra iyoo kaii mitxarii ertiii haa?
 » 6 years ago, # |   0 how to solve problem C Div.2? Ô.Ô
•  » » 6 years ago, # ^ |   +19 Please, wait, we can't discuss the problems yet.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 (-- apparently I should hide this --)
•  » » » 6 years ago, # ^ |   0 It's little like Greedy
 » 6 years ago, # |   +7 Today was very nice time for Korean Users.I always woke up in dawn to compete.
 » 6 years ago, # |   +35 In case anyone missed it:we ask you not to discuss the problems and solutions in the comments until 14:10 MSKThat's 2 hours from now.
 » 6 years ago, # | ← Rev. 2 →   0 Div2 D and E were HARD. (at least for me, unexpectedly harder than the usual D2 D and Es) :(
 » 6 years ago, # |   +1 It was nice. thank you.
 » 6 years ago, # |   +1 this round is hard :) but has got nice problems.
 » 6 years ago, # | ← Rev. 4 →   -11 Div2 C was easier than B :'( :'( :'( That's unfair...UPD: Wait!! Don't downvote, I'm sorry. Div2 C was the hardest one among all.
•  » » 6 years ago, # ^ |   0 I don't think so. Div2 B was simple if you just look backwards than forward. Div2 C took me 30-40 min with all that analysis :P
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 Damn it! Whatever, problem C took me 15 minutes but the contest was over :'(
•  » » » » 6 years ago, # ^ |   0 Happens man :)
 » 6 years ago, # | ← Rev. 4 →   +36 The system test was so fast because of the very small number of sources which passed the pretests :)) Problem A scared a half of the registered peopele in div1...even me, but I had woke up already so what did I have to lose?Excepting the rating, of course :))
•  » » 6 years ago, # ^ |   +6 Hm, that possibility of not submitting code if one solved it too late is wrong and should be changed...
 » 6 years ago, # | ← Rev. 2 →   +3 During contest, I tried to hack B problem with N == M. Why it is not a valid input? Where does the problem statement say that M has to be different that N?Update: Got it. I have to sleep more, lol!
•  » » 6 years ago, # ^ |   +17 The first and the only line of the input contains two distinct integers n and m (1 ≤ n, m ≤ 104), separated by a space .
•  » » » 6 years ago, # ^ |   0 Oh, my bad. Thanks!
•  » » 6 years ago, # ^ |   0 Read the input line properly, its given distinct n,m
 » 6 years ago, # |   +125 Codeforces round 287 : Rank 192, rating change 1582 to 1699 Codeforces round 295 : Rank 95, rating change 1612 to 1699
•  » » 6 years ago, # ^ |   +4 I'm a bit luckier than you. My rating now is 1698 -_-
•  » » 6 years ago, # ^ |   0 I undersatnd you, man.Just take a look at my rating.I had contest when it increased being on positions like 300 and now, it decreased me ~100 taking position 300.So a differnce of differnces of more than 100 having the same position :(
•  » » 6 years ago, # ^ |   +11 You got your brother man!! :D check this out http://codeforces.com/profile/dc26
•  » » » 6 years ago, # ^ |   0
•  » » » 6 years ago, # ^ |   +1 Yeah that's me
•  » » 6 years ago, # ^ | ← Rev. 9 →   +20 Kind of similar story :pCodeforces Round #295 (Div. 2) 114 3 +52 1699 Codeforces Round #294 (Div. 2) 366 3 -52 1647 Codeforces Round #293 (Div. 2) 212 4 +73 1699
•  » » 6 years ago, # ^ |   +49 1699 to 1699 ._.
 » 6 years ago, # |   +48 I spend very much time understanding the meaning of Problem B.QAQ
•  » » 6 years ago, # ^ | ← Rev. 2 →   +9 I still don't understand the idea of that problem.Was stupidly easy.You had just to implement it without needing an idea or something.I say this even thouth I solved it...it wasn't interesting, and compared to the others it doesn't find its place in this contest.The rest of the problems seemed ok event thougth that A and C were counting problems and I didn't read D and E during the contest
•  » » 6 years ago, # ^ |   +8 There were only 20 minutes left when I truly understood the meaning of Problem B.T^T
•  » » 6 years ago, # ^ |   0 Question like this (involving complicated, non-trivial process) should deserve explanation of the sample input at least.
 » 6 years ago, # |   0 Can anybody tell how to solve div-2 E ??
•  » » 6 years ago, # ^ |   0 maybe DP, and with some combinatorial mathematics?
•  » » » 6 years ago, # ^ |   0 i know a n*k solution using dp but that will time out .
 » 6 years ago, # |   +15 I still can't view other's codes yet...
 » 6 years ago, # |   +10 How to solve Div1 C?
•  » » 6 years ago, # ^ | ← Rev. 4 →   +14 Above formula works when k > 0. When k = 0, then simply output s
•  » » » 6 years ago, # ^ |   0 please explain how u arrived at this formula .. thnx
•  » » » 6 years ago, # ^ |   0 I'd appreciate a brief explanation.
•  » » 6 years ago, # ^ |   +15 Consider some digit d and all summands, where this digit is the i-th least significant. It will add 10id to the answer for every way to choose the +s that makes that digit the i-th least significant in some summand. That means there are no +s on the next i positions (between two digits) and there is one (or the end of the string, which gives 2 cases) on the i + 1-st position. There are no other restrictions, so we just need to put K - 1 +s on N - 2 - i positions or K on N - 1 - i positions; the number of ways to do that is given by binomial coefficients.Another optimisation lies in adding up the same thing for all digits d farther than i from the end of the string at once, by quickly counting how many such digits there are.
•  » » » 6 years ago, # ^ |   0 I was thinking the explanation and then I found that your explanation is much clearer than mine.
 » 6 years ago, # |   0 What's the test 8 for the Div2-C?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 5 ACGTC Answer: 1 ("CCCCC") Maximum possible value for a string is MAXIMUM_NUMBER_OF_ITERATIONS * n * n. For "ACGTC", MAXIMUM_NUMBER_OF_ITERATIONS is 2 for 'C'. So this value is 50.UPD: MAXIMUM_NUMBER_OF_ITERATIONS means maximum frequency.
 » 6 years ago, # |   +7 Why I can't see others code and test cases?!
 » 6 years ago, # |   +11 i need see the tests cases :(, i will not sleep until that happens :(
 » 6 years ago, # |   +5 why are the solutions not visible yet !!! ?? I hope the other contest is over ??
 » 6 years ago, # |   +5 Eagerly waiting for the editorial !!
 » 6 years ago, # |   0 How to solve Div2 C?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Call f[c] the number of letter c in the string. Call maxF is the maximum value of all f[c]. Call count the num of letter c that f[c] = maxF. The answer to this problem is count^n. I found the answer by writing brute-force solution first, then try some input to observe the rule.
•  » » » 6 years ago, # ^ |   0 What is the proof of your solution ?
•  » » » » 6 years ago, # ^ |   0 Let s be the string given in input and t a string which maximizes ρ(s, t). Take one character (let's call it c) from t. By shifting s and t in all possible ways, c is going to be at the same position as s[i] exactly n times (for i = 0, n — 1). So, the character c adds to ρ(s, t) the value n * count[c], where count[c] is the number of appearances of c in s.Then, ρ(s, t) = n * sum(count[c]), for every c in t. In order, to maximize this, you will have to choose c for which count[c] is maximum. Let num be the number of c's for which count[c] is maximum. The answer will be num ^ n, because, for every position in t, you have num characters to choose from.
•  » » » » » 5 years ago, # ^ |   0 Thanks :)
•  » » 6 years ago, # ^ |   +2 k => Amount of letters with bigger frequency in inputn => Lenght of inputsol = k^n % MODMy solution
•  » » 6 years ago, # ^ |   +3 http://codeforces.com/submissions/dc26Observe a particular character. In following cases, I am calculating distance of only 'A'. ABBB, ACCC -> 4 AABB,ACCC-> 8 AAAB,AAAC-> 36 AAAA, ABBB-> 16 Hence you can see, formula is something like L*X1*Y1 where L=length X1=frequency in 1st string, Y1=frequency in last string. So Distance reduces to summation of N*X*Y for each of 4 characters, "A, C, G, T" Now N and X are constant. We have to decide Y to maximize the product. Now Suppose my String was AAAC. Now what string should I choose to maximize the product.Frequency of A is 3, C is 1. So A will be the major contributor, I will get maximum when my other string is AAAA Now if my string is of type AACC, both A & C are contributors. So I can make a string of C's and A's I know the length i.e. 4 in this case. Now for every position , I can select either 'A' or 'C'. So m answer here is 2^4. Similiarly. "AACCTT" I can chose, 'A' 'C' or 'T' for every position. So answer is 3^6.
 » 6 years ago, # |   +5 http://codeforces.com/contest/521/submission/10108767I thought this would TLE, since it first calculates the power and then the remainder (does it?). Could anyone give some insight into this? I'm not sure how Ruby calculates that, but I would imagine it uses big integers.
•  » » 6 years ago, # ^ |   +14 Is this what you want?
•  » » 6 years ago, # ^ |   0 What is the logic behind this solution ??
•  » » 6 years ago, # ^ |   0 Well there are only 4 characters, and the max results has 60k digits, which should be able to fit in the time limit.
 » 6 years ago, # |   0 Is there a way to solve Div1-B without using multiset?
•  » » 6 years ago, # ^ |   +3 You can use priority queues. I'm not sure this is the answer you are looking for :)
•  » » » 6 years ago, # ^ |   0 Div-1 B why is evryone converting m to n ... how is that easier than converting n to m
•  » » » » 6 years ago, # ^ |   0 You mean storing a point (x,y) as (y,x)? Because people needed to sort the points by y and then by x. Reversing them means that you can use the default pair comparator.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 You also can sort all of the cubes and use two iterators for the current upper cube and the corresponding cube it lays on.
 » 6 years ago, # |   0 Can you tell me how to solve div.2 C?
•  » » 6 years ago, # ^ | ← Rev. 4 →   0 He won't tell, but you can see this submission: 10118102
•  » » » 6 years ago, # ^ |   0 Thanks a lot. this " j=(j*z)%M;" Can you tell me why? my English is poor please forgive me
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 That's another technique to find z^n modulo M. You can also use the modular exponential algorithm to find that. PS: no forgiveness if you don't give me upvote :D
•  » » » 6 years ago, # ^ |   0 I knew it .thanks a lot
 » 6 years ago, # |   +8 This is really a nice round. It proves that it was a good idea to challenge a Codeforces Round during class break.:) The problems are really nice,and this is my first time of Rating going up:)BTW,the contest ID of 520 in Chinese has a quite romantic meaning.Best wishes to all of you:)
 » 6 years ago, # | ← Rev. 2 →   0 Is there any editorial for problem Div.1-D?
•  » » 6 years ago, # ^ |   +9 The editorials for all problems are coming. I'm sorry for the delay.
•  » » 6 years ago, # ^ |   +8 Short description: div 1d was greedy. if we use assign op for any skill, then it's optimal to use as first op, so change highest assign op for every skill i to "sum b-a[i]" and discard the rest.Now every mult op multiplies answer by b, sum op multiplies answer by (a[i]+b)/a[i]. Greedily take highest multiplication factor until you can't pick any more operations. Print operations used for a skill in the order "type 1, type 2, type 3".Note that when you use a sum operation in a skill, factors for the other sum operations on the same skill change (mult doesn't affect anything because it's only done in the end). The way I solved this was keeping only the highest sum op for every skill in the priority queue and updating factors when needed.
 » 6 years ago, # |   +1 How to solve Div2-E / Div1-C? I could find just a dp solution which takes N * K. Any helps would be appreciated...
 » 6 years ago, # | ← Rev. 2 →   0 Why doesn't my solution of Div1 B work? Isn't the answer a modification of Kahn's algorithm? And what's pretest 4 about?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 The solution is not a "greedy" topological sort of the graph. You can also remove nodes that have non-zero in-degree but after their removal, the connected component they are part of must remain connected. So you should greedily remove nodes that don't affect "connectedness".
•  » » 6 years ago, # ^ |   +14 first person can take 0, 1, 2, 6, 9 he will choose 9second person can take 0, 1, 2 he will choose 0first person can take 1, 2, 4 he will choose 4second person can take 1, 2 he will choose 1first person can take 2, 6 he will choose 6second person can take 2, 3 he will choose 2first person can take 3, 7 he will choose 7second person can take 3, 8 he will choose 3first person can take 5, 8 he will choose 8second person take the remaining 5so the result will be 9041627385 % 1000000009 = 41627304
 » 6 years ago, # |   0 Can someone please explain the logic of Problem C(DIV 2) ?
•  » » 6 years ago, # ^ |   0 explained already!! http://codeforces.com/blog/entry/16707#comment-215954
 » 6 years ago, # |   0 520B - Two Buttons I know that turning m into n is easier than the opposite, but why is this code wrong? Can you give me any simple counterexample? while(n != m){ if(n > m) n--; else{ if(m % 2 == 0){ m /= 2; } else{ if((n-1)*2 >= m) n--; else n *= 2; } } sol++; } 
•  » » 6 years ago, # ^ |   0 Try n=3, m=7.That code goes 3 -> 6 -> 5 -> 4 -> 8 -> 7, when in fact it is better to go 3 -> 2 -> 4 -> 8 -> 7.
•  » » 6 years ago, # ^ |   +15 I thought Problem B and D are very similar, so I don't understand your claim.
•  » » » 6 years ago, # ^ |   -14 Did you participate parallely in Div2 contest? Then Div2D and Div1B are undoubtedly similar :).In what sense they are very similar? Their contents were surely very different and for me "problems X and Y are similar" means "statements of X and Y were similar/they followed one idea/similar techniques were used" and all of those options are clearly absurd.
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   +23 It's true that problem B is an implementation problem, but it was interesting and I failed 3 pretests as I didn't think cases that if one box is removed, then some 'free to be deleted' boxes are no more free. If pretests were a little weaker, then the problem could a decent reservoir for hacks.In my view problem D was quite similar, in the sense of solving technique, as the greedy condition for each item was more evident for me than problem B. I resubmitted only because I didn't keep 'assign -> add -> mult' order. With 'long long' requirement, there were several traps, and I can understand acceptance rate was very low, but this is not because this problem was superbly interesting.In the both problems the main idea was 'use priority queue to decrease time complexity from O(n) to O(log n)' and the data structure to do this was very similar. So while I could be misleading about saying the problem statements were similar, not that much about the solving techniques.Anyway, I enjoyed all A-D problems, and didn't have any clue about problem E. (I'm very weak to graph problems, so...)
•  » » 6 years ago, # ^ |   +10 It should have been mentioned that Vasya and Petya are cosmonauts working on this experiment in zero-gravity conditions.
•  » » 6 years ago, # ^ |   0 Ok man, at least you didn't walk up to the computer screen at 2 AM in the morning, and see that all problems but E are math. Man you have no idea how I felt after that -__-, and you're complaining about 1 problem.There needs to be more diversity in CF rounds, you can't just make 4/5 problems math, or dp, or whatever. It's just not interesting when you do that.
•  » » » 6 years ago, # ^ |   +41 Lol, you will have hard time in competitive programming if you call such problems "math" ; d
•  » » » » 6 years ago, # ^ |   -13 You can't argue with tags man. Shop math, sortings Pluses everywhere combinatorics, dp, math, number theory DNA Alignment math, strings Now if we do a simple string search on "math" we can see it in all three of these problems.
•  » » » » » 6 years ago, # ^ | ← Rev. 2 →   0 In that sense absolutely everything here is math, go ahead and whine everytime when you see a "+" or "product" in a statement since that immediately indicates that this is a math problem --> shit problem.
•  » » » » » » 6 years ago, # ^ | ← Rev. 2 →   -21 I'll go ahead and do that, thx. BTW I should say I was joking about the tags (and this) ^_^
•  » » » » » 6 years ago, # ^ |   +10 You can't argue with tags man.And what if I tell you that everyone who solved a problem can edit tags? :) So you can solve/copy-paste solutions for whole div1 problemset and then easily make it 5/5 math (according to tags).In some sense all programming is math.And problems which you mentioned aren't math in bad sense of this word. I am glad that there are not a lot such problems at CF at all.P.S. Have you ever tried Project Euler? Or Ad Infinitum contests at HackerRank?
•  » » 6 years ago, # ^ |   0 You know, when I was solving this problemset — I was actually happy that problem B was 2D instead of 3D)
•  » » » 6 years ago, # ^ |   0 Of course I was happy also, but fact that I learnt that after few minutes is not nice :P.
•  » » 6 years ago, # ^ |   +79 Well. I feel like I should reply something.Regarding problem B, I don't feel like this problem stands out from the problemset in a bad way. It probably didn't feature wonderful insights, but I like this problem too; if I would have created this problem, I wouldn't hesitate to include it in some of my rounds.The statement might not be in the best shape, I must agree. However, this is quite certainly not savinov's fault. The point is that the problems were prepared collectively, with me being the lead of the process. We decided to change the problem B in the last moment due to unforeseen circumstances (basically, it turned out that the former problem B was featured in some contest earlier), and savinov kindly provided his problem. It might have had some issues, but then again, every problem has issues until it is triple-checked by different people. So, plainly, it's my fault that the problem didn't get the attention it deserved.
 » 6 years ago, # |   0 I can't understand the solution of DIV 2 C. I spent a lot of time thinking of it and I can't understand why we care only for characters which occur most frequently. Having string s = "GAAAGGCCCCCCGGG" we count occurences of each letter : A -> 3 G -> 6 C -> 6 so the answer will be 2^15, becase 15 is the length of word and G i C appear the most frequentlyso for example we count strings like GTTTGGCCCCCCGGG , because here also G i C appears 6 times , but p(s,t) = 1080 which isn't maximum. I believe that maximum is where t is for example GAAAGGCCCCCCGGG or GACAGGCCCACCGGG so A also has contribution to result.Here is my code calculating these values http://ideone.com/ZedQOQI'd be grateful for help
•  » » 6 years ago, # ^ |   0 The strings you provided don't attain the maximum value. Have you tried computing the value p(s, "GGGGGGGGGGGGGGG")?
•  » » » 6 years ago, # ^ |   0 Thank you. The result for GGGGGGGGGGGGGGG is better ( 1350)
 » 6 years ago, # |   0 Div_2 B seems at first sight to me very hard to get algorithm but it has a very easy & interesting solution by division and adding :)
 » 6 years ago, # |   0 very sexy contest!!! :D :D :D
 » 6 years ago, # |   +5 waiting for new contest !!... I want to became CM
 » 7 months ago, # |   0 Holy shit!!! There is eight Grandmaster and one International Grandmaster...