matrix's blog

Codeforces Round #240
By matrix, 11 years ago, In English

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

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

  3. Egor

  4. qwerty787788

  5. hos.lyric

Div 2:

  1. jzzhu

  2. SJTU_WengJian

  3. alcot

  4. LoveEvita

  5. huyifei

  6. NiuYiqiang

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.

  • Vote: I like it
  • +291
  • Vote: I do not like it

Comments Comments (158)
| Write comment?
»
11 years ago, # |
  Vote: I like it +21 Vote: I do not like it

2 Iranian problem setters , that sounds great !

I wish it will be different and special round :)

→ Reply
»
11 years ago, # |
  Vote: I like it +74 Vote: I do not like it

I think there will be a matrix problem :)

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I wish you all good luck and increase the rating

→ Reply
»
11 years ago, # |
  Vote: I like it -44 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
← Rev. 4   Vote: I like it +13 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Delayed?

→ Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

hey, has the round been postponed by 10 minutes? i suddenly see 00:11:42 in the countdown!

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is the contest delayed ?

→ Reply
»
11 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

wish a nice contest

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok you're right

      → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

can we know the reason for delay?

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

last 30 seconds~~~~

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -17 Vote: I do not like it

    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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it -21 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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)

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it -9 Vote: I do not like it

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


#include<iostream>
#include<cstdio>
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;

}
→ Reply
»
11 years ago, # |
  Vote: I like it +9 Vote: I do not like it

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

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

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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!

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Pretest 4 is pretty strong.

→ Reply
»
11 years ago, # |
  Vote: I like it +11 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    are u referring to the warning which says to not submit solutions using the %lld specifier in C++?

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    In fact, we do not have any problem now even if we use %lld on Codeforces.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    luckily for u, it passed. but only just (3447ms)! ;)

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it +6 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it
    • Test Case
    • 1 2 9
    • 5
    • AC output:0
    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      why the answer is 0? still dont get it

      UPD : okay i understand now

      → Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

Nice problems, I liked them.

→ Reply
»
11 years ago, # |
  Vote: I like it +59 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +6 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I was also stuck for a long time :(

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    and then i realized that it's a . not -

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I need to pay more attention to details.

    → Reply
»
11 years ago, # |
  Vote: I like it -8 Vote: I do not like it

why is system testing taking so long today?!

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Perhaps system test cases of Problem C are so abundant.

    → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Any hint for task D , DIV2?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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]

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Combinatorics

    → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No one did. I found 1 C#, 1 Delphi and about 20 Java.

    → Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    I've got AC on Python 3.3

    That was easy 6288729

    → Reply
»
11 years ago, # |
  Vote: I like it +5 Vote: I do not like it

It feels like System Testing Became slow........

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +4 Vote: I do not like it

When can we see our new rates?

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    now it is updated...

    → Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    → Reply
»
11 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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.

→ Reply
  • »
    »
    11 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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!

    → Reply
»
11 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

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.net/contest/415/submission/6284352

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it is n^2logn

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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 .

    → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it +41 Vote: I do not like it

Round Stats

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
11 years ago, # |
  Vote: I like it +14 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you tell me how the idea of this?

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

      → Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    1 135360 718513035 261734062

    the answer is 4435 your program will say it is 600415575

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same as mine. try this 1 2 9 5

    the answer should be 0

    → Reply
»
11 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the problem D in div1

→ Reply
»
11 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply