DBradac's blog

COCI 2016/2017 round 6
By DBradac, history, 8 years ago, In English

Join us today on the 6th round of this year's COCI!

Click to see where the coding begins in your timezone.

We can discuss the problems here after the contest.

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

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

Why the main site isn't working ? UPD : Fixed now

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

How to solve 140?

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

    Edit: wrong algorithm. It's actually possible to end up with a cycle.

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

      Not 100% sure but can you explain how your idea works on something like 2 3 6 where it's optimal to choose edge 2-6 and 3-6 wouldn't your idea only consider edge 2-3 instead??

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

        No, I'd incrase cnt[6] 3 times, so 6 would find an edge with 2*3 and cost 0, and then with 3*2 and also cost 0.

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

When the results will be published?

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

    Currently there is a backlog of submissions waiting to be judged.
    Results will be published when the submission queue is empty.
    That will take approximately 1h.

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

    I think that in less of a half hour, because in the judge, them published this:

    "Currently there is a backlog of submissions waiting to be judged. Results will be published when the submission queue is empty. That will take approximately 1h."

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

It seems that the problemsetter likes the sieve of Eratosthenes.

How to solve the last problem?

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

    120 can solved by prime factorization yes?

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

    My solution is not that fast, but whatever...

    Calculate DP[i][j] = min cost to make number j to number 1, by i step of operation (no lucky number). This takes O(maxA * lg(maxA) ^ 2) time.

    for each query from a to b, we use at most one lucky number when making a move. With that observation, we can reduce each Q * M queries as a minimum y-intercept at position L_i, which can be solved with CHT.

    This whole operation takes O(maxA * lg(maxA)^2 + QM + QT * lg(maxA)^2 ). It runs under 1.21s in analysis mode. code (In the contest it got 0 points because my code was quite bugged)

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

How to solve 100? My algorithm is: count elements which equal or less than arr[i], then print log2(cnt+1). I could do it in O(n) time, but I started 1 hour late, so I did in O(n2). But I don't know if my solution is correct or not.

Sorry for bad English.

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

    It should be log2(cnt). Also you can calculate cnt by sorting.

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

      If you are counting arr[i] too, then log2(cnt)

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

RESULTS ARE OUT NOW!!

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

LOOOOOOOOOL! First place :D, how could it be?
Achievement unlocked :P
I think tests for fifth are weak.

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

    How did you solve it then?

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

      Code

      For N ≤ 104 I did Prim's O(N2) algo (for safety) and for bigger I just connected all components (via DSU) with edges of cost 0, then with edges of cost 1, ... until the graph gets connected. :P Look at the code.

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

        Can someone create an anti-test?

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

          As your array size of bool e[] was too small (M + 9 which is 107 + 9), it is quite easy to hack your solution with a case that the maximum weight of an edge in the MST is greater than 10, your solution may connect some incorrect vertices like 107 + 13 as e[j + r] may return TRUE for j + r is greater than your array size.

          Meanwhile, I originally want to make your solution TLE on some cases instead of WA, so i change your array size of bool e[] to M + M which is sufficient.

          Finally, your code will TLE in cases that number of unique elements is greater than 104, and the weight of an edge in the MST is quite large, as the time complexity of your solution is .

          For instance, your code will TLE on this case:

          100000
9999999
7999999
5000000
4999999
.
.
4900003

          Anyway, i found it not easy to create such a case that your code(assuming the problem of illegal access to array is fixed) will TLE. But, I think the official data set does not contain any max cases with big is quite disappointing.

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

            Yeah, I got TL on your test. :P I thought that tests maybe weak and not include such test. :D

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

Hello, I need you help guys Please give any ideas how could this code for C problem and this code for B problem

