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

The problems are from Dreamoon 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 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. qwer

3. kutengine

4. ifsmirnov

5. TankEngineer

Div2:

1. ridowan007

2. a00012025

3. xavier13540

4. v_Enhance

5. pkq2006

And standings are here:

Div1: результаты

Div2: результаты

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

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 been doing the past few contests? Trying to be another worse ?

Actually, worse began the journey to red

I heard Dreamoon said that he has some

plansabout it =)Just Petr can paint his rating curve according to his wishes, noone else should try to do so.

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`

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.

I think you should write a warning about the unusual time of the round

Some people may miss the round if they didn't notice that.

This round will be held at CST-1:30 (1.5 hours before Codeforces Standard Time)

Let's hope for math :)!

yep he always hope for math for me I always hope for early score distribution announcement :D

I expect it will be a very Nice contest and contains various problem set

Dreamoon 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

Doesn't being an international grandmaster (like dreamoon was before his fall (partially on purpose)) is a sufficient proof :P?

sometimes Theorem has more than one proof :P :D

Dreamoon 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

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.

I don't think he'd go to school at night :D

A 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

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.

Damn. Bayan Qualification + Marathon24 + NEERC + Codeforces Round #272.

Because screw weekends

You count Bayan Qualification along with those other contests? >_>

I'd replace it with Codechef Long Challenge, it has more decent problems now.

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?

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.

what a nice contest time :)

In the div2,the second problem is 1500,I dont't think it's easy.

the third problem also 1500 , what do you think ?

I don't think it's easy,too,uha.

I agree with 12310720112 -_-

Thank you for agreeing with me,haha~

I think a newly registered guy will be on top of Div.2 contest.

I think no because newly registered guy has a Div1 contest at this time :D

Petr will win Div1.

Well, you called it O.o

Found out that I don't have a pen at home 10 minutes before the contest. Going to use Paint instead of pen!

Oh I forgot registering contest.. :<

Goodbye red color :(

Goodbye blue color :(

Goodbye green color :(

Welcome Blue color:)

Goodbye purple.

Next time I'm going right to yellow! (not really)

Goodbye green color :(

Goodbye yellow color :((

Sayonara purple!

But not today!

Goodbye

Orange, helloRed:DGoodbye Div.1 :(

Who else failed A because of long overflow

Are you happy with math problems?

C was good non maths problem >:D

Yes I am happy (yay I got B) but failed A

I don't understand why this naive code fail for pretest 5. code

I was using that for find my mistake, but I couldn't

Because (i%b) should be a divisor of (i/b).

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...

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

longoverflow.really tricky on this part.how to solve B -div1 ??

Output ((6

i+ 1)k, (6i+ 2)k, (6i+ 3)k, (6i+ 5)k) for alli= 0, 1, ...,n- 1. (And thus the maximum is (6n- 1)k.)missed it completely ...thnx

Why 6i ???

why this 6*i+1 format ?? I mean a simple proof ?

See here

Basically you need three odd numbers for each set, and there are 3 odd numbers every 6 numbers.

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, 6

i+ 1, 6i+ 2, 6i+ 3, 6i+ 5 has pairwise GCD 1 for any integeri, so we might as well use it. By using all lowest values ofi(namelyi= 0, 1, 2, ...,n- 1), we have maximumm= 6(n- 1) + 5 = 6n- 1. Also note that since we need three odd numbers per set, we need 3nodd numbers, and ifm< 6n- 1 then we don't have enough odd numbers to use. Thusm= 6n- 1.Remember that we have divided everything by

kto make the pairwise GCD 1 instead ofk, so now just multiply everything bykagain.why 6 !!!

why not any other even number 4, 8, 2, anything :3 ?

You need three odd numbers (one can be even), and this happens every 6.

I wrote for each set

6i+1,6i+3,6i+5and 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 tokandm=(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?You read in n as k and k as n.

n comes before k in the input.

OMG I've just found it)) that is impossible misstake)) I can't believe it =D tnx

and it passed after changing n and k

92anurag was the first to ask.

Uhm, the solution is in the sample. Just use 6

i+ 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.thnx ..got it

Nice idea, I haven't noticed this pattern in the sample. :(

What kind of sorcery is this?

math man, math!

why wa on pretest 5 of question C. http://codeforces.com/contest/476/submission/8207485

Explanation for problem C Div2?

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

10^7 * k operations (where k < 50) should mostly pass.

I did the same. Can you tell me why 8200906 is hacked?

You casted to double, losing precision. (Double can only hold about 53 bits of precision; with

a= 10^{9}, that you're computing needs 59 bits.)Thank you! And also, how do you calculate how much precision it needs?

Oops, I have successfully confused myself.

a= 10^{7}, not 10^{9}.No, the problem is below that:

`sum*i*b`

essentially explodes. Witha=b= 10^{7},i= 10^{7}- 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.

I actually tried

`sum*((a*b)%MOD)`

I doesn't work either.You want

`sum*i*b`

not to give overflow. Thus:`sum`

earlier. Insert`sum %= MOD;`

before the line, or perhaps after computing`sum`

with that casting to double.`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.

