fchirica's blog

Codeforces Round #198
By fchirica, 11 years ago, In English

Hello everyone!

We invite you to participate at Codeforces Round #198, scheduled Friday, 30 August at 7:30 PM MSK. The authors of the problems are me and Linh (ll931110). We are also the authors of the Codeforces Round 191 (Div. 2). Last time, we received positive feedback for the round. We hope this round will be at least as good as the previous one.

Linh brought to you D2-C/D1-A and D2-E/D1-C. I wrote the rest of the tasks. We hope you'll spend more time writing on the paper and thinking than typing on the PC. In addition, all tasks don't require too complicated algorithms. Instead, all require some creativity, hard working and patience. BTWs, the main character of the round will be Iahub, as in the previous one.

I'd like to thank to DamianS, Gerald and Aksenov239 for testing the round. Without them, my job would have been certainly harder. Also, thanks to Delinur for translating the tasks and to MikeMirzayanov for the amazing Codeforces platform and Polygon system.

We wish everyone high rating and to have fun!

UPD1 The score distribution will be dynamic in both divisions. For more information please look here. The problems are sorted in our expected order of difficulty.

UPD2 Thanks for everyone who participated. I hope you fount problems interesting. Also, I think my prevision that you'll think more than write was correct :)

Congratulations to the winners.

Division 1

  1. yeputons
  2. KADR
  3. ftiasch
  4. Myth5
  5. huzecong
  6. R_R_
  7. Gabaum
  8. James
  9. ifsmirnov
  10. niyaznigmatul

Special congratulations to Igor_Kudryashov, the only person who solved D1-E!

Division 2

  1. Azat_Yusupov
  2. angel_of_monkey
  3. molamola.
  4. iseriohn
  5. Mato_No1
  6. silver__bullet
  7. TheDude
  8. Nero
  9. khuebeo
  10. uc-nuts

UPD3 The editorial has been finished. I'm waiting for your feedback / questions.

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

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

can't wait to find out who's the main character in the problem statements :D

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

You call positive feedbacks yelling at you about that u couldn't manage to avoid naive solutions' passing E.

Seems legit.

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

Err... Spend more time on paper... Does that mean this round we should draw sth, like round 195? by the way,thanks for ur hard work!

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

Our teacher said that this test is made by XHXJ,really?

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

Is this an individual contest? How to know if a contest is team or individual?

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

I was dreaming for months a contest like this: no complicated algorithms, spend more time writing on paper than typing on PC.

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

Good luck every one:)

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

GooD Luck :D

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

GL && HF!!!

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

Tasks will be sorted by difficulty in increasing order, will they?

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

How to solve B div2?

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

    For each 2 points I find maximum "left" and maximum "right" triangles(using that points) and sum them.

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

      i calculate all possible triangle,

      then try one by one lets call this one 'left', and check for other possible triangle which is share one of the same edge, and check if that the other triangle is inside the first triangle or not, and call this triangle 'right', then out = max(out,left+right)

      but i got wa :( in pretest 2, anyone care enough to correct my code :) http://codeforces.me/contest/340/submission/4381739

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

      Excuse me, How's the time complexity of your algorithm? I use an O(n^3) algo., but I got TLE. :( http://codeforces.me/contest/340/submission/4378019

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

        I use an O(n^4) algo and got AC, but before that I use a convex hull for a decrease count of points.

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

Problems are little bit hard for div2 contesters, but I have to say, very interesting problems.

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

Couldn't completely write NlogN of LAS for problem-D in time, because realized it in last 5 minutes. So sad =( And fchirica was correct, implementation was easy.

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

    You can use Patience_sorting.
    Here is my code which passed the system test

    set st;
    set::iterator it;
    for(int i=0; i<n; i++) {
    st.insert(a[i]);
    it=st.find(a[i]);
    it++;
    if(it!=st.end()) st.erase(it);
    }
    cout<<st.size()<<endl;

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

div 2 problems difficulty A D D D E !!

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

why doesn't the system testing start ? :-/

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

I hacked more than 10 'A' solutions with this test case:

1 1 1 2000000000

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

    Weak pretests , in previous contests TLE solutions did not get pretest pass

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

    me too hacked 12 with same

    → Reply
»
11 years ago, # |
  Vote: I like it -27 Vote: I do not like it
The comment removed because of Codeforces rules violation
→ Reply
»
11 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Special Thanks for your great contest! I'm willing to take all the downvotes only to thank you personally! :)

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

