ikatanic's blog

COCI Round 2 Season 14/15
By ikatanic, 9 years ago, In English

Join us on Saturday, November 8th, 2014 for the second round of COCI!

Click here to see when the coding begins in your timezone!

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

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

why it appears " Comments (3)" ,but there is nothing in comment(of course not count this), is this a bug or comments are deleted?

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

Could you upload the contest to gym after it's over?

I really enjoy your contests, but the time is usually unsuitable for me :(

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

    That's a good idea. I'll see if it is possible.

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

thank for informing...i joined it

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

Oof. Got everything, but with over 9000 bugs, most likely. I had to rewrite some codes from scratch because I didn't read some clarifications until late in the contest...

For the hardest problem, I used divide and conquer with BIT in .

Also, (now correct) codes: MOBITEL UTRKA STUDENTSKO BOB SUMA NORMA.

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

    How did you solve C?

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

      Compress the numbers into a permutation of 0..N - 1. Then, divide them all by K. You're left with sorting this sequence in as few steps as possible, which has been in CF before — you just need to sort the complement of the longest non-decreasing sequence. Can be done in , but O(N2) is sufficient here.

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

    Nice, it's also possible to solve the problem using divide and conquer in O(N log N). And there is data structure + sweepline solution in O(N log N).

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

    Can you explain norma (6th problem) in more details, please?

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

      Sure. It's probably clear that the divide and conquer solution splits an array into 2 of equal halves, recurses into the 2 halves and adds the sum for sequences that are formed by merging parts of both halves; the key is in doing that merge.

      We can list all prefixes of the right half and suffixes of the left one as triples (min, max, len). If the left part contains the minimum (equal minima also fall under this case), we can sort them by min and iterate over non-increasing min while adding right parts whose min is  >  = . Now, another fork comes: the max of the left half can be larger or smaller than that of the right one. In the first case, we need the sum of minlmaxr(lenl + lenr) for maxr > maxl; in the second one, the sum of minlmaxl(lenl + lenr) for maxr ≤ maxl. We just need to compute the sums of 4 values in 4 BITS for that and evaluate the sums of each of these 4 terms from them for fixed l. The case minl > minr is very similar.

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

        Thanks!

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

        is this approach correct? we first sort our array first we say that dp[i] = minimal*L of the subsequences which ends with i which is sumdp[i-1](sum of dp[0] till dp[i-1]) + 2^i-2*arr[0] + 2^i-3*arr[1] ... + 2^0*arr[i-1] + arr[i](for the alone arr[i]) which we save this amount in sum and we do sum=sum*2+arr[i] and then at the end we multiply dp[i] by arr[i] and add it to our final answer
        Edit: it is incorrect but it can be solved like this

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

    How much points did you got from last problem?

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

lol,I solve problem D,E but I can't solve C still,can someone help ?

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

    How to solve D?

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

      you need to construct for each i row array b: where b[i][j] means maximum k that a[(i-k,i)][j]=1 then you can easly find: how many rectangles ends in (i,j) point. sorry i know my english is bad (( so you can check my code http://pastebin.com/YGgehUFM

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

        How many point you got ?! I'll bet that it's not more than 50 point!

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

          He got 0 :)

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

            Why do you think so? and what's your solution?

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

              I solved it using DSU + Sweepline! (I think it must have an easier solution)...

              My Code

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

                Can you explain your solution in details?

                your function "solve" can be called O(nm) times every time it is called it calls the sort function which has complexity O(n log n) so how is your solution is the fast?

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

                  lets say X is size of vector v.

                  every time I call solve function it is O(X.log X), and we know there will be n.m object in vector v. so my algorithm comlpexity is O(n.m.log n)

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

              I found his name at scoreboard and saw his points for problem D. I wrote N^3 solution and got 70 points.

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

          yes all of you are right, my solution was incorrect,but its near to correct solution,here i will explain correct solution you can see:

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

O(N(logN)2) for hardest problem deserves better then %50, isnt it?

EDIT: it seems my implementation was bad, since there is full score with same solution.

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

Is it possible to solve D problem with DP? I got 24 points using DP. I knew it was wrong but I tried to get some points.

This is what I tried:

t[i][j] -> Value at row i and column j.

dp[i][j] -> Amount of rectangles ending at row i and column j.

row[i][j] -> Amount of the last consecutive equal values ending at column j in row i.

col[i][j] -> Amount of the last consecutive equal values ending at row i in column j.

Then:

dp[i][j] = 1 + dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + (t[i][j] =  = t[i][j - 1]?row[i][j - 1]: 0) + (t[i][j] =  = t[i - 1][j]?col[i - 1][j]: 0 + (t[i][j] =  = t[i - 1][j]&&t[i][j] =  = t[i][j - 1]&&t[i][j] =  = t[i - 1][j - 1]?X: 0))

I can't get the value X in this dp.

Is this a correct approach to this problem or am I completely wrong? If somebody solved this problem using DP I will thank if he/she explains the approach. Thanks in advance.

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

    I think there is no O(NM) DP solution. Problems of this type have a standard solution using stack that can be slightly modified to compute what you need.

    → Reply