### drazil's blog

By drazil, 8 years ago,

Hello, everyone! Codeforces Round #272 will be held at this local time. We're looking forward to your participation!

The problems are from dreamoon_love_AA and drazil(that's me) from Taiwan, and thanks 9mmlitswe for some discussion. Also we want to thank Zlobober and Gerald for helping us prepare the round, Delinur for translating the statement into Russian, and MikeMirzayanov for Codeforces and Polygon.

This is our first round on Codeforces, we hope you'll find it interesting! Please read all problem statements and discover what the main character dreamoon_love_AA do in those problems for he's really cute =)

Update1 Note this round will be held 1.5hrs earlier than usual Codeforces rounds, so please double check the starting time in your local time.

Update2 Score distribution!
Div2: 500-1500-1500-2000-2500
Div1: 500-1000-1500-2000-3000

Update3 The contests are over. Congratulations to the winners!

Div1:
1. Petr
2. qwer1561
3. kutengine
4. ifsmirnov
5. TankEngineer

Div2:
1. ridowan007
2. a00012025
3. xavier13540
4. v_Enhance
5. pkq2006

And standings are here:
Div1: standings
Div2: standings

Update4 Editorial can be found here. It's finished by now but it's welcome to tell me if anything can be improved!

• +253

 » 8 years ago, # | ← Rev. 2 →   -48 After the rather lengthy round announcements of Round 271, Bayan Contest, Round 270, and Round 269, the age of short announcements are back. And what has dreamoon_love_AA been doing the past few contests? Trying to be another worse ?
•  » » 8 years ago, # ^ |   +42 Actually, worse began the journey to red
•  » » 8 years ago, # ^ |   +40 I heard dreamoon_love_AA said that he has some plans about it =)
•  » » » 8 years ago, # ^ |   -18 Just Petr can paint his rating curve according to his wishes, noone else should try to do so.
•  » » » » 8 years ago, # ^ |   +14
•  » » 8 years ago, # ^ |   0 Please, don't neglect any Coder. Every coder has a high ambition to become RED. And mind the Quote Failure is the pillar of success
 » 8 years ago, # |   +80 Did Zlobober became a long-term problem tester as Gerald? Fact that he is no longer visible in contribution standings (as MikeMirzayanov :P) seems to confirm this.
 » 8 years ago, # | ← Rev. 2 →   +23 I think you should write a warning about the unusual time of the roundSome people may miss the round if they didn't notice that.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +8 This round will be held at CST-1:30 (1.5 hours before Codeforces Standard Time)
•  » » » 8 years ago, # ^ |   +34 Let's hope for math :)!
•  » » » » 8 years ago, # ^ |   +1 yep he always hope for math for me I always hope for early score distribution announcement :D
 » 8 years ago, # |   +18 I expect it will be a very Nice contest and contains various problem set dreamoon_love_AA rank at UVA is 7 solved about 3205 problem this is his profile http://uhunt.felix-halim.net/id/2397 I don't know other Online judges but being rank 7 on UVA is sufficient to see cool & various problem set
•  » » 8 years ago, # ^ |   +19 Doesn't being an international grandmaster (like dreamoon_love_AA was before his fall (partially on purpose)) is a sufficient proof :P?
•  » » » 8 years ago, # ^ |   +46 sometimes Theorem has more than one proof :P :D
•  » » 8 years ago, # ^ | ← Rev. 2 →   +7 dreamoon_love_AA also solve around 1432 problems here in codeforces ( as like you i don't know others OJ number but i am pretty much sure there must be more than thousands also ) . i always wonder is problem solving is that kind of addiction to him if he won't solve 10 or more problems in a day he can't eat or sleep :D
•  » » 8 years ago, # ^ |   +6 I wonder how many problem he solved in one day. Did he sleep at night or goes to school? I was trying to see his first solved problem in uva. But now it is still loading for few minutes.
•  » » » 8 years ago, # ^ |   0 I don't think he'd go to school at night :DA year has 365 days. His profile shows 8 years of solving. That means about a problem a day (very roughly), probably often several easy ones a day. Do you think sleep matters at all in this case? :D
•  » » » » 8 years ago, # ^ |   0 Of course you are right. He is solving till 2006. At 2014 he solved about 8-15 problem some day. Of course it is easy for him after a lot of solving.
 » 8 years ago, # |   +21 Damn. Bayan Qualification + Marathon24 + NEERC + Codeforces Round #272.Because screw weekends
