ko_osaga's blog

Baltic Olympiad in Informatics 2023
By ko_osaga, history, 12 months ago, In English

It seems that Codeforces is flooded with spam bots now. Unrated spam bots have a long history on this site. The only difference is that now they work in an automated matter, instead of people who think like bots. So why are they able to write posts in the first place?

Enough rant, Baltic Olympiad in Informatics 2023 is held in Lyngby, Denmark. Good luck to all participants!

Day 1 mirror starts in an hour. Let's discuss the problems after the contest.

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

»
12 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

How to solve day 1 problem 2? I got 66/100 with randomization.

→ Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it -41 Vote: I do not like it

    How to solve day 2 problem 4?

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

      I got 78/100 by just DFSing. I chose all nodes that had only 1 edge as starting nodes. For the second task where there is an intersection, I did BFS to find the most distant node from that intersection and then used DFS from that node but that only works when there is only one intersection.

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

        Possibly wrong task? I asked about staring contest (from day 1).

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

          Sorry, I answered the Lex person who asked about the 1st problem in today's competition. I got the staring contest 50 points. Was pretty perplexed about it, how to do it in n + 25 queries. Sorry, I should have not answered him.

          → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      I just asked for D2P1 why are you downvoting :(

      → Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Codes for which I fullscored

How to solve day2 p2?

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

    Idk, but the first query is probably $$$(b, b), (b, -b)$$$, do you have a solution for $$$w=3$$$?

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

      No, I have $$$k \log k$$$ query and my first queries are also that (but in two times).

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

        I think you need to query something with $$$x$$$ or $$$y$$$ coordinates of the candidate points

        → Reply
  • »
    »
    12 months ago, # ^ |
    ← Rev. 3   Vote: I like it +16 Vote: I do not like it

    If you have a point with a maximum $$$x$$$ as a candidate, you can query $$$(x+d,y)$$$. Delete this candidate, and ban all distances $$$d$$$ between this query point and candidates.

    if you find $$$d$$$ in the distances you can delete that candidate and the distances to the query points.

    For full points, choose the smallest $$$d$$$ that is not banned and check for which candidate $$$(x,y)$$$ distance $$$d$$$ is unique for one of the points $$$(x+d,y), (x-d,y), (x,y-d), (x,y+d)$$$ which are inside the box.

    You will always find it since $$$d\times k = O(k^5) < 2\times10^8$$$

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

      May I ask how do you do this in two queries?

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

        Do $$$(-b,b)$$$ and $$$(b,b)$$$ in one query and the thing I described above in the other query

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

I think the easier 4 problems are very standard, but I won't say much because the participants may feel differently.

For day1 p1, maybe I'm wrong, but I don't think there is any sort of participant in the world who likes such problem...

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

    What are some key points/ concept one must know to tackle Day1, P1, in general how can it be solved for N points, it is really hard since the trade-off between choosing a good radii or moving some distance with a bad radii.

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

    I like the problem, but I haven't competed in the open contest.

    → Reply
  • »
    »
    12 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    Yes, you are wrong :) I think this problem looks very fun and I take it over almost any DS problem :p

    → Reply
»
12 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

