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!

Holy shit!!! There is eight Grandmaster and one International Grandmaster...

Red Alert! :P

And there is some MikeMirzayanov !!!

when i saw your comment i just had to make this

It's gonna be LEGEN wait for it DARY!!!

artofproblemsolving

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

Div1 participants be like

funny

I am scared!

Feeling unfortunate for not able to participate in such a "red hot" contest due to exams. :(

It's good that I have school just in the afternoon :D

(on the other hand, will I wake up so early?)

Oh, come on, 5 hours till the contest, why sleeping at all?

Because I'd be sleeping at lectures otherwise (again) and it's not very nice to lecturers to always sleep through everything :D

To sleep or not to sleep...

I always hated English class -_-.

ditto! but my English is poor!

Such a beautiful day on most places in planet earth, would love to get some minus from the awesome people in codeforces.

challenge accepted:))

wish you all best luck

Thanks. I love you

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

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

If you don't submit anything , your ratings will not be screwed

want to enjoy this contest and hope rating increases :P

The contest is very bad time in IRAN

where's the score ditribution ??

7 Problems and 10 Red problem setters...

Not everyone in the list is a problem setter :)

I have missed my academic Classes and waiting for

CodeforcesRound 295.No rooms???

Edit: Fixed

where is rooms?

:'(

nice modulo used, first time 1000000007, second 1000000009, third 1000000007

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

Yyyy, is 1000000009 clearer than 10^9 + 9 ; d? But I agree that those modulos were pretty stupid...

You can copy-paste 1000000009, which removes some room for error.

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

Cause of this I write

`mod = (int)1e9+9;`

I always use my template like it, so I'll write code such as "ModInt<>", rather than "ModInt<1000000009>", because of stupid habit.

Unpredictability.

Now I know what was wrong with my code :(

Single change of line gets acc :/

See more on Know Your Meme.

Were there any successful hacks during this round?!

Edit: Xellos beat me to it :)

A pretty solid amount. If we're talking both divisions obviously.

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

Good! Today you have answer for n,k<=15,tommorow to n,k<=30 ... after around 7500 days you certainly have correct solution :D

So I have to wait for 20 years.

Or you could copy some of it(answers) and buy yourself some years :)

I finally got AC. 29 hours......

mogityantt testebi da amocanebii,meore amocanis 4 testis shemdgenels movutyann suyvelaperiiiiii ( :) <3 best wishes!!! )

Problems were fantastic, I LOVED this contest. It was more think-based than algo-based.

shen chemi dzma gemeixede aqett O_o mogityann azrovnebaa ,ra iyoo kaii mitxarii ertiii haa?

how to solve problem C Div.2? Ô.Ô

Please, wait, we can't discuss the problems yet.

(-- apparently I should hide this --)

It's little like Greedy

Today was very nice time for Korean Users.

I always woke up in dawn to compete.

In case anyone missed it:

we ask you not to discuss the problems and solutions in the comments until 14:10 MSK

That's 2 hours from now.

Div2 D and E were HARD. (at least for me, unexpectedly harder than the usual D2 D and Es) :(

It was nice. thank you.

this round is hard :) but has got nice problems.

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.

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

Damn it! Whatever, problem C took me 15 minutes but the contest was over :'(

Happens man :)

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

Hm, that possibility of not submitting code if one solved it too late is wrong and should be changed...

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!Oh, my bad. Thanks!

Read the input line properly, its given distinct n,m

Codeforces round 287 : Rank 192, rating change 1582 to 1699

Codeforces round 295 : Rank 95, rating change 1612 to 1699

I'm a bit luckier than you. My rating now is 1698 -_-

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

You got your brother man!! :D check this out http://codeforces.com/profile/dc26

Another brother

Yeah that's me

Kind of similar story :p

Codeforces 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

1699 to 1699 ._.

I spend very much time understanding the meaning of Problem B.QAQ

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

There were only 20 minutes left when I truly understood the meaning of Problem B.T^T

Question like this (involving complicated, non-trivial process) should deserve explanation of the sample input at least.

