wilcot's blog

Codeforces Round #344 (Div. 2)
By wilcot, history, 9 years ago, translation, In English

Hello, Codeforces!

My name is Ivan Udovin, and I would like to say, that the Codeforces Round #344 will be held on Thursday (March 3, 2016 at 19:35). This is our first round, but it doesn’t mean that problems will be boring and not interesting. The problemsetters of this round are me (wilcot) and Ilya Kheifets (xfce8888). Thanks a lot to Alex Vistyazh (netman) and unknown person (he don’t want to be added in the announcement) for testing our round. Also I’d like to thank Fedor Korobeynikov (Mediocrity) for his awesome idea for task E.

We thank Gleb Evstropov (GlebsHP) for his help in preparing the contest, Maria Belova (Delinur) for translating the statements into English, and, of course, Codeforces team and Mike Mirzayanov for unique Codeforces and Polygon platforms.

This round consists of five problems. Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others.

Scoring distribution: 500, 1000, 1500, 2000, 2500.

Good luck, have fun.

PS. Editorial is ready.

PPS. Congratulations to the winners:

Div. 2:

  1. lovelive

  2. Murtazo.Ali

  3. chychmek

  4. chrome

  5. Batman

Div. 1:

  1. Um_nik

  2. chffy

  3. natsugiri

  4. ershov.stanislav

  5. AndreiNet

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

Comments Comments (185)
| Write comment?
»
9 years ago, # |
  Vote: I like it -16 Vote: I do not like it

I miss a normal codeforces round. I think this one will be interesting. Good luck to everyone.

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

There is a small typo in the article — while the article says Wednesday, the actual round takes place on Thursday. Could you fix it please?

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

A new round, and an new hope to become expert ^_^

→ Reply
»
9 years ago, # |
← Rev. 4   Vote: I like it -26 Vote: I do not like it
and unknown person (he don’t want to be added in the announcement)

but it is important to know who tested a round for us. Generally, a round won't be interesting if people see it was tested by a newbie, but higher ratings can draw more attentions, right? So, at least writing the tester's rating can be useful here. Alternatives,

Thanks a lot to Alex Vistyazh (netman) and an International Master (who don’t want to be ...

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

nice short announcement. waiting for an interesting problem-set and best of luck for your first round.

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

    thank you my good friend, wish you all the best!!!! may the best coder win

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

    why so many downvote on this comment :o

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

      It is inertia. If it happens so that the first person downvotes the comment, the others are inclined to do the same. It is also true if the comment gets upvoted first.

      This psychological phenomenon clearly manifests itself here and on other internet platforms where people can see how others vote. It is highly exploited in the real life, for example, in advertising or presidential campaigns.

      By the way, if you are interested, it is one of the many cognitive biases :).

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

expert next goal

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

    How long did it take you to become a specialist?

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

      you can check his profile if you are interested to know

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

Codeforces Round #344 (Div. 2)

Why do they always add Codeforces before the round? Who doesn't know this much? Or maybe its just a safety measure to stop people from asking questions like Will the round be conducted on Codeforces? In that case, you can change the heading to Rated Codeforces Round #344 (Div. 2)

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

    Did Codeforces Round mean conducted on Codeforces? How about previous round such as 8VC Venture Cup 2016? No Codeforces stuff in its round name.

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

      Pretty sure about the fact that every Codeforces Round #xxx type of round has been conducted on Codeforces so far, not exclusively though, like 8VC,Manthan,etc.

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

        Supposedly, it means that the round was mostly concluded with the support of Codeforces staff, than some other company (like VK Cup, AIM Tech, etc.) hence, they add "Codeforces" before the name of the round.

        And by support of Codeforces staff, I don't mean just the Polygon system, I mean the help of translators (Delinur) and other outside help (Zlobober RIP GlebsHP)

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

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

"Main heroes of this round: Blake — the owner of the "Blake Technologies" company, and Chris — an employee of this company, and others." I think there is tree problem :3 , the root of the tree is Blake and Chris is one of the leafs :D . it will be so interesting if that's true :D .

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

    What is the theory behind this?

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

    Problems will be like As Blake is the CEO, he doesn't have time to solve this problem because he has bigger problems to solve, so he asks Chris

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

No dynamic scoring please -_- Hope to see some interesting problems with good problem statement :D

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

    Don't worry, usually standard CF rounds don't use dynamic scoring.

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

Only in my device Google Chrome didn't open or brake Codeforses(last 30 minute)?

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

I might be the only contestant who got hacked on A. RIP :D

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