•  » » 8 years ago, # ^ |   +9 You count Bayan Qualification along with those other contests? >_>I'd replace it with Codechef Long Challenge, it has more decent problems now.
 » 8 years ago, # |   +12 3000 point E problem come back! Do you guys want to make a super hard problem that is even harder than Chinese IOIer's round?
•  » » 8 years ago, # ^ |   0 I was about to say the same :). Maybe I should read E in the beginning and in case I got this coded already, paste my solution, otherwise not give it any thought :P.
 » 8 years ago, # |   +11 what a nice contest time :)
 » 8 years ago, # |   0 In the div2,the second problem is 1500,I dont't think it's easy.
•  » » 8 years ago, # ^ |   0 the third problem also 1500 , what do you think ?
•  » » » 8 years ago, # ^ |   0 I don't think it's easy,too,uha.
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 I agree with 12310720112 -_-
•  » » » 8 years ago, # ^ |   0 Thank you for agreeing with me,haha~
 » 8 years ago, # |   +12 I think a newly registered guy will be on top of Div.2 contest.
•  » » 8 years ago, # ^ | ← Rev. 2 →   +14 I think no because newly registered guy has a Div1 contest at this time :D
•  » » » 8 years ago, # ^ |   0 Petr will win Div1.
•  » » » » 8 years ago, # ^ |   0 Well, you called it O.o
 » 8 years ago, # |   +26 Found out that I don't have a pen at home 10 minutes before the contest. Going to use Paint instead of pen!
 » 8 years ago, # |   0 Oh I forgot registering contest.. :<
 » 8 years ago, # | ← Rev. 2 →   +44 Goodbye red color :(
•  » » 8 years ago, # ^ | ← Rev. 2 →   +18 Goodbye blue color :(
•  » » » 8 years ago, # ^ |   +5 Goodbye green color :(
•  » » » » 8 years ago, # ^ |   0 Welcome Blue color:)
•  » » » » » 8 years ago, # ^ |   0 Goodbye purple.Next time I'm going right to yellow! (not really)
•  » » 8 years ago, # ^ | ← Rev. 2 →   +15 Goodbye green color :(
•  » » 8 years ago, # ^ |   +16 Goodbye yellow color :((
•  » » 8 years ago, # ^ |   +11 Sayonara purple!
•  » » » 8 years ago, # ^ |   +6 But not today!
•  » » 8 years ago, # ^ | ← Rev. 3 →   +7 Goodbye Orange, hello Red :D
•  » » 8 years ago, # ^ |   0 Goodbye Div.1 :(
 » 8 years ago, # |   +5 Who else failed A because of long overflow
•  » » 8 years ago, # ^ |   +62 Are you happy with math problems?
•  » » » 8 years ago, # ^ |   0 C was good non maths problem >:D
•  » » » 8 years ago, # ^ |   0 Yes I am happy (yay I got B) but failed A
•  » » » 8 years ago, # ^ |   0 I don't understand why this naive code fail for pretest 5. codeI was using that for find my mistake, but I couldn't
•  » » » » 8 years ago, # ^ |   +13 Because (i%b) should be a divisor of (i/b).
•  » » 8 years ago, # ^ | ← Rev. 3 →   +22 I thought: "Problem with MOD! I'll do some hacks today!" and instalock it. After few minutes I figured out that my solution is wrong because I forgot to add some MOD...
•  » » 8 years ago, # ^ |   0 Exactly though i didn't give the contest because I actually woke after 30 mins past the start time but definiately this is the first problem I have seen of long overflow.really tricky on this part.
 » 8 years ago, # |   +6 how to solve B -div1 ??