Can anybody tell how to solve div-2 E ??

maybe DP, and with some combinatorial mathematics?

i know a n*k solution using dp but that will time out .

I still can't view other's codes yet...

How to solve Div1 C?

Above formula works when k > 0. When k = 0, then simply output s

please explain how u arrived at this formula .. thnx

I'd appreciate a brief explanation.

Consider some digit

dand all summands, where this digit is thei-th least significant. It will add 10^{i}dto the answer for every way to choose the`+`

s that makes that digit thei-th least significant in some summand. That means there are no`+`

s on the nextipositions (between two digits) and there is one (or the end of the string, which gives 2 cases) on thei+ 1-st position. There are no other restrictions, so we just need to putK- 1`+`

s onN- 2 -ipositions orKonN- 1 -ipositions; the number of ways to do that is given by binomial coefficients.Another optimisation lies in adding up the same thing for all digits

dfarther thanifrom the end of the string at once, by quickly counting how many such digits there are.I was thinking the explanation and then I found that your explanation is much clearer than mine.

What's the test 8 for the Div2-C?

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.Why I can't see others code and test cases?!

i need see the tests cases :(, i will not sleep until that happens :(

why are the solutions not visible yet !!! ?? I hope the other contest is over ??

Eagerly waiting for the editorial !!

How to solve Div2 C?

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.

What is the proof of your solution ?

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.

Thanks :)

k => Amount of letters with bigger frequency in input

n => Lenght of input

sol = k^n % MOD

My solution

http://codeforces.com/submissions/dc26

Observe 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*Y1where

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.

http://codeforces.com/contest/521/submission/10108767

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

Is this what you want?

What is the logic behind this solution ??

Well there are only 4 characters, and the max results has 60k digits, which should be able to fit in the time limit.

Is there a way to solve Div1-B without using multiset?

You can use priority queues. I'm not sure this is the answer you are looking for :)

Div-1 B why is evryone converting m to n ... how is that easier than converting n to m

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.

You also can sort all of the cubes and use two iterators for the current upper cube and the corresponding cube it lays on.

Can you tell me how to solve div.2 C?

He won't tell, but you can see this submission: 10118102

Thanks a lot. this " j=(j*z)%M;" Can you tell me why? my English is poor please forgive me

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

I knew it .thanks a lot

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

Is there any editorial for problem Div.1-D?

The editorials for all problems are coming. I'm sorry for the delay.

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.

How to solve Div2-E / Div1-C?

I could find just a dp solution which takes

`N * K`

.Any helps would be appreciated...

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?

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

first person can take 0, 1, 2, 6, 9 he will choose 9

second person can take 0, 1, 2 he will choose 0

first person can take 1, 2, 4 he will choose 4

second person can take 1, 2 he will choose 1

first person can take 2, 6 he will choose 6

second person can take 2, 3 he will choose 2

first person can take 3, 7 he will choose 7

second person can take 3, 8 he will choose 3

first person can take 5, 8 he will choose 8

second person take the remaining 5

so the result will be 9041627385 % 1000000009 = 41627304

Can someone please explain the logic of Problem C(DIV 2) ?

explained already!! http://codeforces.com/blog/entry/16707#comment-215954

520B - Две кнопки 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?

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.

Heh, after reading that savinov is also a problemsetter, having #285 in my mind (when I have written two full of hate comments and they turned out to be my two most upvoted comments ever :P) I was scared that some noninteresting problems will be included. And after publishing editorial it turned out that he set one problem — guess which — of course the most shitty one ( ͡° ͜ʖ ͡°) (I hope that it's clear it is B).

B was just straightforward simulation. Could anyone point me something interesting in that problem :P? Moreover it was not nice to code (not that awful since that is still an easy problem, but ratio awfulness of code / needed thinking is still very high). Not to mention that when coding it I got sick of it and switched to C (which turned out to be a good decision, since it was easy) and then read D and couldn't resist solving that very interesting problem (kudos to Endagorion!), even though I was aware that EV of my rating will be higher if I will return to B.

What is more, it got terrible and very confusing statement. In the very title we are told that this problem is about cubes, I have always thought that cubes are something living in 3D space, it turned out that I was mistaken. Then "Let's consider a coordinate system such that the OX is the ground, and the OY is directed upwards." — ok, so OZ is that only one remaining. Then "The figure turned out to be stable. This means that for any cube that is not on the ground, there is at least one cube under it such that those two cubes touch by a side or a corner." — ok, so if directly under one cube there is another one and it touches it by whole face then it is not stable and if area of tangency region is 0 then it is stable? Great idea! Then some confusing part about clarifying that statement which I unfortunately omitted looking for some helpful infos in latter part of statement. And after reading the whole statement I realized "ok, so those 'cubes' are 2-dimensional, good to know" ( ͡° ͜ʖ ͡°) (and of course I needed to reread the statement completely).

I have always thought that Codeforces rounds is not a place for some "ACM Out Of Nowhere Regional"-style problems which statements can be compressed to "You got some stupid rules — simulate it".

I am aware that this is pretty offensive and sorry about it, but I just couldn't help writing that. I think that simply savinov's rounds will be the only ones I will omit purposefully. Maybe it's too big amount of hate for posting just one noninteresting problem (of course I have seen much uglier problems), but facts that it was given together with Endagorion's problems and its terrible statement empowers that impression significantly.

I thought Problem B and D are very similar, so I don't understand your claim.

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.

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

You know, you also keep a priority queue in Dijkstra, but I won't call it similar algo to those ones. In B one has to come up with an ingenious observation "We want to maximize number (with fixed length). Let's maximize greedily the most significant digit!" and update available values (which for sure doesn't have anything in common with D), while in D you can just take a prefix of upgrades sorted in some funny order without any modifications during choosing them consecutively, so I still no longer see any common things other than greediness.

Moreover I guess that you have at the moment 2572 rating not for no reason and D might have been clear for you, while I think it was in fact very tricky, while B was straightforward and just demanded some carefulness when coding it (D also).

The most tricky part in D was in my opinion observing that we can choose to buy upgrades in other order than we have to perform them. But things get even more complicated, because if we will perform adding and multiplying only then for each upgrade we know how many times it will increase result, but things get complicated when we are dealing with assingments, because for addings the ratio after performing it and before changes if we will perform an assignment or not, but next observation is that this is in fact not an obstacle since we can simply treat greatest assignment as an ordinary adding (and forget about others). I consider that reasoning very nice, suitable for D problem.

By the way I didn't notice that we can choose to buy upgrades in other order than we have to perform them and computed best way assuming that we use exactly k upgrades on that skill for all reasonable values of k. I noticed that if we won't perform all multiplyings (other than those with b=1) then we can perform at most 1 adding and iterated on that number and whether we perform assignments (I used logarithms to compare profits since they were too big). Then I observed that 2 *

prof[i][j] > =prof[i][j- 1] +prof[i][j+ 1], what allows us to do everything greedily. I think that those observations are also pretty nice, but unfortunately I didn't make it work since my code turned out to be pretty tedious and vulnerable to many small mistakes.It should have been mentioned that Vasya and Petya are cosmonauts working on this experiment in zero-gravity conditions.

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.

Lol, you will have hard time in competitive programming if you call such problems "math" ; d

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.

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.

I'll go ahead and do that, thx.

BTW I should say I was joking about the tags (and this) ^_^

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

mathinbadsense 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? OrAd Infinitumcontests at HackerRank?You know, when I was solving this problemset — I was actually happy that problem B was 2D instead of 3D)

Of course I was happy also, but fact that I learnt that after few minutes is not nice :P.

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.

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 frequently

so 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/ZedQOQ

I'd be grateful for help

The strings you provided don't attain the maximum value. Have you tried computing the value p(s, "GGGGGGGGGGGGGGG")?

Thank you. The result for GGGGGGGGGGGGGGG is better ( 1350)

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

very sexy contest!!! :D :D :D

waiting for new contest !!... I want to became CM