DBradac's blog

By DBradac, history, 8 years ago, In English

Join us this Saturday on the 7th 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
  • +53
  • Vote: I do not like it

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

I just tried to register but I'm getting "You're not allowed to log in from this location." Is it not an open contest?

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

    Change the contest from HNOI to COCI.

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

Reminder: less than 2 hours left.

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

I wonder what happened to the author of the second task. Why the footnote is so sarcastically?

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

Firstly, I scared input of 50 :D

»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

The problem statement of second task is so long it's disgraceful.

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

How to solve B (80) problem ?

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

    Look at divisors of 2N.

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

    Hint: sum of l,l+1,...,r-1,r is equal to (l+r)/2.0*(r-l+1)
    try iterating over every possible value of (r-l+1)

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

    You can solve in

    Easy understandable code

    You will understand from that :

    sum of 2 adj. numbers: m + (m + 1) = 2m + 1

    sum of 3 adj. numbers: m + (m + 1) + (m + 2) = 3m + 3

    sum of 4 adj. numbers: m + (m + 1) + (m + 2) + (m + 3) = 4m + 6 .. etc..

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

How to solve C? I used bitmasks for 40pts.

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

    This might be overkill.

    Let's denote the amount of a-s, b-s and c-s Slavko has for some some suffix of Mirko's string as sa, sb, sc. Also denote the amount of a-s, b-s and c-s in the suffix as ma, mb, mc. Then that suffix is solvable with the given letters iff the maximum flow of the following graph is sa + sb + sc:

    Now we can iterate over Mirko's string and choose the lexicographically smallest character so that the remaining string is still solvable with the remaining letters.

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

      huh, at least I'm not the only one who did that :D

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

    Task Igra: implement an O(n) function to answer "is it possible to arrange a valid string if we have (a1, b1, c1) free characters against (a2, b2, c2) already placed characters (notice that a1 + b1 + c1 = a2 + b2 + c2). To do it you can iterate over what part of a1 goes to b2, and then all the rest if fixed and can be checked with some ifs.

    Now you can iterate over each character of answer string and try to place a, then b, then c and check if it is correct. It is O(n2), obviously. By the way, the function is some kind of maxflow, so it can even be solved in nearly constant time, making O(n) operations total.

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

      I tried to fill a2 with b1 and c1 by first giving all the b1 and then c1...another possibility is by giving all c1 and then b1. I generated 8 such possible ways.

      Is it wrong? :/

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

    You can just pick the letter greedily, checking if choosing such letter and you can still have a valid string afterwards.

    e.g. if you choose 'a' at pos i, you need to make sure no. of 'b' in Slavko[i + 1 .. n] <= (a — 1) + c, no. of 'c' in Slavko[i + 1..n] <= (a — 1) + b. you can do this O(1). where a, b, c are the number of letter that Mirko still have.

    So overall time complexity is O(N).

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

      Did you get full score for that approach? Because I did the same and got only 30 points (it is possible that my code has a bug).

»
8 years ago, # |
  Vote: I like it +30 Vote: I do not like it

How to solve 140pts?

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

I wonder why the limits for third task are so small. Isn't there an O(n * alpha^2) solution?