Interesting problemset!

Can someone describe me solution for the fifth task ?

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

    All I've came to:

    You need to maximize value sum(A[j], A[j + 1], ..., A[i — 1]) — A[j](i — j) if i > j. Or value A[i] * (j — i) — sum(A[i + 1], A[i + 2], ..., A[j]) if i < j.

    And print initialy characteristic + (diff > 0 ? diff : 0)

    How to do this faster than O(n^2) I can't get:D

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

      Then I supposed we will iterate over all i and find index j with maximum value j*A[i]-sum[j] where sum[j] denoting sum of first j elements for j>i. Similar way for i<j. But that again wasn't enough for anything faster :D

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

        Yep, that's right. Here you can find how to do that in time with O(n) preprocessing time.

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

          lol, some time ago I've tried understand this, but without success. Maybe now I'll come to success. Thanks for link)

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

          Thanks. I heard for it normally, but I have never used it. I must learn several optimisations :)

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

    We iterate the array. For ith index we will find the best position j, left to the i (it could be right instead of left, but we will compute the right in another iteration), which maximizes (this equals to change of the value of the array when we move jth element to ith position).

    As I said before we do the same thing (almost the same thing, equations are little different of course) for right. Then, the answer is the value of the original array + max(0, max of all changes).

    To find the best j for a particular i, we need to fiddle with the equations a little and represent every element as a linear line:

    ps[0] =  - ar[0]

    ps[i] = ps[i - 1] - ar[i]

    max1 ≤ j < i{ps[i] - ps[j] - ar[j] * j + ar[j] * i} = ps[i] + max1 ≤ j < i{( - ps[j] - ar[j] * j) + ar[j] * i}

    Now we can represent ith element as a linear line. ith line equals to y = ar[i] * x + ( - ps[i] - ar[i] * i).

    We first add the line 1. We then start iterating from index 2. When we're done with i (computed the result for it), we add the line i to our structure.

    (To find the result for that position) When we're at a new position, let's again call it as i, we find the line which has the highest value for x = i. We also need to increase this value by ps[i].

    To find the best line, we can use the convex hull trick on a segment tree, since slopes aren't non-decreasing like in the case of traditional convex hull trick.

    Time complexity: O(NlogN)

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

I swear, in next few CF rounds I will not hack! :(

How to solve C? I guess we have to sort three values i, ti and ri according to ri? How to do the same?

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

    I did it with segment tree+two pointer. Phew! Lot of confusing code

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

      I thought of solving the problem like this. Find maximum value of ri and it's position in input. Then all sortings done before this input will be useless. After this input, check for next largest value of ri and repeat this process. Obviously after finding ri we have to do something in array(I still need to find out more).

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

        I thought along the same lines but this would fail for worst case as in: 

        1 10
2 9
1 8
2 7
1 6
        → Reply
        • »
          »
          »
          »
          »
          9 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yea i thought of that case too but i think we can do something between finding next ri. Like if we say for t1=1, r1=10 and t2=2, r2=8 then we can say from 1 to 8 array is descending and from n=9 to 10 array is ascending. Now we choose numbers in array. I think it can be done nikitosoleil method(two arrays). I am not sure.

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

      My solution is much more easier. I have two sorted arrays (increasing and decreasing order) and taking a look only at elements, that had changed their position. For every position I store will it be sorted at last time int dec or inc order. In first case I am placing in this position first unused element from dec array, in another case first from inc arr. You can take a look at my submission: 16494098 for better understading me. Hope that this will work. P.S. It was the first time when I have submitted three problems less than in one hour :) UPD: Failed. UPD2: Bugged code, but right idea. Some little changes and AC: 16501782

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

        Damn! Ofcourse! Since we are only looking on right side of the segment for maximum, I could've simply done a suffix-sum calculation in O(M) lol

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

        No wonder you were expert. :) Sometimes contest go bad, very bad. :(

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

          In this and two contests before I have done stupid mistakes in one problem, but on the previous contest I have done stupid mistakes in all problems)

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

    What I did:

    Found the maximum number of sorted elements from all queries, from 0 to x

    Sorted [0,x]

    Then from that query looped to the end of the queires reversing the array from 0 to query's length, keeping track of what order was used last time. If the order changed, then reversed the array, otherwise did nothing.

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

      I think your solutions fails for this test : in

      I have hacked a similar solution with this test.

      N = 200000
K = 200000
print N, K
for i in xrange(N):
   print i + 1,
