Hi everybody!

Codeforces round #240 will take place tomorrow 19:30 MSK

This is our first round in Codeforces and we hope that everything will be fine. The problems were prepared by Amir Keivan Mohtashami(matrix), Farbod Yadegarian(FarbodY) and Gerald Agapov(Gerald). Also special thanks to Mohammad Amin Khashkhashi Moghaddam(alex-mercer) for testing this round.

I want to also thank MikeMirzayanov for Polygon and Codeforces systems, and also Maria Belova(Delinur) for translating the statements.

We wish you a good and challenging round.

Have fun!

Score distribution:

div1: 500 — 1000 — 1500 — 1500 — 2500

div2: 500 — 1000 — 1500 — 2000 — 2500 (standard)

**UPD: due to technical reasons the round was delayed for 10 minutes. We apologize for any inconvenience caused.**

**UPD2:** **Congratulations to the winners!**

**Div 1:**

sankear (The only one who solved problem E during the contest. Congratulations!)

**Div 2:**

**UPD3:** The round analysis are prepared by DmitriyH. You can find them here.

Also the tutorial is not completely ready yet. But you can find some notes about some of the problems here. I'll try to complete it as soon as possible.

2 Iranian problem setters , that sounds great !

I wish it will be different and special round :)

Hope the problems be interesting like havaliza's problems :)

I think there will be a

matrixproblem :)What makes you so positive?

Nickname of the topic starter.

is it only me that has received the announcement first time in Russian despite primary Language being English in codeforces?

I received the announcement in English

In fact,Everyone has been informed

I wish you all good luck and increase the rating

parcham balast amir,farbod dameton garm ;-)

Do you know dibil power Ha ? this is 1000th dibil :D HURRAY DIBILS

oh no -44 HELP DIBILS

i don't know how, but i'm registered

twicefor this contest!EDIT: sorry the image i initially posted was too large, so here is link to image

Thanks. Nothing dangerous. I'll fix it before the round.

cool thanks. but plz make sure to remove only

one(notboth) :Pi think the issue is fixed now. thanks for ur help! :)

Same here

May be the rating will increase or decrease twice ;)

I love coding too. :)

i wish it had! :P