I think there is some problem on div 1 problem D'time limit! 2 dimension segmeng tree and the 2 dimension tree array have a same time complexity O(m*logn*logn),but you make first TLE and last one AC..it is different from usual cf's problem.

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

    i think you probably make some mistake about the time.

    the time complexity of quad tree is O(n) is indeed.

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

      !!!what?...i treat it as O(logn*logn) until now.=.=~..thank you~

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

        Can "xianduanshu tao pinghengshu" get accepted?I do want to do so,but when I see the time limit I changed my mind.(sorry I don't know how to translate it into english)

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

          I don't see the time limit at first....555...and after TLE by segment tree, i'm too native to believe that cf would not "卡常数"..so i didn't to write tree array at once.

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

      Are you sure about it? every step at updata or query on my quad tree(just like kd tree) , the area became area / 2. So i think the number of total steps is log(n^2), time complexity is O(logn*logn). Why you say it's O(n).

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

        I think it's O(N) for query(1,1,1,n)

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

          Agree.Your code is not log(N) for each query and update.Unless I've misunstood your code.

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

          Thanks every one. i know my wrong now!

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

        • O(log(n2)) = O(2log(n)) = O(log(n)), so there must be something wrong.

        • btw. binary indexed tree or fenwich tree instead of tree array :)

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

Nice problems, really liked them. Damn E, declared the array of 1000 instead of 2000, else I would've gotten AC.

Very nice contest. Congratz to the organizers!

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

Problem B in Div2 was awesome.

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

Very nice problem set,and a very enjoyable contest overall.

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

great contest! great problem! thank you all!

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

Very cool problemset. I really liked D: At first glance I thought it was another Range tree problem. I almost implemented that, but luckily I remembered the author's comment that "all tasks don't require too complicated algorithms" :D

Edit: First time in congratulation list, yay ^_^

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

I will always add X while subtracting two integers modulo X!!!
I will always add X while subtracting two integers modulo X!!!
I will always add X while subtracting two integers modulo X!!!

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

DIV1-C can be solved in O(N), why constraints are so weak?

solution

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

    So that O(N*N) solutions can pass too.

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

      I suppose problem would be more interesting with larger constraints, so well-known derangement problem with n^2 solution shouldn't pass:-)

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

        The O(n) solution is well-known, so smaller constraints wouldn't make it more interesting. Just make the imbalance between people who've seen it and those who didn't worse.

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

Awesome contest ! I loved the problems , they were GREAT . Thank you for this very well made contest :) !!!

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

Thank you authors for the contest!

I'm wondering what was the intended solution in Div 1 C, because one can use inclusion-exclusion principle to get to the answer, which is: ,where K is the number of places i where a[i] = i still can happen and F is the number of free places. Judging from post-contest reaction, most people used DP approach. Thanks to gen for knowing Latex.

Also, does anyone has any tips on Div 1 D without using any king of 2D structures? I believe one could somehow split it in 2 independent parts: rows and columns, but couldn't think of how.

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

    For D div 1:

    First you need to observe that the problem can be solved by using only operations of 2 types: Query(1,1,x,y) and Update(1,1,x,y)

    By observing 4 relative positions of (u,v) to (x,y), you can solve it by using 2D Fenwick tree (which I hope is simple enough) :)

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

      Yeah, maybe it was intended. But I just got a feeling from the pre-round author comments that there is some cool solution with no 2D structures at all. And that the long long as the values was designed to stop the majority of 2D structures from passing.

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

    There is another simple solution. Let n be the number of free cells and k the number of those free cells in which we cannot put values equal to their position, but it can still happen. Let calculate such DP[n][k] = (n — 1) * DP[n — 1][k — 1] + (k — 1) * DP[n — 2][k — 2], if k > 1. DP[n][1] = (n — 1) * (n — 1)!, DP[n][0] = n!. One can see that we should calculate only values with constant difference between n and k, so there are only O(n) states.

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

How it was necessary to solve the problem of B div 2?

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

    You have to fix one diagonal with O(N^2) and then with O(N) find the best points ( the ones that make the biggest area ) to the left and right of the diagonal . Overall complexity is O(N^3).

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