get SIGSEV on some of the tests??! I am just sick of getting this verdict, I get it almost every contest!

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

    In the code for problem C, you have a bad limit, because you have maxn = 500009 instead of maxn = 1048576, that is 2^20.

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

      Thank you. What can you say about the B problem? Does seg tree require limit of N*4? I thought N*3 is more than enough..

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

      Even though, it won't pass. Cause, utilizing map here takes more memory than intended. He should remove his map and use another way to compress.

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

        I sent the code with the correct limit, and it works perfectly.

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

    For problem B, change the size of s array by maxn*5 and get AC. I know, that's sad :'( Maybe with maxn*4 also works

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

      maxn*4 is enough.

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

        Guys, can anyone prove that N*3 is not enough? Because, in one tutorial, I have read, that N*2 is already enough (it wasn't seg tree built by loop, it was the same reqursive aproach..)

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

          see

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

          I think that for find a correct limit you need to know that the Segment Tree will have a height of , now you know that for every level in the Segment Tree the number of nodes is equal to , then the total nodes in the Tree is .

          See this link

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

    There's actually a really good implementation of segment tree that uses 2*N memory: click. It's iterative, and therefore much faster than the recursion based segment tree. There are some problems where recursive segment trees are required. However, this should work on most problems.

    For this problem you actually didn't need segment tree. There exists a very simple greedy solution (< 15 lines lol).

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

I'd like to share my (approximately) O(N) solution to 120

http://pastebin.com/n0eXg04q

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

Will there be any editorial ?

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

That feeling when one if costs you 120 points... and 11th place. I feel dumb anyways since I didn't use a basic Sieve of Eratosthenes in D, what I did was for every number in the interval I used logN prime factorization and used the formula f(N) = product of f(p^i) where p is every prime factor, and i is its exponent. f(p^i) can be calculated in logarithmic time, so the algorithm is about O(NlogN). (the solution passed in under 1s in analysis mode)

Code

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

    My approach was the same as yours. After reading pllk's solution I also feel extremely stupid.

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

How to solve E?

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

    I used DSU to group the elements and applied greedy approach to find the minimum result.

    First group all the elements by finding whose modulus gives 0, then go for 1,then 2 and so on.. till you have grouped all.

    My Code

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

      Weak tests or there is some legit proof that this works fast?

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

      Won't your code TLE on this case?

      100000
9999999
7999999
5000000
4999999
.
.
4900003

      UPD By submitting your code and the input to http://evaluator.hsin.hr/, your code results in TLE:

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

I have a solution for problem Sirni that can solve up to Subtask 3 (n ≤ 105, p ≤ 106), but I don't know how to deal with p ≤ 107.

First, remove all duplicate from array P. Then, call nextx the index of the smallest number in P that is larger than or equal to x.

Now, consider index i. For each integer k, let m = kPi, we will only add the edge (i, nextm). Finally, we build the MST for the graph.

Why we can ignore all edge that connect index i and all index a1, a2, ..., ak such that Pnextm + 1 ≤ Pa1 ≤ Pa2 ≤ ... ≤ Pak ≤ m + Pi - 1? Because, the algorithm will eventually add edge (nextm;a1), (a1, a2), (a2, a3), ..., (ak - 1, ak). So, for each j in [1;k], instead of using edge (i;aj) with cost Paj - m, we can use edges (i;nextm), (nextm;a1), (a1, a2), ..., (aj - 1, aj) with the same cost and more benefit. So, we only need to consider edge (i, nextm).

The maximum number of edge in the graph is , which is about .

UDP: My code

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

    It's enough to change std::sort to countsort. I've modified your code a bit and it got accepted.

    Modified code

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

    I used the same approach and got AC(worked for p ≤ 107).

    It seems that you're sorting the edges in order to create the MST(please correct me if I'm wrong), this works in which wont work for p ≤ 107, but since the weight of the edges are  ≤ 107, you can create an array of vectors of size 107 and add the edges to the corresponding vector, this way the complexity is .

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

    With counting sort it can get accepted, http://ideone.com/iqBChI

    UPD: Actually, I was bit late :(

    → Reply