UPD: seems like my solution is wrong

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

    I submitted an O(n^2) solution, but I think that it could be changed slightly to an O(n) one. How did you get an alpha^2 factor?

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

      First alpha for iterating over every character, second alpha for checking if this character can be inserted (if it doesn't make some of the remaining characters unusable)

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

        Oh, I thought that by alpha you meant the inverse Ackermann function

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

how to solve F?

I can solve it only for 64 points with a weird Gauss Elimination but I have no idea how to do it for max.

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

    I didn't solve it (made pretty bad mistake), but I think this is the intended solution.

    The only thing left would be to find σ, which can be done using Knuth-Morris-Pratt.

    So this solution runs in O(M) time.

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

Is it just me or COCI's are becoming harder and harder?

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

    You can look at the scores of people in past contest to compare. Write back if you find something interesting.

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

    I think this contest was harder than usual.

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

    In 5th round I got 434 points, 6th round was 350 points and now I didn't even solve three problems in this round :(

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

    Or maybe the previous rounds this season were easier than usual? At least this is how I feel about it.

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

What's an expected value?

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

    Sum of every possible result divided by the number of these results. If a result can be obtained in two different ways it should be counted twice.
    I haven't read the problem asking for expected value. I'm giving the general meaning

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

      Thanks

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

      That is correct only if all results have equal probability.
      The general definition of expected value is :
      Let's say that there are n results of something with values
      a[1],a[2],..a[n-1],a[n] and the probability of the ith result to appear is p[i], then:
      The expected value=sigma p[i]*a[i]

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

Fourth problem (120) may fail because of recursion?

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

How long does it normally take for COCI results to be final? It's my first time competing in a round.

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

    Like an hour. But initially the results only appear at the evaluator page, it takes a while before they appear at hsin.hr/coci

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

    you can see them now

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

Azret was the first place in 6th round but he scored 130 in this contest. Isn't it weird?

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

I got a solution for problem D that got TLE on 2 last testcases. How can I improve it?

First, treat the scale as a binary tree (left child = left beam, right child = right beam, weight = leaf node). There will be maximumly 3n nodes in this tree.

Call dpu the smallest sum (in binary form) for a balanced subtree in vertex u. Then:

We got a O(n2) solution now. How can we make this faster?

Since dpu is now a string, multiply by 2 also mean add character '0' to the end of the string. So, with careful implementation using pointer, "assigning" value for all dp states will take totally O(n). What about time needed to compare the strings from two children? It's in the worst case (The tree look like an segment tree with value of all leafs equal each other). So we got a solution.

My code

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

    My solution was saving the values and the exponential of two considered that the answer is one of the node * power of 2. This give a linear solution. The last two were hard so I luckily got 12th by solving first 4 problems lol.

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

    Sorry if this is stupid, but how to prove correctness of the DP for an internal(scale) node? I mean if we have scale with children having weights a and b(a ≤ b) we'd have to add b - a weight to the left child, but how do you know that it can be done while maintaining the current balance within that subtree? Wouldn't it be required for b - a to be divisible by 2height where height =  height of the node from the bottom?

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

My solution for D got just 54pts. I think my approach is correct —

For all the weights, I found the wt such for maximum value — w[i]/pow(2,level[i]). Answer is concatenation of binary representation of wt and level of wt times '0'.

also I took care of the fact that level can go upto 10^6.

My Code

Where am I wrong?

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

    Probably handling 106 strings of length 106 is too much. It is better to represent the numbers in the form of a·2b where a is some odd integer.

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

      I didn't made strings of length 10^6. Check my code. I got just 54 pts.

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

      Could you post a link to your solution? Thank you in advance. :)

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

Am I the only one, who thought, that in the 4th problem you are only allowed to add weights to the existing weights (in other words, to the leaves of the tree)? Got only 54 points during the contest because of that and full score in the analysis mode when I decided to leave this assumption alone (and I believe, that my first assumption is way more intuitive).

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

    I assumed that and got 120. You were wrong elsewhere.

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

      What does your solution produce for the following test case?

      2

      2 -5

      -2 -2

      According to my AC solution, the answer is 1010, and according to my failed slution, the answer is 1100

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

      And one more thing: if we assume, that we can only add the weights to the leaves of the tree, the total weight should be divisible by 2treeDepth, which, I believe, is not true for the fifth test in the testset

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

        This is not true. See the first clarification on the message board — you may add any real number to the leaves. In your example, we can add 0.5 to both of the "2" leaves.

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

          Oh, I've missed that clarification. Now it all makes sense: the problem, where you are allowed to put the weights to non-leaf vertices and the problem where you are allowed to add any real number to the leaves are equivalent. Thanks!

»
8 years ago, # |
  Vote: I like it +18 Vote: I do not like it

How to solve the 5th problem?

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

    Sketch of the solution (I am an author of the problem):

    Take any 3 noncolinear points and bring them all to the [5, +inf] x [5, +inf] quadrant of the plane. It can be seen that such series of moves exists if you observe the tiling of the plane by parallelogram generated from those 3 points. Now, you can just use BFS to find shortest series of moves to bring those 3 points to that part of the plane. Since coordinates are small you can check all possibilities and see that in worst case this takes around 1200 moves.

    Last, you can see that after you have points A, B in quadrant [5, +inf] x [5, +inf] you can move any other point C to first quadrant with just one move.

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

Form problem D, it seems like I had to use linear diophantine and solve it using extended euclidean algo but I have no idea was it is an just gave up :(