Is there no time limit scaling for slow languages (e.g Python)? Was something like that maybe discussed before on Codeforces? I just timed-out on div1-B using python (finding LIS in nlog(n)), but passed in 0.124 after retyping the code in C++ :(

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

http://codeforces.me/contest/341/submission/4375062

No reversely sorted test case!

3
3 2 1

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

    The set [1] is an independent set alongside [2] and [3].

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

Some whining about the problems follows.

Problem B: it was 100500 times already, it's a shame to reuse this problem again.

Problem C: it is obvious for the ones who remember how to calculate the number of permutations without fixed points (or for the ones who do not hesitate to use Google/Wikipedia during the contest). Again, this problem appeared on a different contests 1050 times. And for the ones who do not remember the solution it is way harder, since they have to reinvent this dynamic programming.

Problem D: it is super-evil, since 2-d segment tree (with time complexity is terribly slow (especially in Java), and 2-d Fenwick tree (with the same time complexity) seems to be the intended solution (at least, everyone got AC with it). Did the authors intend to make a problem with key idea in non-asymptotic optimizations?

Update: another complaint: seems that most of the Java solutions for problem A are easily hackable (with anti-java-sort test). Did not you bother to add such a test? It is very unfair, since one can be hacked with this test, and in the other room the same solution may pass. Anyway, as I understand, general guideline for tests is to kill as much killable solutions as possible, and it seems to be violated.

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

    If somebody had been successfully hacked by such a test then it would have been added to final system tests.

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

      As I know, there is no automatic adding of successful hacks to system tests on codeforces (unlike topcoder). And adding the tests selectively is even worse (e.g. see this).

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

        Exactly in that contest I was the victim of a successful hack added to the system tests. The successful hack made by Arti1990 was added as a test 52 to the final tests of problem C.

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

          Ouch, this probably means that tests are still manually added during contest despite the discussion initiated by Petr. Too bad :(

          Anyway, IMO problem authors should not depend on this and at least try to prepair strong tests before the contest.

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

            Sorry, maybe my previous post wasn't clear enough. Exactly in that contest which you pointed in your previous post (Round 172) the successful hack was added to the system tests.

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

              Ah, I see, thanks for the clarification. IMO is would be better just to automatically add all successful hacks to systest, but it can explode testing time as a drawback.

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

It is strange that there is no warning like this in task D:

"Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier."

And I forget to use long long but passed pretest. :(

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

    %lld works now in all C++ compilers used on CF

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

      Hmm..then why not to remove this annoying time-consuming message that appears after submitting llds? Time, especially at the beginning of contest, is really significant for wasting it on reading unnecessary warnings.

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

I submitted the following code for A: http://codeforces.me/contest/341/submission/4374002 and got WA on pretest 1, with checker saying it received 0 instead of 22. Could anyone explain me why did my code print 0? On my laptop it prints 22, both with "%lld" and "%I64d". The logical part of the code is OK, as I got AC after simply deleting some macros and unnecessary #include's (code http://codeforces.me/contest/341/submission/4376745).

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

Can somebody tell me why this code ( http://codeforces.me/contest/340/submission/4383684) is outputting 10 3 ,it is giving 22 3 on my laptop.

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

    Try to compile your solution with -O3 option

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

      no change in output , but what is wrong in the code ?

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

      Ideone also giving correct output : http://ideone.com/py5h0L

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

        Try reading and writing with streams (ifstream, ofstream, etc..). If you want where you got that 10 you can also try to print ar as the answer and see what codeforces tells you

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

    I've replaced #define LL long long with this:

    typedef long long X;
#define LL X

    And now it gives 22 3

    http://codeforces.me/contest/340/submission/4383966

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

      yeah that worked! How can this create any difference :-o ?

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

        I used g++ -O2 main.cpp -S -fverbose-asm to get the assembly codes and it turns out that the var ans is not in it while it is in if using g++ main.cpp -S -fverbose-asm.

        I found that this code when compiled with -O3 will output 10 (g++4.6.2). So it must be a bug in the compiler.

        #include<stdio.h>

long long ar[3]={2,3,5};
long long ss,ans,num;
int i;

int main(){
    for(i=0;i<3;i++){
        ans += ((ar[i]*i) - ss);
        ss += ar[i];
    }
    num = ss + 2*ans;
    printf("%I64d\n",num);
    return 0;
}

        After reading the assembly codes, I found it ran like this:

        ar={2,3,5}
ss=ans=num=i=0
ss'=ss
ss+=ar[0]
ss+=ar[1]
ss+=ar[2]
ans-=ss'
ss'*=2
ans-=ss'
i=3
tmp=ans*2
tmp+=ss
num=tmp
print num
        → Reply
»
11 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Looks that was a great contest!! unfortunately I missed it...

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

I find that i cannot view any problem. when i click the problem title, the web give the alert telling me "can't find or parse problem descriptor". I know nothing about the exception, and anyone can give me the answer or one solution?? Thanks!!

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

What's the meaning when I got a "Hacked"? Ps:I am a beginner!!

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

Very interesting round and thanks for challenging problems !

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

    Yes! that was interesting ! thanks for problems :)

    → Reply