•  » » 8 years ago, # ^ | ← Rev. 2 →   +16 Output ((6i + 1)k, (6i + 2)k, (6i + 3)k, (6i + 5)k) for all i = 0, 1, ..., n - 1. (And thus the maximum is (6n - 1)k.)
•  » » » 8 years ago, # ^ |   0 missed it completely ...thnx
•  » » » 8 years ago, # ^ |   0 Why 6i ???
•  » » » 8 years ago, # ^ |   0 why this 6*i+1 format ?? I mean a simple proof ?
•  » » » » 8 years ago, # ^ |   0 See hereBasically you need three odd numbers for each set, and there are 3 odd numbers every 6 numbers.
•  » » » » 8 years ago, # ^ |   +29 First, divide everything by k, so now we want all numbers in each set to have pairwise GCD 1.Note that we can only have one even number; if we have two even numbers, their GCD is even and thus not 1. So we need three odd numbers.As it turns out, 6i + 1, 6i + 2, 6i + 3, 6i + 5 has pairwise GCD 1 for any integer i, so we might as well use it. By using all lowest values of i (namely i = 0, 1, 2, ..., n - 1), we have maximum m = 6(n - 1) + 5 = 6n - 1. Also note that since we need three odd numbers per set, we need 3n odd numbers, and if m < 6n - 1 then we don't have enough odd numbers to use. Thus m = 6n - 1.Remember that we have divided everything by k to make the pairwise GCD 1 instead of k, so now just multiply everything by k again.
•  » » » » » 8 years ago, # ^ |   +3 why 6 !!!why not any other even number 4, 8, 2, anything :3 ?
•  » » » » » » 8 years ago, # ^ |   +4 You need three odd numbers (one can be even), and this happens every 6.
•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   +11 I wrote for each set 6i+1,6i+3,6i+5 and first even number, which is coprime with each of these 3 numbers. And each time I was choosing an odd number bigger than previous one. I've checked that the even number in each set is less than all other odd numbers. And also multiplied each number to k and m=(6n-1)k. But this solustion didn't pass. Do you know my misstake? Could you show me some test for this, in which this solution is wrong?
•  » » » » » » 8 years ago, # ^ |   +1 You read in n as k and k as n.n comes before k in the input.
•  » » » » » » » 8 years ago, # ^ |   +11 OMG I've just found it)) that is impossible misstake)) I can't believe it =D tnx
•  » » » » » » » 8 years ago, # ^ |   +12 and it passed after changing n and k
 » 8 years ago, # | ← Rev. 2 →   +13 92anurag was the first to ask.
•  » » 8 years ago, # ^ |   +23 Uhm, the solution is in the sample. Just use 6i + 1, 6i + 2, 6i + 3, 6i + 5 (assuming k == 1). Upper bound is easily obtained from the observation that at least 3 numbers in each set should be odd.
•  » » » 8 years ago, # ^ |   0 thnx ..got it
•  » » » 8 years ago, # ^ |   0 Nice idea, I haven't noticed this pattern in the sample. :(
•  » » » 8 years ago, # ^ |   +17 What kind of sorcery is this?
•  » » » » 8 years ago, # ^ |   +5 math man, math!
 » 8 years ago, # |   0 why wa on pretest 5 of question C. http://codeforces.com/contest/476/submission/8207485
 » 8 years ago, # |   0 Explanation for problem C Div2?