Yeah, it worked! Thank you really much. I appreciate your effort.

`(ll)`

expected, but`(double)`

foundShouldn't it be double because something divided by 2 might something.5?

use

`(ll)(a+1)*a/2`

insteadBecause there is exactly one even number in a+1 and a.

There should be another mistake somewhere else because it still doesn't pass. 8208763

`sum`

is too large.Observe that all numbers satisfying the condition has the form

x= (bk+ 1)(mod(x,b)). Sincemod(x,b) can be any integer between 1 andb- 1 inclusive,kcan be any integer between 1 andainclusive, 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 somex. 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...Time limit is 0.00001 seconds ?

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

Yes, both O(b) and O(a) will pass. Can you rephrase the second question as I did not understand it.

I did the same.

But why i got WA?

http://codeforces.com/contest/476/submission/8205508

Check your mod and division by 2. http://codeforces.com/contest/476/submission/8210369

Nevermind.

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

Yes I noticed after :D Thank you !

Thank you.

(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

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. )

Note that

x=b·div(x,b) +mod(x,b). (This is more or less by definition;div(x,b) isx/brounded down, thus when multiplied bybgives the largest multiple ofbnot exceedingx, andmod(x,b) is the missing amount to bring the multiple ofbup tox.)The rest is just plugging in what's given in the problem and manipulating a bit.

Thank you ! It's really help me.

Now we see that , r can be 1 to b-1. thus for a particular value of k, we have

so , psudocode is below

don't forget to mod every expression.

I spend more time for problem C div 2, I am bad

Yeah i did that too. i was just getting confused with all those numbers . (defined by problem and me !)

Very interesting problems! Thanks to authors!

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 .удален.

This is my submission on A Div.1: 8203037

What is wrong with my expression?

Because your algorithm is wrong !!!!!

Thank you, captain obvious :v

Btw I'm asking what's wrong, not why it's wrong :v

I don't understand your questions

ok what? your algorithm

I think you misinterpreted the problem or something, thinking that you're only counting numbers between 1 and

aor something, not counting numbers whosekis between 1 anda.solution of div2-E / div1-C someone please?

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.

Isn't this O(pn^2), too slow?

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.

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?

there is precalculation of |S|*|S|

then the dp too is |S|*|S|

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.

But its only O(n^2).

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?

long double,you should use cout<< to output....Ld is not using to output long double

BTW,if you run this code in CF.

you will find sizeof(long double) is 12 in CF...

who can tell me where is my "#"? and why the string is bigger than others?

`#`

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.THX~~

thanks for your answer.

I'll use cin/cout in future. but. I think printf("%f",(double)ld); is not bad.

C Fail system test on 26.... Yellow, here I come back!

Can anyone explain pretest 5 (input: 4 3) in problem C(div.2)?

Which numbers should be added?

a= 4,b= 3Try for

k= 1. We wantdiv(x, 3) =mod(x, 3). Sincemod(x, 3) = 1, 2, we thus have two numbers: one withdiv(x, 3) =mod(x, 3) = 1, and one withdiv(x, 3) =mod(x, 3) = 2. The numbers satisfying this are 4 and 8 respectively.Try for