print
for i in xrange(K):
   if(i % 2 == 0):
      print 1, N — i
   else:
      print 2, N — i
      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      I won't know until system tests are over, but I did the following: EDIT: Failed on test 13. I think the main idea is correct though, so check the last paragraph.

      1. If there are n numbers, create an array of size n (orderings) of integers, initialized at 0.

      2. Read input numbers and put them in a linked list. Create empty stack too.

      3. Read managers. For each manager, set orderings[r] = t (1 or 2).

      4. Set sorted = false. For i = n — 1 until 0:

      4.1. if (ordering[i] != 0 && !sorted) list.sort(), sorted = true;

      4.2. if ordering[i] == 1: pop from the left of the list and push to stack.

      4.3. else: pop from the right and push to stack.

      1. Pop from the stack and print until empty.

      It's not exactly that, because when ordering is 0 you have to look at the last order, unless no sort has been performed yet.

      I'm not sure about whether it's right or left for orderings 1 or 2, because I don't remember which one was nonascending/descending, nor the default order of list.sort(). But when ordering is 0 you always pop from the right (if no sort has been done yet, else you follow the previous left-right rule).

      The idea is that if the largest sort is n — k elements, the last k are in the initial order. From there, the n — k — 1 indexed element is the biggest/smallest number left (depending on the direction of the last sort of that size), the list is reduced in each step this way, until you get to the empty string.

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

    I simply took maximums of type_1 query and type_2 query except for the last query, if in case last query is for type_1 then i first sorted max(type_2) in non-descending order and then sorted max(type_1) in non ascending order,and vice versa for the type_2 query in the last query. hope it works... :)

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

Somebody know why KMP on problem D might give WA14? And how did you solve that problem? I thought of KMP, but now I see that I could use hashing also.

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

Wow C has 1k submissions!! It took me lot of time to code C

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

    I think a lot of them would fail System Test

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

    From your earlier comment it seems that your solution is more complicated that it needs to be.

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