•  » » 8 years ago, # ^ |   0 for (mod = 1; mod < b; mod++) res += mod * b * a(a+1)/2 + mod * a 
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 How are you sure that an O(b) solution with multiplication,division and mod solution will pass under 1 second? Same question to O(a) solutions also
•  » » » » 8 years ago, # ^ |   0 10^7 * k operations (where k < 50) should mostly pass.
•  » » » 8 years ago, # ^ |   0 I did the same. Can you tell me why 8200906 is hacked?
•  » » » » 8 years ago, # ^ |   0 You casted to double, losing precision. (Double can only hold about 53 bits of precision; with a = 109, that you're computing needs 59 bits.)
•  » » » » » 8 years ago, # ^ |   0 Thank you! And also, how do you calculate how much precision it needs?
•  » » » » » » 8 years ago, # ^ |   +3 Oops, I have successfully confused myself. a = 107, not 109.No, the problem is below that: sum*i*b essentially explodes. With a = b = 107, i = 107 - 1, we have , thus you're computing . This requires 94 bits; long long only has 63 bits.Computing precision is simple; take the number, take its logarithm base 2, and round up. That's the number of bits you need.
•  » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 I actually tried sum*((a*b)%MOD) I doesn't work either.
•  » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   +3 You want sum*i*b not to give overflow. Thus: You should have taken the modulo of sum earlier. Insert sum %= MOD; before the line, or perhaps after computing sum with that casting to double. You should have taken the modulo of the first multiplication before doing the second. Replace sum*i by ((sum*i)%mod). The good thing is that delaying the modulo to the end of the line is still okay, although you should try making a habit of taking modulo after every arithmetic operation if overflow is a problem.
•  » » » » » » » » » 8 years ago, # ^ |   0 Yeah, it worked! Thank you really much. I appreciate your effort.
•  » » » » 8 years ago, # ^ |   +3 ll sum = (double)(1+a) / 2 * a; (ll) expected, but (double) found
•  » » » » » 8 years ago, # ^ |   0 Shouldn't it be double because something divided by 2 might something.5?
•  » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 use (ll)(a+1)*a/2 insteadBecause there is exactly one even number in a+1 and a.
•  » » » » » » » 8 years ago, # ^ |   0 There should be another mistake somewhere else because it still doesn't pass. 8208763
•  » » » » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 res = (res + ((sum*((i*b)%MOD))%MOD) + ((a*i)%MOD)) % MOD; sum is too large. res = (res + (((sum%MOD)*((i*b)%MOD))%MOD) + ((a*i)%MOD)) % MOD; 
•  » » 8 years ago, # ^ |   +26 Observe that all numbers satisfying the condition has the form x = (bk + 1)(mod(x, b)). Since mod(x, b) can be any integer between 1 and b - 1 inclusive, k can be any integer between 1 and a inclusive, and all those numbers are valid, you're adding up (b + 1)(1) + (b + 1)(2) + ... + (b + 1)(b - 1) + (2b + 1)(1) + (2b + 1)(2) + ... + (2b + 1)(b - 1) + ... + (ab + 1)(b - 1).We group every b - 1 terms; these are all in the form for some x. Thus our sum becomes , which can be simplified to .There you go, an O(1) solution. I wonder why the time limit is 1.5 seconds...
•  » » » 8 years ago, # ^ |   0 Time limit is 0.00001 seconds ?
•  » » » 8 years ago, # ^ |   0 hey thanks for the solution.. Can O(b) or O(a) solutions which are given here pass under 1.5 seconds? Also, How do i check what is the expected complexity according to constraints in such problems
•  » » » » 8 years ago, # ^ |   0 Yes, both O(b) and O(a) will pass. Can you rephrase the second question as I did not understand it.
•  » » » 8 years ago, # ^ |   0 I did the same. But why i got WA? http://codeforces.com/contest/476/submission/8205508
•  » » » » 8 years ago, # ^ |   +1 Check your mod and division by 2. http://codeforces.com/contest/476/submission/8210369
•  » » » » » 8 years ago, # ^ | ← Rev. 5 →   0 Nevermind.
•  » » » » » » 8 years ago, # ^ |   +1 Change a and b type to long long and it will pass =) You simply overflow in (b*(b-1)/2). http://codeforces.ru/contest/476/submission/8211783
•  » » » » » » » 8 years ago, # ^ |   0 Yes I noticed after :D Thank you !
•  » » » » » 8 years ago, # ^ |   0 Thank you.
•  » » » 8 years ago, # ^ |   0 (a + (a*b*(a+1)/2))*(b*(b-1)/2)Prob C — Div 2 By using above formula why i am getting WA http://codeforces.com/contest/476/my#Can you check my solution I used ur formula but getting WA
•  » » » 8 years ago, # ^ |   0 Are there any mathematics calculations which way you thought that all numbers satisfying the condition has the form x = (bk + 1)(mod(x, b)) ? Does it mean that you get this formula with transform this: k=(x/b)/(mod(x,b) or you just get it by logical analysis ?I know that 'X' has form (bk + 1)(mod(x, b)) but I doesn't get it by algebraic manipulations. Could I get it from this formula: k=(x/b)/(mod(x,b) ? ( Excuse me for this stupid question but i really don't understand why you add 1 there: (bk **+ 1**)(mod(x, b)) ) certainly if you get this by algebraic manipulations. )
•  » » » » 8 years ago, # ^ |   +1 Note that x = b·div(x, b) + mod(x, b). (This is more or less by definition; div(x, b) is x / b rounded down, thus when multiplied by b gives the largest multiple of b not exceeding x, and mod(x, b) is the missing amount to bring the multiple of b up to x.)The rest is just plugging in what's given in the problem and manipulating a bit.
•  » » » » » 8 years ago, # ^ |   0 Thank you ! It's really help me.
•  » » 8 years ago, # ^ |   +3 x = q*b+r ---(1) and q/r = k or q = rk; put this in 1 x = brk+r = r(bk+1) Now we see that , r can be 1 to b-1. thus for a particular value of k, we have 1(bk+1) + 2(bk+1) +3(bk+1)... (b-1)(bk+1) =(bk+1)(1+2+..b-1) so , psudocode is below sum = 0; for(k=1;k<=a;++k) { sum+=b*(b-1)/2 * (bk+1) } don't forget to mod every expression.
 » 8 years ago, # |   +4 I spend more time for problem C div 2, I am bad