k= 2. We wantdiv(x, 3) = 2·mod(x, 3). Sincemod(x, 3) = 1, 2, we thus have two numbers: one withdiv(x, 3) = 2,mod(x, 3) = 1, and one withdiv(x, 3) = 4,mod(x, 3) = 2. The numbers satisfying this are 7 and 14 respectively.Trying for

k= 3 gives 10, 20, and fork= 4 gives 13, 26.Adding them all gives the requested 4 + 8 + 7 + 14 + 10 + 20 + 13 + 26 = 102.

Just write a brute force ....

the numbers are : 4 7 8 10 13 14 20 26 sum = 102

Hello !

what's wrong with my code?! for div 2 C

http://codeforces.ru/contest/476/submission/8197243

`((b % mod) * (sum2 % mod) * (sum1 % mod))`

If

`b % mod`

,`sum2 % mod`

,`sum1 % mod`

are together pretty large (about 10^{9}each), they make the resulting number to get overflow (about 10^{27}).Try to mod every value RIGHT AFTER multiply. Don't multiply three values in a time, it will be overflow.

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

Changed

to

and my C passed ;__;. I'm such a loser ;_;.

How to solve div1-C?

First you need to calculate nearest subsequence that match P and start from i for every i<s.size .

Now we can use a simple dp, at each position we have 3 choices :

1- you can skip this position to next one so : rec(pos+1, should_delete).

2- you can delete this position if should_delete!=0 so : rec(pos+1, should_delete-1).

3- if we have match from pos we can use this match, we have the ending position of this match (calculated in first step) so number of characters we need to delete so we can use this match is : end[pos]-pos+1-p.size . now if this number is less than or equal to should_delete then you can use this match so : 1+rec(end[pos]+1, should_delete-(end[pos]-pos+1-p.size)).

The answer for each step is maximum of this three choices.

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: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

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.

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???

Indeed, Codeforces should start giving T-shirts more often. I need Codeforces and Facebook T-shirts to complete my collection.

/\

Then some people would get too many t-shirts :D

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 !!

Thanks for the nice comment :)

Welcome vai :)

Thank drazil for this interesting contest!

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

sthat is equal top(this is constructing the array`found`

), by iterating over each character ofsandp, taking note when the latest starting position of a subsequence ofsending with the character inp. 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).what's wrong?

Can anybody give me hind how to solve prob-B div-2 My submission: http://codeforces.com/contest/476/my#

getting WA :(

Try to implement iterating over subset with bitmasking.If there are

`m`

question marks,you have`m^n`

options.Then something likeThen your answer will be

`ways/(double)(1<<n)`

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.

In problem C div 1 (E div 2)

`occ(s',p)`

was a set of substrings. What does "substring" mean?A substring of another string

Sis a string of consecutive characters ofS; in other words, it is formed fromSby deleting some (including all and no) characters from the front and the back, but without deleting any character in-between the chosen characters. IfS=abcd, thenbc,ab,b,a,abcd, ε are substrings ofS(ε is the empty string), butbd,abd,cbaren't.Thank you, sometimes it is not clear for me, is substring like subsequence — where you can delete some character in-between.

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.

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)) =kinstead, as the problem already defineddiv. And of course you can always ask the problem setter using the question asking feature.No. It was stressed that their quotient must be an integer (e.g. not real), which is sufficient.

I didn't understand prob C. Could someone please explain me this problem

(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#

long long?

Btw — look at the link you've attached. There is "my#" in the end. Is this what you wanted to link :)?

Is there a bug with the rating? It looks weird ._.

:D

didn't reach red, thats bad :D

I apologize for a re-post but i can't understand why this summation works for Div1-A/Div2-C ![ ]()

seeking answer to same question....

Why this summation works/how one has come up to this summation??

and . So expanding that summation will give the exact formula as the one in editorial.

hm...please tell me where is my mistake in div2b? (wrong test 11 after all formatting)

abs() (((((((((((((

Div I problem E: an almost same but stronger version of this problem:

http://codeforces.com/gym/100162/problem/I

This problem can be solved with O(m n log n) with simpler idea and implementation in comparision with Div.1 E.

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

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.

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.

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

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.

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)

Round Stats

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.