So, what was the hack cases for A and B?

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

    I tried to hack for int overflow in A. But I am stupid there will be no int overflow. In B, I tried hacking TLE submissions but i failed! :(

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

      There can be overflow Input 1 536870911 536870911

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

        Only if you've used short int datatype, or char, or bool ;)

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

        Answer is 1,073,741,822.

        Answer fits in int.

        There will be no overflow because input is restricted till 2^29 and if we 'OR' all powers of 2 from 1 to 2^29 we will get 2^30 — 1. Then adding we will get 2^31 — 2 which fits in int range.

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

        536870911 + 536870911 is almost twice less than 231.

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

    B: If you update the grid after each operation, worst-case complexity is O(k * max(n, m)).

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

      Ah I see. I thought there is some tricky case...

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

Second problem with O(k*n) k = 100000 n = 5000 failed in hacking. So fast...

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

    Same there:D

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

    i was able to hack with this test case

    cout << 5000 << ' ' << 20 << ' ' << 100000 << endl;
forall(i,0,100000){
	cout << 2 << ' ' << 2 << ' ' << 2 << endl;
}
    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it

      WHAT ? :|

          long long int n, k, d, i, j, ans, currA, currB;

    cout << "5000 1 100000\n";
    for (i = 0; i < 100000; i++)
    {
        cout << "2 1 10\n";
    }

      This gave me unsuccessful hacking attempt :\

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
        ← Rev. 2   Vote: I like it +6 Vote: I do not like it 
        cout << 20 << " " << 5000 << " " << 100000 << endl;
    for(int i = 0 ; i < 100000; i++){
    	cout << 1 << " " << 1 << " " << 1 << endl;
}

        `

        why is this unsuccessful on bruteforce

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

          Operation 1 is much faster than 2. (memory access time)

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

            Even operation 2 doesn't seems to work atleast for me. Here's the solution i was trying to hack: http://codeforces.me/contest/631/submission/16492474

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

              The submission used long long int b[n][m]; so the memory is contiguous. (especially you specified m = 1)

              Had it be b[5000][5000] your hack would be successful.

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

                Yes i think you are right. Others are doing this with m=5000 n=20 to fit into n*m <= 10**5

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

        codeforces' server is very fast

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

        Same here, I didn't get it. Wasted 30 min learning how to hack with generated input and trying to understand why it didn't work, and I in the end I just got some negative points.

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

      I did exactly the same except of this

      cout << 2 << ' ' << 2 << ' ' << 2 << endl;

      I wrote

      cout << 1 << ' ' << 1 << ' ' << 2 << endl;

      But if i remember correctly for k=100000, it gave input data size was too large.

      So i used k=10000

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

        i choose 2 so that there will be cache problems with array

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

          How was your input size less than 256bytes for k=100000?

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

            You should use generator program for test case for large inputs.

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

            You can write a generator program instead of manual input. That's the second tab of the pop up window after you click the "Hack" button"

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

              Facepalm! I could have hacked atleast 2-3 submissions in my room.

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

    I hacked 8 solution in n=5000 k = 100000 case :)

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

      In my case it was not accepting n=5000 k=100000 due to large input size!

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

    Good estimation is 10^9 ops per second (from my experience).

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

      for Python also?

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

        No, python is much slower (from my testing 40 times slower) and I don't recommend it as a programming language for contests.

        10^9 is a good estimation for C++, C# and Java.

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

noticed my solution for B is wrong after locking it , so hacked 10 people :p

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

    What's that special test case that failed 10 solutions?? o.O

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

      TLE probably. I did an analysis sometime back, and I concluded that codeforces can compute approx 2.7x10^8 trivial instructions(assignment,increment, arithmetic +/-,stuff like) that in 1 sec. Anything more than that is TLE, and if somebody had 10^9 instructions/sec pass then compiler probably optimized something.

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

I wonder what was test 7 for problem D. I really can't figure out what was wrong in my solution... anyway, if A, B, and C all pass, it will still be a good result. :)

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

    May be something like this:

    3 3 3-a 2-b 3-a 1-a 2-b 2-a

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

      Is the answer 1 ? I guess so...

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

      I saw the test. Actually, my implementation of KMP algorithm was wrong. :'(

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

How to solve C?

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

    Let's assume we have instruction 1-n. Everything before that instruction doesn't matter. So let's find the last instruction 1/2 — n. If that doesn't exist the number stays the same, if it does we have to take the smallest or the largest number in the array. After that we search for 1/2 (n-1) that is after our previous instruction and do the same process, but we also have to remember what was the last instruction that was made(if it was 1 or 2 so we know what number do we have to search for). We can sort the instructions and also use the set to get maximum/minimum and to remove elements(after we have used them already) so the complexity is O( (n+m) (log n + log m))

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

      What if there are consecutive instructions like for n = 10 1 10 2 9 1 8 2 7 1 6 2 5 1 4 2 3 1 2 1 1 this will sort the array 10 times right?

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

        After the first instruction we know, that result[10] is equal to biggest number in array, and it won't change, after the second one we know that result[9] is equal to smallest number in array without the biggest number — so smallest number, after third we know, that result[8] is equal to the biggest number in array without biggest and smallest number etc, you don't need to sort it every time

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

At first I read OR as XOR in A. Anybody else coded for XOR lol

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

    Give me five!) It taken 10 minutes to understand why WA2

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

      I was confident about my code so I immediately went to check the problem statement. Wasted 8 minutes coding for XOR lol.

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

        I've got sillier case: coded for 1-2 minutes, but couldn't get my mistake for 10 minutes)

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

        Same here! Although I didn't wasted 8 minutes coding for XOR because then I just changed XOR to OR. I let it be O(n*n) rather than changing to O(n).

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

    Me too :)

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

    I did it initially. But soon I could realize when sample test cases didn't pass on my local machine

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

    SunitSwn

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

    Lol same here. i even submitted the solution with an O(n**2) solution, but luckily it failed in pretest 1 only :P

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

      My XOR even passed first five tests. No idea why. I got -50 because of this. :( Here's my solution Link

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

        Ohh, now i recall that what i stated above happened to me on problem 2. The first one gave me ans as 42 with xor which i spotted before submitting. Yours passed pretests 2 too because you are taking max sum of xor of (A[i..j] + B[l..k]) where [i..j] may or may not be equal to [l..k]. It had to be equal according to problem statement.

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

    Yes. I even asked an official clarification question so everybody can permanently see in the problem history how dumb I was.

    Official answer was "There is no XOR. There is only OR. You are a fool."

    (Part of it was not written but clearly implied).

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

      I didn't know this problem history feature until you mentioned it.

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

      What?

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

        Oh dear I didn't mean to insult the problem setters, I was totally joking!

        Your message was of course not rude at all. But my question DESERVED a rude reply, that's what my "joke" meant. I sure hope you at least THOUGHT it was a dumb question, because it was. :-)

        Anyway, I loved the problem set. A and B were perfect difficulty but even after solving them the editorial showed a much better solution for A by thinking a little bit about the data instead of blindly coding, so it was a great lesson. And C was very doable, another excellent learning problem. Thank you!

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

    Same!

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

problem A can't hack in n^3

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

I hope there will be me many TLE on problem A and B after system testing.

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

So, maybe authors could comment why they picked so tight input limits on problem B? Basically what I don't like about this — brute-force solution wasn't cut.

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

    I too was disappointed. May be n.m <= 100000 should be alright. Why n,m <= 5000?

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

    This was done to ensure that the solution should pass on a Python.

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

very nice problems and I enjoyed... I understood u love optimizing algorithms a lot :)) tanQ guys :)

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

wanted to act like an expert and went for C first without even looking at A and B. Spent too much time on C and could not submit B :v Looks like my being blue was just a fluke. I am not ready yet :v

And , as a result, today I will go back down to my rightful place. How the heck people solve problem like C in 20 minutes -_- . My brain feels dizzy after 1:15 hours of non-stop storming on C :/

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

    I don't think it is a good idea to go for C+ right away if you are below like red or something.

    But it is a good idea after solving first easy tasks (A, B and sometimes C) to read all others.

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

      no, I know it takes something special to start right away from D or E. But C is kinda different to me. To solve C, you only need to be proficient in some basic algos. Whereas D and E often requires expertise on some special algos too. (Of course, we have seen exceptions in past contests where C was quite hard too, but i am just expressing the general scenario)

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

    I only read C first in rounds which have both div 1 and div 2. For rounds with div 2 only like this, C is usually harder.

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

      Isn't it the other way round?

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

        By "rounds which have both div 1 and div 2" I mean rounds that have 2 separate contests, one for div 1 and the other for div 2 :P

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

      so according to you today's C was hard? :v

      That's kinda good to know. If I heard I had wasted 90 mins to solve an easy problem, it would be devastating

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

    and after the system test, a lot of people failed on C which I passed. If only my brain worked 1 min faster :/ I just had to submit B (even the code was complete) :/

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

I thought 5*10^8 operations can be done in 1 sec :(

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

codeforce i want to say thank you !!!! such a interesting question and help full for improve my coding skills. again thank you.

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

    without submitting a solution?

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

absolutely loved this contest, waiting for the next contest from wilcot and xfce8888

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

Wow i thought i flunked this contest but rank went from 1.8k to 1.3k. I guess my rating will go down by only few points.

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

It feels bad when you fail something you spent 1:20 hrs on ;_;

Curse of the tourist. Never make fun of tourist ;_;

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

TLE in PyPy (16491742) and AC in Python (16500293) with exact same code. :|

Isn't PyPy supposed to be faster? Also, aren't Python/PyPy time limits supposed to be 5x that of default time limits?

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

    As I know on codeforces time limits are the same for all programming languages.

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

Oh :-( Overflow... :-(

http://codeforces.me/contest/631/submission/16496133 vs http://codeforces.me/contest/631/submission/16500541

Overflow doesn't allow me to get AC from all of the problems of this contest. :-(

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

When will we see the rating change?

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

Auto comment: topic has been updated by wilcot (previous revision, new revision, compare).

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

Can the Div. 2 D be solved using KMP? My approach was like I would compress multiple characters to single character and form a string. Then I'd use KMP to find the matching between the two. I keep tract of (l, c) pairs. I know their frequency and where they match. With this much information please help me find the answer. My code : http://ideone.com/yb5JCW

Thanks in advance.

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

It was a really nice problemset. Thanks!

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

I think there is a little problem. I solved two problems, you can check it in the standings (465th).

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

10 days without contests?

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

    New contests could be announced in between.

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

Congratulations..

contest was be very interesting. especially the last question is very interesting :) but I can not solve this in contest )

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

How to sort 2d array according to first column? I know how to do it for 2 columns(using pairs) but how to do it when columns are more than 2?

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

    Creating a custom struct/tuples with custom sort function or pair< int, pair<int, int> > should work

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

    you can use vector of vectors :-)

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

how many operations the codeforces server do in one second? ◉_◉

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

    What the hell man? Why did you stole my pic?

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

      I think that you stole my pic

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

        I think that you both are liers. It's my face on your avatars. Please ban.

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

anyone on how to solve c? i sorted queries on basis of ri>rj and implemented sorts while skipping ones with ri<r(i-1)&& i<j. some people solved it with segment tress . please explain it?

thanks_in_advance

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

    You solution has complexity. I suggest you read an editorial.

    → Reply