### matrix's blog

By matrix, 6 years ago, ,

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:

1. louise

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

3. Egor

4. qwerty787788

5. hos.lyric

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.

• +291

 » 6 years ago, # |   +21 2 Iranian problem setters , that sounds great ! I wish it will be different and special round :)
•  » » 6 years ago, # ^ |   +8 Hope the problems be interesting like havaliza's problems :)
 » 6 years ago, # |   +74 I think there will be a matrix problem :)
•  » » 6 years ago, # ^ |   -12 What makes you so positive?
•  » » » 6 years ago, # ^ |   0 Nickname of the topic starter.
 » 6 years ago, # | ← Rev. 2 →   0 is it only me that has received the announcement first time in Russian despite primary Language being English in codeforces?
•  » » 6 years ago, # ^ |   -6 I received the announcement in English
•  » » » 6 years ago, # ^ |   -13 In fact,Everyone has been informed
 » 6 years ago, # | ← Rev. 2 →   0 I wish you all good luck and increase the rating
 » 6 years ago, # |   -37 parcham balast amir,farbod dameton garm ;-)
 » 6 years ago, # |   -44 Do you know dibil power Ha ? this is 1000th dibil :D HURRAY DIBILS
•  » » 6 years ago, # ^ | ← Rev. 4 →   -22 oh no -44 HELP DIBILS
 » 6 years ago, # | ← Rev. 4 →   +13 i don't know how, but i'm registered twice for this contest! EDIT: sorry the image i initially posted was too large, so here is link to image
•  » » 6 years ago, # ^ |   +28 Thanks. Nothing dangerous. I'll fix it before the round.
•  » » » 6 years ago, # ^ |   +35 cool thanks. but plz make sure to remove only one (not both) :P
•  » » » 6 years ago, # ^ |   +1 i think the issue is fixed now. thanks for ur help! :)
•  » » » 6 years ago, # ^ |   0 Same here
•  » » 6 years ago, # ^ |   +36 May be the rating will increase or decrease twice ;)
•  » » » 6 years ago, # ^ |   +3 I love coding too. :)
•  » » » 6 years ago, # ^ |   0 i wish it had! :P
 » 6 years ago, # |   +19 Wish both Iranian problem setters, Amir Keivan and Farbod, Gold medals in this years INOI. Good luck.
 » 6 years ago, # |   +4 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
•  » » 6 years ago, # ^ |   +1 Usual time. There was an issue around timezone support.
 » 6 years ago, # |   +12 Delayed?
•  » » 6 years ago, # ^ |   0 Delayed!)
•  » » 6 years ago, # ^ |   0 Yeah. Probably related to the occasional crashes ("Service temporarily unavailable.")
•  » » 6 years ago, # ^ |   +64 Will it ended like TCO 2014 Round 1A yesterday ?
•  » » » 6 years ago, # ^ |   0 I hope not!
•  » » » 6 years ago, # ^ |   0 No, I think it won't be held next week, like TCO Round 1A.
•  » » 6 years ago, # ^ |   0 number of registers keep increasing... from around 900 to 1000...
 » 6 years ago, # |   +1 hey, has the round been postponed by 10 minutes? i suddenly see 00:11:42 in the countdown!
•  » » 6 years ago, # ^ |   0 i agree with you
•  » » » 6 years ago, # ^ |   +1 nice hahdle
•  » » » » 6 years ago, # ^ |   0 thanks :D
•  » » » » 6 years ago, # ^ |   0 So you can vote for my handle :)
•  » » 6 years ago, # ^ |   0 yes
 » 6 years ago, # |   0 Is the contest delayed ?
•  » » 6 years ago, # ^ |   0 as you see
 » 6 years ago, # |   +22 Let's hope it is not a problem like what happened in TCO yesterday.
 » 6 years ago, # |   +2 Is that server downtime ? I saw "Codeforces is temporary unavailable" page several times just before some minutes.
•  » » 6 years ago, # ^ |   0 I don't know, but let's just hope everything is under control.
 » 6 years ago, # |   -17 احا !!
 » 6 years ago, # |   0 wish a nice contest
•  » » 6 years ago, # ^ |   0 Что такое? Пишет осталось 4 мин, время проходит, и снова 4 мин, уже 3 раз.
•  » » » 6 years ago, # ^ |   0 ok you're right
•  » » » 6 years ago, # ^ |   -8 Время до закрытия регистрации; Время до начала контеста; Второе время до начала контеста.
 » 6 years ago, # |   +5 can we know the reason for delay?
 » 6 years ago, # |   0 last 30 seconds~~~~
 » 6 years ago, # |   0 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?
 » 6 years ago, # | ← Rev. 2 →   0 LOL I think this is the first round I've encountered on CF that the English statement is correct instead of the Russian one.
