-is-this-fft-'s blog

By -is-this-fft-, history, 5 years ago, In English

The Baltic Olympiad in Informatics will be held in Tartu, Estonia from April 27 to May 2. Both days of the contest will feature an online mirror contest. We invite you to take part.

Both online mirrors will start one hour after the corresponding onsite contests. Both contests last 5 hours.

Solutions will be accepted in the following programming languages: C++, Java and Python. We have separate time limits for C++/Java and Python. Tasks have IOI-style batched partial scoring. Problem statements will be available in English and a multitude of languages spoken in the participating countries.

Some links:

Let's discuss problems here after the contests!

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

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

Can we solve task Robot from day 0 faster than n^4?

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

    Can you share the tasks? The analysis mode is not operating.

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

      Sadly the only pdfs i have are in polish.

      Robot — you are given a N by M grid, each element can either be a blockade, or have a certain amount of coins on it, we start at position 1,1 and can only move down or to the right. Our goal is to generate a sequence of moves of length at most k, which doesn't pass through any blockades, and goes over as many coins as possible(this sequence gets repeated until we leave the maze). It is guaranteed that there exists a correct sequence that passes over a non-zero number of coins.

      The other two problems were not interesting, and just there for contestants to get used to the grading system.

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

Bump, the onsite contest starts in 10 minutes and the online mirror in 1 hour and 10 minutes. I added scoreboard links to the post.

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

it seems that the online mirror doesn’t work

upd: it's fixed, good luck everyone

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

if anyone has gotten the problem statements, could you please share them?

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

    I can't believe I didn't think of this.

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

How to solve problem 3? I have no idea how to get full score.

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

    Root the tree at E.

    Let x and y be the 2 vertices on the queried edge. You can escape iff at least one of them isn't an ancestor of r, which you can check quickly with binary lifting.

    To find the minimum distance, let dp[i] be the minimal distance to a shop that is in the subtree of i, and let h[i] be the distance from i to the root E. We need to find min(dp[i]-h[i])+h[r], where i is any ancestor of r that is under both x and y. We can find this again with binary lifting.

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

    Take $$$E$$$ as the root of the tree. Suppose the edge $$$(a, b)$$$ was removed, where $$$a$$$ is $$$b$$$'s parent, and you are at node $$$u$$$. You you can reach $$$E$$$ iff $$$b$$$ isn't an ancestor of $$$u$$$ (we can check that by seeing if $$$lca(u, b) \neq b$$$).

    For the case where $$$b$$$ is $$$u$$$'s ancestor, calculate for each vertex $$$v$$$ the distance to the closest shop in his subtree with a dfs and call this value $$$sub(v)$$$. Now, the answer to the query will be $$$min(dist(u, w) + sub(w))$$$, for any $$$w$$$ that is an ancestor of $$$u$$$ whose depth is greater than or equal to $$$b$$$'s depth.

    We can calculate this using binary lifting on values ($$$sub(v)-dist(E, v)$$$) for each $$$v$$$ and then adding $$$dist(E, u)$$$ to the minimum value found.

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

    Even if E is not fixed and given with query, we can solve this problem with time complexity O(Q log^2 N) by centroid decomposition + segment tree (I solved this problem with this method)

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

When points for the first task will be updated?

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

How to get full score of first task? I got 77 pts with below steps:

38 pts : divide N bits by M bits and result is calculated by xor

76 pts : divide M bits to (M/8) blocks with 8 bits. divide N bits to (M/8) blocks with (N/M)*8 bits.

each block of size (N/M)*8 correspond to a block of size 8. each location of the block have weight with range in [0, 256) (I used random). We want to make the (summation of the weight with number 1 in the block) mod 256 = (binary number of block of size 8)

and calculate minimum number of 0->1 changes by dynamic programming.