•  » » 8 years ago, # ^ |   0 Yeah i did that too. i was just getting confused with all those numbers . (defined by problem and me !)
 » 8 years ago, # | ← Rev. 2 →   +1 tfw understood how to solve C at 30 sec before contest finish
 » 8 years ago, # |   +35 Very interesting problems! Thanks to authors!
 » 8 years ago, # |   0 How to solve Problem C Div 2 / problem A Div 1 ? i am trying to calculated with arithmetic sum formula Sn = (n/2) * ( 2*a + ( n - 1 ) * d ) , where n is the limit of the sequence . here is my code WA at test case 5 . can anyone please explain what is going wrong here .
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 удален.
 » 8 years ago, # |   0 This is my submission on A Div.1: 8203037What is wrong with my expression?
•  » » 8 years ago, # ^ |   -14 Because your algorithm is wrong !!!!!
•  » » » 8 years ago, # ^ |   0 Thank you, captain obvious :vBtw I'm asking what's wrong, not why it's wrong :v
•  » » » » 8 years ago, # ^ |   +1 I don't understand your questions
•  » » » » 8 years ago, # ^ |   +6 ok what? your algorithm
•  » » 8 years ago, # ^ |   0 I think you misinterpreted the problem or something, thinking that you're only counting numbers between 1 and a or something, not counting numbers whose k is between 1 and a.
 » 8 years ago, # | ← Rev. 2 →   0 solution of div2-E / div1-C someone please?
•  » » 8 years ago, # ^ |   0 DP with state pos, no_char_to_delete, where pos is the position of S.First pre-calculate next[i] for each i, where you can find P in S[i,next[i]], deleting zero or more character.Then using this info, you can run the dp.
•  » » » 8 years ago, # ^ |   0 Isn't this O(pn^2), too slow?
•  » » » » 8 years ago, # ^ |   0 I implemented a DP with those states using some precomputing and making it in total O(pn log n). I suppose the simplest O(pn^2) approach should TL.
•  » » » » » 8 years ago, # ^ |   0 I got that, but the number of useful states isn't Theta(pn^2)? If that's not the case, may you only hint which kind of states are useless?
•  » » » » » » 8 years ago, # ^ |   +8 there is precalculation of |S|*|S|then the dp too is |S|*|S|
•  » » » » » » 8 years ago, # ^ |   0 Your DP is F[i][j] — maximum amount of patterns that can be formed if you use characters 1~i and remove exactly j letters. O(pn) states.
•  » » » » 8 years ago, # ^ |   0 But its only O(n^2).
 » 8 years ago, # |   0 I tryed to use long double (16 bytes in my gcc) and printf("%Ld",v) for "B" problem but not lucky at 1st test. double and "%f" passed 1st test, and "%.9f" passed all tests... I don't understand why "%Ld" not passed 1st test, where is my error?