Wish both Iranian problem setters, Amir Keivan and Farbod, Gold medals in this year`s INOI. Good luck.

Is the contest time 19:30 or 23:30?

Currently (at least for me), the time on the contest list is 23:30 and the counter shows that the contest starts in 6 hours...

Screenshot: http://koti.mbnet.fi/pllk/cf.png

Usual time. There was an issue around timezone support.

Delayed?

Delayed!)

Yeah. Probably related to the occasional crashes ("Service temporarily unavailable.")

Will it ended like TCO 2014 Round 1A yesterday ?

I hope not!

No, I think it won't be held next week, like TCO Round 1A.

number of registers keep increasing... from around 900 to 1000...

hey, has the round been postponed by 10 minutes? i suddenly see

`00:11:42`

in the countdown!i agree with you

nice hahdle

thanks :D

So you can vote for my handle :)

yes

Is the contest delayed ?

as you see

Let's hope it is not a problem like what happened in TCO yesterday.

Is that server downtime ? I saw "Codeforces is temporary unavailable" page several times just before some minutes.

I don't know, but let's just hope everything is under control.

احا !!

wish a nice contest

Что такое? Пишет осталось 4 мин, время проходит, и снова 4 мин, уже 3 раз.

ok you're right

Время до закрытия регистрации; Время до начала контеста; Второе время до начала контеста.

can we know the reason for delay?

last 30 seconds~~~~

In Problem B,I can't see the picture about "how much dollar a worker can get if he returns w tokens". Then what should I do?

LOL I think this is the first round I've encountered on CF that the English statement is correct instead of the Russian one.

I have a guess:

since the authors are Iranian then they wrote problems in English and then the statements have been translated to Russian ,during translating the mistake happened

What? There were 8 hocruxes? And 8th was hidden in Tom's CF account? One more HP movie? Harry Potter and Codeforces account LOL

In problem B the image was so bad i made one wrong submission before asking a question to clarify that the expression was floor (w*a)/b , i had earlier thought it to be floor((w-a)/b)

I too faced the same problem , and misread it floor ( (w-a)/b) instead floor( (w*a)/b) . Wasted 45 mins :(

Why my solytion on problem C-div 2 gets TLE?

use this

or you could also use ideone

i find it more useful for sharing code.. :)

Your code ran endlessly when dealing with the special case

`n=1`

.thanks

or even paste ubuntu

Nice statements... Easy to understand... :)

Hope to see you again as author.... :)

nice contest...

made stupid mistake in B which led to me wasting too much time...

hope to learn a lot from the editorials... :)

thank you to the problem setters!

can you say what was the wrong i think i do same wrong

i took x-floor((floor(x*a/b)*b)/a) instead of x-ceil((floor(x*a/b)*b)/a)... took quite a while to realize this mistake...

isnt x%b enough?

nope... it is not enough... for example, take x=12, a=2, b=7... the actual answer is 1 but x%b gives 5...

so i couldnt understand the B

thanks

you're welcome

Pretest 4 is pretty strong.

if you are talking about problem C pretest 4 then i agree...

Actually I'm talking about problems B, C, and D.

Screenshot: http://i.imgur.com/b8M210d.png

i cant say much on pretest 4 until i see it, but i think

pretest 7is strong!n=1 and k!=0 :D

:D didn't take care of that... :P

LOL , I made two wrong submissions one failed on pretest 4 and the other failed pretest 7

Annoying issue with printf: As suggested in the problem statement, I tried using printf to output the numbers for problem C, but I could not submit because of the warning. In the end I had to submit the cout version, which I am afraid might time out.

are u referring to the warning which says to not submit solutions using the

`%lld`

specifier in C++?In fact, we do not have any problem now even if we use

`%lld`

on Codeforces.luckily for u, it passed. but only just (

`3447ms`

)! ;)You can use %I64d, CF preferred %I64d. I used it instead of %lld.

I had the same issue. And it is really strange to have a warning with "lld" which is correct. And no warnings at all wile using "ld" and it seems like there is no situation when it could be useful.

Previously there was a bug in MinGW, and

`%lld`

did not work — only non-standard`%I64d`

did. Now it has long been fixed, but the Codeforces warning remains.Oh, I didn't know the bug. Thanks. I thought the reason of the warning was that CRT used by MinGW hadn't supported

`%lld`

in the past.Yes, it was exactly this.

I see. Many thanks!

Liked the problems and the statements specifically, though I couldn't solve Div2 E, lol.

Would be really great if some corner and/or extreme cases were excluded from the pretests.

who can explain 4th pretest on B question(div2)?

It was a special case. n == 1 (if k==0 print any positive integer, else print -1)

why the answer is 0? still dont get it

UPD : okay i understand now

C was very nice. I've just finished it now. Big + for the authors. Very nice problems !

Nice problems, I liked them.

Pretests were too strong. I don't complain though :)

Can anybody help me guess why I have WA on the 7th test from Div1 A ? :)

Link your submission :D :D

http://codeforces.ru/contest/414/submission/6287121

DEL

Read the problem statement again, the numbers you print should be >= 1

You should output

`1`

(or any sufficiently small positive integer) for test case`1 0`

, not`0`

. The integersa_{i}must be in the range [1, 10^{9}].Omg! :D

Thank you, now I understand the mistake :)

if n=1 and k=0 you should print

`1`

instead of`0`

I thought it's (w — a)/b for the whole contest and couldn't solve it. I noticed it's a multiplication after viewing some solutions :/

I was also stuck for a long time :(

at the first moment i thought like you did...

and then i realized that it's a

`.`

not`-`

I need to pay more attention to details.

why is system testing taking so long today?!

Perhaps system test cases of Problem C are so abundant.

Any hint for task D , DIV2?

DP [len][last]

for i = 1 to n for j =1 to k for next= j to k with step j DP[i+1][next]+=DP[i][j]

it can be solved using dynamic programming. if u dont know about it, then first read up on it and solve 3-4 basic DP problems before reading below.

we can assume that

`dp[i][j]`

be the number of solutions such that`i`

elements are already chosen, and the last of them is`j`

.then we will have

`dp[i][j] = dp[i+1][j] + dp[i+1][2*j] + ... + dp[i+1][n/j*j]`

. and the base case is`dp[n][x] = 1`

.my AC solution 6275634 uses this idea.

I use the same idea :D, i think it was an easy dp

Combinatorics

Really? Could you explain your solution?

Problem D Div 2 (B Div 1): I should learn a faster language. Even

O(KN) on Python still fails the time limit (or I analyzed the run time incorrectly). Most people I asked had only but used C++ or Java or something fast. :(Is there anyone that tried to solve it in Python or some "slow" language and got accepted?

Sadly, not all problems are solvable using python on codeforces.

You should be cautious submitting problems having O(+1000000), It will most probably time out ... specially using python 3.

Heh, okay, guess I need to get my C++ skills up too. Never thought Python is this much slower than C++. And perhaps note to problem setters: problems that don't force the participants to use a particular language are good. I'm missing those.

It's not about being able to use any language, it's about writing a program that's fast enough. Maybe you could make a Python code work fast enough if you optimized a lot?

My solution of C (div1) has a complexity that makes it possible to pass, but it gave TLE during the contest, yet I'm not saying the time limit should've been larger. It's basically the same thing.

I was under the impression that

O(KN) is already fast enough ("hey, only 4·10^{6}! Okay, perhaps multiply some coefficient, but it's not that large, isn't it?"), but you have a point too there.No one did. I found 1 C#, 1 Delphi and about 20 Java.

Delphi isn't "slow".

That's why i said "no one did" :)

I've got AC on Python 3.3

That was easy 6288729

920ms~~ how lucky it is~

6288836

Optimized version, 530 ms

It feels like

System TestingBecame slow........I think it is because of the special judge of div1 A(div2 C)...

When can we see our new rates?

just wait a minute~~~ the system is calculating wish your rate get increased~~

I hope so. Thanks. U2 I got to go to school tomorrow early morning so that's why I'm asking:D

now it is updated...

In (Div 2)problem B there was a huge confusion between — and . sign in the equation w.a/b

At first, I thought that the sign was —. Thus, I couldn't explain sample tests. The image of expression maybe not clear enough.

Damn. I solved C in

O(n^{2}2^{n}) (plusO(n) per query), but my code wasn't fast enough during the contest. I only managed to optimize it well enough to pass around1 minuteafter the contest.6285907, 6288207 — first one got TL during the contest(the only one that passed pretests but got TL on systests), second one passed all system tests in practise mode. The difference is only in one line:(

My solution's complexity is O(n*2^n+mn)

I make a mistake in Div1 D, write a-(b-c) as a-b-c. I corrected this and submitted only to find that the contest was just over!

can anyone tell me what is the complexity of my solution to Div2 D problem ? at first i thought it n^2*k because of the loop in the function , i know that loop will not be completed at all , but it loops to n in worst case , when i tried the largest case it didn't take too much time , so i submitted it and it got AC , but i want to know the actual complexity of this solution ? My solution : http://codeforces.com/contest/415/submission/6284352

I think it is n^2logn

Note the following important "equation":

(it can be easily proved).

Now we see that in your code computation of dp[num][counter] takes about operations (and this is done for each 'num' and each 'counter'). Then for each counter computations are quite short:

The counter can have

kdifferent values, so overall complexity is .nice analysis！

i got it :) thaaaank yooou :)

Waiting for the editorial for div1 C and E... I have no idea for these two ....

Maybe this fact will help you in Div1-C. For any

xfollowing is true:gcd(x,x+ 1) = 1.He said div1 C, not div1 A.

Oops I thought it was div2 C. Sorry.

Are you sure this helps for div 1 C, not div II C?

Round Stats

My screencast: http://codeforces.com/blog/entry/11471

Were constraints in C that big (when O(n log n) (ofc n:=2^n) is expected constraints on CF are rarely higher than 200k) to make O(n log^2 n) exceed time limit? I have written solution in that complexity (I'm so incautious, I thought that this is O(n log n), when this was simply O(n log^2 n) xd) and I think noone will get hurt if those solutions will fit in time limit :P. In my computer on maxtest O(n log n) works 6s while O(n log^2 n) works 7s :P (but in CF difference is significantly bigger). But I won't whine much, I should've think a second before coding :d.

Nice problems, B from div1 can be done better in O( n log k * log^2(n)) with matrix multiplication http://codeforces.com/contest/414/submission/6290524

can you tell me how the idea of this?

Since dp[i][j]=sum{dp[i-1][j'] | j'|j }. Let Vi = (dp[i][1],dp[i][2],...,dp[i][n]) then you can find a matrix that Vi=M*V[i-1]. Thus, you can solve this dp with matrix multiplication. In this case the matrix seems to be in some special form so Horia can store it in O(nlogn) space and multiply two matrix in O(nlog^2n).

I don't know the reason that after system test, my problem A and B are "skipped"!!! (and A,B problems, I just submit one time) Could admin give me a reason??

My Problem B couldn't pass the pretest 4 ... what's the wrong with this? Can anyone faced the same problem?

your solution is not correct, for example with a=2,b=3 and w=2, the answer is

`0`

not`1`

w=((w%b)*(a%b))%b; cout<<w;

1 135360 718513035 261734062

the answer is 4435 your program will say it is 600415575

same as mine. try this 1 2 9 5

the answer should be 0

How to solve the problem D in div1

Is the system still pending on testing? I am not able to submit solutions for practice mode.