When will the standings be shown?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Anyone have insights for day 2 problem 3?

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

    Can you provide hints for day1 P1?

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

    Imagine the sequence backward: it starts from $$$N$$$ and it "spreads out", in the form of $$$N - 1$$$ or $$$x, y$$$ such that $$$xy = N$$$. Let $$$DP(S)$$$ be the minimum cost to create a sequence that contains the set $$$S$$$. Transitions are: Decrement one element, or divide one element into two smaller ones. Complexity estimation is tough, but using unordered_map makes it pass.

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

      I should learn how to read

      → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      Is that a "very standard" problem to you lol xd?

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

        I never thought of something like that (I was stuck on the $$$s_1 = s_2 = \dots = s_n$$$ subtasks...), so in my opinion, either I am too inexperienced or this isn't standard lol

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

        Hmm, I think the hardest part is to learn how to hash vector.. I don't know. "write brute and pray it don't mess up for random reason" isn't too standard, maybe

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

          Using stl map worked just fine for me

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

          Lol, you chose literally the most standard and least important part of the problem and called it the hardest part xd (I assume you are aware of standard hashing of words and words<=>vectors, though standard set hashing seems even more appropriate, i.e. hash of the set is the xor of random values associated with every element of our domain)

          I admit that this problem falls under "write a (seemingly?) exponential solution and pray that the number of reachable states is low" type, which is probably not the most exciting type of problems in the world, but IMHO it is much more than just that. At least for me, this looks like a random textbook backtracking problem with no sensible solution and the thought that this could potentially be solved polynomially seems completely ridiculous. During the process you need to consider states that are sets of integers of unbounded size. It is very uncommon that something like this will lead to a polynomial solution and what is more — the solution turns out to be almost-linear, i.e. $$$O(n^{1 + o(1)})$$$! Proving this (or any other polynomial bound) was not required to get 100pts, what might have caused people who solved it "yolo way" to underappreciate its beauty

          Also, in order to get 100 points, you need to have some clever idea anyway and come up with some solution that cleverly forgets about irrelevant sequence parts (what may include guessing these if you choose to solve it forwards). It's not like the simple bruteforce has any chance of solving the problem. And even if you have that idea, it is highly nontrivial to understand why such solutions have any chance of solving that within reasonable time

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

            Man, I got 85 point at 14 minutes after contest, and after constant optimization got 100 in 25 minutes. You should grind ds to gitgud

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 months ago, # ^ |
                Vote: I like it -28 Vote: I do not like it

              Lol. I understand that this problem turned out to be easier than expected, but you seem to either misunderstood or just ignored my main point. Also, you have 3500 rating (camping on it though), so it's not like you can't solve hard problems fast from time to time. You're lucky that it did not require knowing how FFT works though ;)

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

            For the handwaving, I noticed that for a set with fixed product there are not many worst case, for example 2*3*5*7*11 or 2^14. And this is a number theory stuff, random shits work

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

Also why does it take so long for results to be published (in both mirror and official contest)?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Day 1 P3?

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

    Let $$$DP[i]$$$ be the minimum time to leave the shelter $$$i$$$, given that you intend to avoid periodical damage from there. $$$DP[i] = min(DP[j] + \lceil (x[i] - x[j]) /p \rceil (p + d))$$$ plus something.

    If we can replace the fractional part to $$$\lfloor x[i] / p \rfloor - \lfloor x[j] / p \rfloor$$$, then the problem is easy. But If $$$x[j] \% p < x[i] \% p$$$ you have an error term of $$$1$$$. Therefore, those cases should be done separately.

    To do this, you can maintain an RMQ with key $$$x[i] \% p$$$. If the queried part has a smaller modulo, add an error term, otherwise just do it normally. Remember to do coordinate compression over $$$x[i] \% p$$$.

    → Reply
    • »
      »
      »
      12 months ago, # ^ |
        Vote: I like it +20 Vote: I do not like it

      I think maintaining a decreasing stack in a map works better since it's either a prefix or suffix queries.

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

    an alternate solution with a less clean implemenation but a more obvious dp definiton than ko osaga's :

    define Dp[i][j] = minimum time to reach the shelter i at time t, such that t % p = j

    then, there are 2 types of transitions :

    1) Dp[i][(j + x[i] — x[i-1])%p] = Dp[i][j] + damage taken in interim

    2) dp[i][j] = min(dp[i][j], dp[i][(j-1}%p] + 1) (because you can wait before leaving a shelter)

    This gives an easy n * p solution.

    To improve it, you note that the 2nd kind of transition is just a range set on dp[x] — x, and the first kind of transition is range add (ill leave you to figure out the details).

    Then, you just store the dimension of p in a segment tree with range set and range add, and do n * log p updates

    For full, use dynamic segment tree

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

where can I upsolve problems?

→ Reply
»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For Day2 P3 can someone give example where sorted sequence isn't good, but unsorted is? Thanks in advance.

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

    Sorted sequence always better than unsorted

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

      But when I submitted code with considering only sorted sequence it didn't pass, but considering also unsorted did.

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

        I submitted code with considering only sorted sequence and it passed so most probably it's bug

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

          Oh, ok. Thanks for help

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

Is there going to be any editorial ?

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

Is it possible to submit or reach test cases of the problems? I can't submit on kattis mirror.

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

    Are you sure your problem isn't this?

    If that doesn't work, the problems should be uploaded on CSES (hopefully) in a couple of weeks.

    → Reply