77 pts : change random seed

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

    The solutions for problems from day 1 have already been posted in the official website.

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

    Some thoughts: your solution and the official solution use the same idea, with 'addition mod 256' playing the same role as 'xor', and the block size $$$k=8$$$ replaced by $$$k=11$$$. This idea should be very close to achieving the theoretical upper bound, except for the step where you have to divide into $$$m/k$$$ subproblems. The reason it's close is because if we have $$$z$$$ 0s left, then we should except to need to write $$$o$$$ 1s, where $$$o$$$ is minimal such that $$${z \choose o} \approx 2^m$$$. I assume the dp used to calculate $$$P$$$ just makes this idea more precise. Assuming our decoding function is 'sufficiently random', we shouldn't need to write much more than $$$o$$$ 1s, and the dp makes sure that we don't write more 1s than necessary. But the subproblems part messes with this analysis, and also introduces another problem: As soon as one subproblem fails, we can't write any more data. So we don't want too many subproblems, I think.

    Here is a variant that should let you increase $$$k$$$ from 11 to about 16: Instead of doing dp (which is $$$O(z2^k)$$$), use meet-in-the-middle ($$$O(2^{k/2})$$$, more or less): enumerate the smallest subsets that we can choose, and check if we can combine (i.e. xor) two of them to get the desired result. (Now it is important that we use xor rather than addition mod $$$2^k$$$, because otherwise we might need to write 2's.) For birthday reasons, once we've enumerated about $$$\sqrt{2^k}$$$ subsets, we can expect to be done. Using a map for lookups seems to be too slow when $$$m=16$$$ and $$$b$$$ is small, but vector worked fine. (At least for $$$m=16$$$; I haven't tried the 'divide into subproblems part.)

    It would be nice if we could always take $$$k = m$$$, but it seems hard. (If $$$m$$$ is big enough, and $$$b/m$$$ is not too big, then I guess that instead of dividing into subproblems we might want use Gaussian elimination to 'write a subset of size about $$$m/2$$$' rather than 'the smallest subset'.)

    Anyway, a very nice problem!

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

Waaait... Please don't tell me that the official solution to Nautilus is pragmas xD

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

    C++ compiler is just too smart. We noticed that if you write the 66p solution in a rather clean way (from the compiler's point of view — such as not put if statements inside innermost loops etc), and then add pragmas, the result is almost as fast as the official bitset solution. This would pass for example: https://ideone.com/Xf7Ybh

    On my pc,

    • this solution: 0.3s with pragmas, 1.6s without
    • An official bitset solution: 0.15s with pragmas, 0.26s without

    (YMMV with the exact runtimes, but notice the tiny difference between 0.26s and 0.3s)

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

      I'm not a fan of bitsets, but to some extent i can understand official solutions including them, since they basically make the solution faster by log(max_val). But if it's known before the contest that you can, without much effort, get the same effect just by using micro-optimizations that don't have an effect on the asymptotic complexity, i think the subtask including bitsets should be dropped, or at least made less impactful.

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

        We just thought the probability of having a solution with pragmas from someone who wouldn't just immediately recognize the usefulness of bitsets seemed low enough to leave it as it is. And turns out everyone who got 100p during the contest did actually use bitsets. Would it really have been a better contest if all the 66p solutions would have scored 100p? :p

        Not sure about "without much effort". This runtime seems so random to me — if you replace memmove with swap, that solution suddenly runs in 6.5s instead of 0.3; but then if you delete the sse4 pragma, it runs in 0.4s even with swap?! Basically what I'm saying is that either you have to make a lot of random decisions correctly or actually know what you're doing :D

        What if the compiler gets even smarter and starts optimizing your recursive solutions into dp in the future when you add some #pragma NobodyCaresAboutMemoryUsage flag? :D

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

Since day 1 contest is finished, is there a way to check how good are my solutions now? Especially the interactive problem flash?

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

    Test sets are given on the contest's website.

    I'm afraid making Flash available online somewhere may prove difficult — as far as I know, the task is a complete nightmare from a technical standpoint. There is a testing script included with the test set, maybe it's possible to include one that more closely simulates the contest.

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

it seems that the online mirror doesn’t work again

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

How to solve necklace?

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

    We should find the longest $$$a + b$$$ where $$$s[i-a, i) = t[j, j+a)$$$ and $$$s[i, i+b) = t[j-b, j)$$$. So, if we fix $$$i$$$ and $$$j$$$, we can independently calculate the largest $$$a$$$ and $$$b$$$. If we do naively and use rolling-hash, we can calculate maximum $$$a$$$ and $$$b$$$ in $$$O(n)$$$, so it takes $$$O(n^3)$$$ overall.

    But we can speed-up this approach. It means we can get maximum $$$a, b$$$ in $$$O(1)$$$. We can use DP and let $$$dp_A[i'][j']$$$ the maximum $$$a$$$ when $$$i = i'$$$ and $$$j = j'$$$. Also same for $$$dp_B[i'][j']$$$. We can calculate this DP in $$$O(n^2)$$$. We can reduce memory, by typical approach, "reusing" DP array, because we only need $$$dp_A[i' - 1][?]$$$ for calculating $$$dp_A[i'][j']$$$, and so on for $$$dp_B$$$.

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

How to solve the third problem?

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

Who gets to participate in the BOI ?

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

    National teams consisting of 6 contestants per country. Countries participating are nations next to the Baltic sea. Teams are selected through their country's respective national olympiad.

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

ojuz when will the problems be available to submit? You can find the tasks here: http://boi2019.eio.ee/tasks/

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

    Good luck with implementing Flash, you have our blessing. :D

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

      No, we are not able to "start 4 instances of your program simultaneously", so I don't think the problem is judgeable (maybe I understood the problem little incorrectly)

      Also, we cannot deal with necklace too because of 'special' memory limit of 3MB (our poor memory measurement system will always spit out MLE)

      I have lots of tasks to upload (JOI Spring Camp, BOI, and all the OIs that will be done soon) but these days I have very little time. I will probably have time after a month, please wait a bit more :(

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

        Most of the technical details about testing are there because either (a) they were required to make the problem work in our testing system (CMS) or (b) they were designed to prevent (accidentally) cheating. It may still be judgeable (even if a bit less accurately) on your system somehow (but obviously will take time to figure out how :/).

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

Both contest days are now available for practice here:

https://cses.fi/boi/list/

The grader for Flash is not authentic, but it should be better than nothing.