•  » » 8 years ago, # ^ |   0 long double,you should use cout<< to output....Ld is not using to output long double
•  » » 8 years ago, # ^ | ← Rev. 3 →   0 BTW,if you run this code in CF. #include int main() { printf("%d",sizeof(long double)); } you will find sizeof(long double) is 12 in CF...
•  » » » 8 years ago, # ^ |   0 who can tell me where is my "#"? and why the string is bigger than others?
• »
»
»
»
8 years ago, # ^ |
+21

# produces a level 1 heading.

# Heading level 1 (# in front)

## Heading level 2 (## in front)

### Heading level 3 (### in front)

Use ~~~~~ to delimit your code, putting it above and below the code.

•  » » » » » 8 years ago, # ^ | ← Rev. 2 →   0 #include int main() { printf("test....it's ok?\n"); } 
•  » » » » » 8 years ago, # ^ |   0 THX~~
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 thanks for your answer.I'll use cin/cout in future. but. I think printf("%f",(double)ld); is not bad.
 » 8 years ago, # |   +26 C Fail system test on 26.... Yellow, here I come back!
 » 8 years ago, # |   0 Can anyone explain pretest 5 (input: 4 3) in problem C(div.2)?Which numbers should be added?
•  » » 8 years ago, # ^ |   0 a = 4, b = 3Try for k = 1. We want div(x, 3) = mod(x, 3). Since mod(x, 3) = 1, 2, we thus have two numbers: one with div(x, 3) = mod(x, 3) = 1, and one with div(x, 3) = mod(x, 3) = 2. The numbers satisfying this are 4 and 8 respectively.Try for k = 2. We want div(x, 3) = 2·mod(x, 3). Since mod(x, 3) = 1, 2, we thus have two numbers: one with div(x, 3) = 2, mod(x, 3) = 1, and one with div(x, 3) = 4, mod(x, 3) = 2. The numbers satisfying this are 7 and 14 respectively.Trying for k = 3 gives 10, 20, and for k = 4 gives 13, 26.Adding them all gives the requested 4 + 8 + 7 + 14 + 10 + 20 + 13 + 26 = 102.
•  » » 8 years ago, # ^ |   0 Just write a brute force ....the numbers are : 4 7 8 10 13 14 20 26 sum = 102
 » 8 years ago, # |   0 Hello !what's wrong with my code?! for div 2 C http://codeforces.ru/contest/476/submission/8197243
•  » » 8 years ago, # ^ | ← Rev. 2 →   +8 ((b % mod) * (sum2 % mod) * (sum1 % mod))If b % mod, sum2 % mod, sum1 % mod are together pretty large (about 109 each), they make the resulting number to get overflow (about 1027).
•  » » 8 years ago, # ^ |   0 Try to mod every value RIGHT AFTER multiply. Don't multiply three values in a time, it will be overflow.
 » 8 years ago, # |   0 Hi!I got a TLE on D, but I found out that my program ran exactly 2000ms on some case but the system gave me a TLE :(Here's the submission link: http://codeforces.com/contest/477/submission/8206241
 » 8 years ago, # |   +10 Changed const int N = 2e3 + 2; to const int N = 2e3 + 3; and my C passed ;__;. I'm such a loser ;_;.
 » 8 years ago, # |   0 How to solve div1-C?