•  » » 6 years ago, # ^ |   -17 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
•  » » 6 years ago, # ^ |   -21 What? There were 8 hocruxes? And 8th was hidden in Tom's CF account? One more HP movie? Harry Potter and Codeforces account LOL
 » 6 years ago, # |   +8 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)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 I too faced the same problem , and misread it floor ( (w-a)/b) instead floor( (w*a)/b) . Wasted 45 mins :(
 » 6 years ago, # | ← Rev. 3 →   -9 Why my solytion on problem C-div 2 gets TLE? #include #include using namespace std; int main() { int n,k;scanf("%ld%ld",&n,&k); int d=0; if(n&1){n--;d=1;} if(n>>1 > k){printf("-1\n");return 0;} else { int bn=n/2; printf("%ld %ld ",(k-bn+1),2*(k-bn+1)); bn--; int j=2*(k-bn+1)+1; while(bn--) { printf("%ld %ld ",j,j+1);j+=2 } } if(d==1) cout<<1000000000-1<<"\n"; return 0; } 
•  » » 6 years ago, # ^ |   0 use this
•  » » 6 years ago, # ^ |   0 or you could also use ideonei find it more useful for sharing code.. :)
•  » » 6 years ago, # ^ |   +1 Your code ran endlessly when dealing with the special case n=1.
•  » » » 6 years ago, # ^ |   0 thanks
•  » » 6 years ago, # ^ |   +1 or even paste ubuntu
 » 6 years ago, # |   +9 Nice statements... Easy to understand... :)Hope to see you again as author.... :)
 » 6 years ago, # |   +3 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!
•  » » 6 years ago, # ^ |   0 can you say what was the wrong i think i do same wrong
•  » » » 6 years ago, # ^ |   0 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...
•  » » » » 6 years ago, # ^ |   0 isnt x%b enough?
•  » » » » » 6 years ago, # ^ |   0 nope... it is not enough... for example, take x=12, a=2, b=7... the actual answer is 1 but x%b gives 5...
•  » » » » » » 6 years ago, # ^ |   0 so i couldnt understand the B
•  » » » » » » 6 years ago, # ^ |   0 thanks
•  » » » » » » » 6 years ago, # ^ |   0 you're welcome
 » 6 years ago, # |   +6 Pretest 4 is pretty strong.
•  » » 6 years ago, # ^ |   0 if you are talking about problem C pretest 4 then i agree...
•  » » » 6 years ago, # ^ |   +3 Actually I'm talking about problems B, C, and D.Screenshot: http://i.imgur.com/b8M210d.png
•  » » 6 years ago, # ^ |   +4 i cant say much on pretest 4 until i see it, but i think pretest 7 is strong!
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +1 n=1 and k!=0 :D
•  » » » » 6 years ago, # ^ |   0 :D didn't take care of that... :P
•  » » » 6 years ago, # ^ |   +3 LOL , I made two wrong submissions one failed on pretest 4 and the other failed pretest 7
 » 6 years ago, # |   +11 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.
•  » » 6 years ago, # ^ |   0 are u referring to the warning which says to not submit solutions using the %lld specifier in C++?
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 In fact, we do not have any problem now even if we use %lld on Codeforces.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 luckily for u, it passed. but only just (3447ms)! ;)
•  » » 6 years ago, # ^ |   0 You can use %I64d, CF preferred %I64d. I used it instead of %lld.
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   0 Yes, it was exactly this.
•  » » » » » » 6 years ago, # ^ |   0 I see. Many thanks!
 » 6 years ago, # |   0 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.
 » 6 years ago, # |   0 who can explain 4th pretest on B question(div2)?
•  » » 6 years ago, # ^ |   +2 It was a special case. n == 1 (if k==0 print any positive integer, else print -1)
•  » » 6 years ago, # ^ |   +2 Test Case 1 2 9 5 AC output:0
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 why the answer is 0? still dont get itUPD : okay i understand now
 » 6 years ago, # |   +6 C was very nice. I've just finished it now. Big + for the authors. Very nice problems !
 » 6 years ago, # |   +17 Nice problems, I liked them.
 » 6 years ago, # |   +59 Pretests were too strong. I don't complain though :)
 » 6 years ago, # |   0 Can anybody help me guess why I have WA on the 7th test from Div1 A ? :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 Link your submission :D :D
•  » » » 6 years ago, # ^ |   0
•  » » » » 6 years ago, # ^ | ← Rev. 2 →   0 DEL
•  » » » » 6 years ago, # ^ |   0 Read the problem statement again, the numbers you print should be >= 1
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 You should output 1 (or any sufficiently small positive integer) for test case 1 0, not 0. The integers ai must be in the range [1, 109].
•  » » » 6 years ago, # ^ |   0 Omg! :DThank you, now I understand the mistake :)
•  » » 6 years ago, # ^ |   +3 if n=1 and k=0 you should print 1 instead of 0
 » 6 years ago, # |   +6 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 :/
•  » » 6 years ago, # ^ |   +1 I was also stuck for a long time :(
•  » » 6 years ago, # ^ |   0 at the first moment i thought like you did...and then i realized that it's a . not -
•  » » 6 years ago, # ^ |   0 I need to pay more attention to details.
 » 6 years ago, # |   -8 why is system testing taking so long today?!