•  » » 8 years ago, # ^ |   0 First you need to calculate nearest subsequence that match P and start from i for every i
•  » » 8 years ago, # ^ |   0 First, let's calculate for each position i in string s value L[i] — minimum length of substring which ends in i and it is possible to get string p by removing some characters from it. It can be easy calculated using dynamic programming.Next, let's find dp[i][cut] — answer for prefix of s which ends in i and with cut character removes done. It can be calculated next way: dp[i][cut] = dp[i-1][cut]; if (cut > 0) dp[i][cut] = max(dp[i][cut], dp[i-1][cut-1]); for (int k = L[i]; k <= cut + p.length(); ++k) dp[i][cut] = max(dp[i][cut], dp[i - k][cut - k + p.length()] + 1); This solution gives us O(|s|3) complexity. But you can notice that in every dp visited in the cycle difference between i - k and cut - k + p.length() is fixed: it is equal to i - cut - p.length(). So, you just need to use fenwick trees where in ftr[i + cut][i] you will update the answer.Then the cycle will look like this: dp[i][cut] = max(dp[i][cut], get(ftr[i - cut - p.length()], i - k) + 1); where get(a, b) function returning maximum on fenwick tree a prefix with length equal to b.Of course, you can examine my solution: 8203748
 » 8 years ago, # |   0 I read all the problems first time incorrectly. I figured first one after first wrong submission, figure second after frustrated by C which I made it too complex.Btw problem was very good, lot to think less to code.
 » 8 years ago, # |   -25 Last contest Bayan Warmup, my rank was 150, and top 50 won T-shirt.This contest, my rank was 46, but top 50 didn't win T-shirt.Why aren't there any T-shirt for each contest???
•  » » 8 years ago, # ^ |   +18 Indeed, Codeforces should start giving T-shirts more often. I need Codeforces and Facebook T-shirts to complete my collection.
•  » » » 8 years ago, # ^ |   +23 /\
•  » » 8 years ago, # ^ |   +19 Then some people would get too many t-shirts :D
 » 8 years ago, # |   +17 Today my contest is not so good at all, but feeling proud to see the participant ridowan007 of our country(Bangladesh) got rank 1 in Div-2. Really nice performance !!
•  » » 8 years ago, # ^ |   0 Thanks for the nice comment :)
•  » » » 8 years ago, # ^ |   0 Welcome vai :)
 » 8 years ago, # | ← Rev. 2 →   +28 Thank drazil for this interesting contest!
 » 8 years ago, # |   +13 My submission for Div1-C got TLE, even though first inspection shows its complexity is O(|s|2 + |s||p|). Besides "use a faster language other than Python", is there anything in my code that can be improved? My algorithm is to first find all "sufficiently close" subsequences of s that is equal to p (this is constructing the array found), by iterating over each character of s and p, taking note when the latest starting position of a subsequence of s ending with the character in p. Note that since any ending character is used only once, there are only |s| elements at most. Next, I used a DP with states of the form (latest found element considered, number of subsequences) (this is constructing the array dp).At the end of this, I have an array of how many characters at least must be deleted to give a given number of subsequences (this is constructing the array dpres), which is easily converted to give the maximum number of subsequences possible by deleting a given number of characters (this is the first state of res; the second state just takes the minimum of the first state and the theoretical maximum number of subsequences with only having a certain number of characters).
 » 8 years ago, # |   +61
•  » » 8 years ago, # ^ |   +5 what's wrong?
 » 8 years ago, # |   0 Can anybody give me hind how to solve prob-B div-2 My submission: http://codeforces.com/contest/476/my#getting WA :(
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Try to implement iterating over subset with bitmasking.If there are m question marks,you have m^n options.Then something like for(int i=0;i<(1< 0) questpos++; else questpos--; } if(questpos==pos) ways++; // here pos means position of a , if it is equal to questpos , then we increase number of ways } Then your answer will be ways/(double)(1<
 » 8 years ago, # |   +5 Thanks for all the interesting problems.I liked Div 2 C and B very much.I didn't come up with solution for A.Interesting and nice problem set.
 » 8 years ago, # | ← Rev. 2 →   0 In problem C div 1 (E div 2) occ(s',p)` was a set of substrings. What does "substring" mean?
•  » » 8 years ago, # ^ |   +1 A substring of another string S is a string of consecutive characters of S; in other words, it is formed from S by deleting some (including all and no) characters from the front and the back, but without deleting any character in-between the chosen characters. If S = abcd, then bc, ab, b, a, abcd, ε are substrings of S (ε is the empty string), but bd, abd, cb aren't.
•  » » » 8 years ago, # ^ |   0 Thank you, sometimes it is not clear for me, is substring like subsequence — where you can delete some character in-between.
 » 8 years ago, # |   +3 I think there should be one more line in problem C Div.1. div(x,b)%mod(x,b)=0. This causes problem in understanding problem statement for a lot of participants.