•  » » 6 years ago, # ^ | ← Rev. 2 →   +8 Perhaps system test cases of Problem C are so abundant.
 » 6 years ago, # |   +3 Any hint for task D , DIV2?
•  » » 6 years ago, # ^ |   +3 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]
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 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.
•  » » » 6 years ago, # ^ |   +1 I use the same idea :D, i think it was an easy dp
•  » » 6 years ago, # ^ |   0 Combinatorics
•  » » » 6 years ago, # ^ |   +3 Really? Could you explain your solution?
 » 6 years ago, # |   +4 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?
•  » » 6 years ago, # ^ |   0 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.
•  » » » 6 years ago, # ^ |   0 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.
•  » » » » 6 years ago, # ^ |   0 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.
•  » » » » » 6 years ago, # ^ |   0 I was under the impression that O(KN) is already fast enough ("hey, only 4·106! Okay, perhaps multiply some coefficient, but it's not that large, isn't it?"), but you have a point too there.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 No one did. I found 1 C#, 1 Delphi and about 20 Java.
•  » » » 6 years ago, # ^ |   0 Delphi isn't "slow".
•  » » » » 6 years ago, # ^ |   0 That's why i said "no one did" :)
•  » » 6 years ago, # ^ | ← Rev. 2 →   +4 I've got AC on Python 3.3That was easy 6288729
•  » » » 6 years ago, # ^ |   0 920ms~~ how lucky it is~
•  » » » » 6 years ago, # ^ |   +1 6288836Optimized version, 530 ms
 » 6 years ago, # |   +5 It feels like System Testing Became slow........
•  » » 6 years ago, # ^ |   0 I think it is because of the special judge of div1 A(div2 C)...
 » 6 years ago, # |   +4 When can we see our new rates?
•  » » 6 years ago, # ^ |   0 just wait a minute~~~ the system is calculating wish your rate get increased~~
•  » » » 6 years ago, # ^ |   0 I hope so. Thanks. U2 I got to go to school tomorrow early morning so that's why I'm asking:D
•  » » 6 years ago, # ^ |   0 now it is updated...
 » 6 years ago, # | ← Rev. 2 →   +7 In (Div 2)problem B there was a huge confusion between — and . sign in the equation w.a/b
•  » » 6 years ago, # ^ |   +3 At first, I thought that the sign was —. Thus, I couldn't explain sample tests. The image of expression maybe not clear enough.
 » 6 years ago, # |   +17 Damn. I solved C in O(n22n) (plus O(n) per query), but my code wasn't fast enough during the contest. I only managed to optimize it well enough to pass around 1 minute after the contest.
•  » » 6 years ago, # ^ | ← Rev. 2 →   0 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:(
•  » » 6 years ago, # ^ |   0 My solution's complexity is O(n*2^n+mn)
•  » » 6 years ago, # ^ |   0 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!
 » 6 years ago, # | ← Rev. 3 →   +3 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
•  » » 6 years ago, # ^ |   0 I think it is n^2logn
•  » » 6 years ago, # ^ |   +18 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 k different values, so overall complexity is .
•  » » » 6 years ago, # ^ |   0 nice analysis！
•  » » » 6 years ago, # ^ |   0 i got it :) thaaaank yooou :)
 » 6 years ago, # |   +1 Waiting for the editorial for div1 C and E... I have no idea for these two ....
•  » » 6 years ago, # ^ |   -23 Maybe this fact will help you in Div1-C. For any x following is true: gcd(x, x + 1) = 1.
•  » » » 6 years ago, # ^ |   0 He said div1 C, not div1 A.
•  » » » » 6 years ago, # ^ |   0 Oops I thought it was div2 C. Sorry.
•  » » » 6 years ago, # ^ |   0 Are you sure this helps for div 1 C, not div II C?
 » 6 years ago, # |   +41
 » 6 years ago, # |   0 My screencast: http://codeforces.com/blog/entry/11471
 » 6 years ago, # |   0 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.
 » 6 years ago, # |   +14 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
•  » » 6 years ago, # ^ |   0 can you tell me how the idea of this?
•  » » » 6 years ago, # ^ | ← Rev. 2 →   0 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 hcretescu can store it in O(nlogn) space and multiply two matrix in O(nlog^2n).
 » 6 years ago, # |   +3 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??
 » 6 years ago, # |   0 My Problem B couldn't pass the pretest 4 ... what's the wrong with this? Can anyone faced the same problem?
•  » » 6 years ago, # ^ |   0 your solution is not correct, for example with a=2,b=3 and w=2, the answer is 0 not 1`
•  » » 6 years ago, # ^ |   0 w=((w%b)*(a%b))%b; cout<
•  » » 6 years ago, # ^ |   0 same as mine. try this 1 2 9 5the answer should be 0
 » 6 years ago, # |   0 How to solve the problem D in div1
 » 6 years ago, # |   +3 Is the system still pending on testing? I am not able to submit solutions for practice mode.