•  » » 8 years ago, # ^ |   +1 You mean C Div 2?Normally if division is written using mathematical typeset it is to be interpreted as real division. Besides, if the intention is floored division, it should have been div(div(x, b), mod(x, b)) = k instead, as the problem already defined div. And of course you can always ask the problem setter using the question asking feature.
•  » » 8 years ago, # ^ |   0 No. It was stressed that their quotient must be an integer (e.g. not real), which is sufficient.
 » 8 years ago, # |   0 I didn't understand prob C. Could someone please explain me this problem
 » 8 years ago, # |   0 (a + (a*b*(a+1)/2))*(b*(b-1)/2)Prob C — Div 2 By using above formula why i am getting WA http://codeforces.com/contest/476/my#
•  » » 8 years ago, # ^ |   +6 long long? Btw — look at the link you've attached. There is "my#" in the end. Is this what you wanted to link :)?
 » 8 years ago, # | ← Rev. 2 →   +20 Is there a bug with the rating? It looks weird ._.
•  » » 8 years ago, # ^ |   +16 :D
•  » » » 8 years ago, # ^ |   +6 didn't reach red, thats bad :D
 » 8 years ago, # | ← Rev. 2 →   0 I apologize for a re-post but i can't understand why this summation works for Div1-A/Div2-C ![ ]()
•  » » 8 years ago, # ^ |   0 seeking answer to same question....Why this summation works/how one has come up to this summation??
•  » » 8 years ago, # ^ |   0 and . So expanding that summation will give the exact formula as the one in editorial.
 » 8 years ago, # |   0 hm...please tell me where is my mistake in div2b? (wrong test 11 after all formatting)
•  » » 8 years ago, # ^ |   0 abs() (((((((((((((
 » 8 years ago, # |   0 Div I problem E: an almost same but stronger version of this problem:http://codeforces.com/gym/100162/problem/I
•  » » 8 years ago, # ^ |   0 This problem can be solved with O(m n log n) with simpler idea and implementation in comparision with Div.1 E.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 en,yes,but there is one issue to write this kind problem to contest,if someone has solved the weak version with (n+m)*log(n) approach, he or she can copy previous code and submit in contest,and (I say just in theory) some red coder has opportunity to copy others code in the contest
•  » » » » 8 years ago, # ^ | ← Rev. 2 →   0 In fact, there is a more similar problem on regular Codeforces round: Codeforces Round #154 (Div. 2) pC I have considered the case you mentioned. But I think the implementation of this solution is complicated and boring so nobody would implement it before CF272. I cannot deny the risk of providing this problem as pE.
•  » » » » 8 years ago, # ^ |   0 And you always cannot expect a problem nobody solved it before. In fact, I think I can arrive high rating at Coeforces or Topcoder just because there are many contest problems I had written in past.
•  » » » » » 8 years ago, # ^ |   0 er... I think you misunderstood what I mean"write problem to contest", I'm not meaning solve problem ,I mean set task for others to solve. I haven't seen you as problem writers for many times
•  » » » » » » 8 years ago, # ^ |   +8 I think I understand what you say correctly. As a writer, I always hope my problem to be the same with other old problems. But usually I can still see other people say he create the same problem before.(I am so sad that see somebody say he set the same problem before with my SRM629 Div 1 hard. OAQ).At least I think the idea of the problem pE is far away from the problem you mention. But it seems you don't think so. The only thing I can say is very sorry.I am eager to create totally original problems OAQ.
•  » » » » » 8 years ago, # ^ |   0 probably if one solved many problems he can arrive high rating,but for a particular contest I think it should be fair to everyone not only to the one who solved many problems in past(especially who solved the similar problem in the past)(at least problem writers should try his best to avoid similar problems in contest)
 » 8 years ago, # |   +1
 » 8 years ago, # |   0 I'm trying to submit a solution to the Div2 E problem, but I'm repeatedly getting WA on the first test case itself, even though my code is giving correct answer for both the sample test cases on my machine. Here's one of my submissions for reference. TIA.