borgar02's blog

IATI 2022 editorial
By borgar02, history, 17 months ago, In English

Is there an editorial for the IATI 2022 problems, or can anyone explain their solutions? I am interested especially in the day 2 problems.

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

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

are there any problem statements published as of now?

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

Problem 2 day 2 consists of several steps:

  1. Finding the right approach (best strategy)

  2. Get all the relevant formulas.

The best strategy is to add a character to the smaller string, and if you make a mistake, always remove it.

Let's assume that size of first string is $$$i$$$ and it's smaller than the size of the second string. $$$l[i]$$$ will be the Expected Value of steps needed to a new character to first string. That is increase the size with 1. According to the best strategy, the value doesn't depend on the size of the second string. If Luca wasn't lucky and he made a mistake, he will need $$$lf[i]$$$ steps to go back to previous stage, when the size of first string was $$$i$$$ and the second string has no mistakes.

It's easy to get the following 2 formulas:

$$$lf[i] = 1 + p * (lf[i-1] + l[i-1])$$$

$$$l[i] = 1 + (1-p) * (lf[i] + l[i]) = {{1 + (1-p) * lf[i]} \over {p}}$$$

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

Day $$$2$$$ problem A: You are given an array $$$a_1,a_2,\ldots, a_n$$$, an integer $$$A$$$ and $$$q$$$ integers $$$R_1,R_2,\ldots R_q$$$ (queries). In one operation you may swap $$$2$$$ adjacent elements of the array for cost $$$a_{i-1} + a_i$$$. You should answer these $$$q$$$ queries independently: for fixed $$$R$$$, what is the minimum possible value of $$$a_1 + a_2 + \ldots a_R + cost \ of \ operations$$$? Here, $$$cost \ of \ operations$$$ denotes the total cost of all operations performed.

Main subtasks are:

  1. Solving the problem in $$$O(q \cdot n \log n)$$$
  2. Solving the problem in $$$O(n^2)$$$
  3. Using some heavy data structure to solve for $$$1 \leq n,q \leq 50 \ 000$$$

I should note that I haven't solved the full problem, but I suspect that it can be solved in $$$O(n \sqrt{n} \log n)$$$.

First Subtask
Second Subtask
Possible ideas for a full solution

I should note again that I don't have a concrete full solution. If you (anyone) have, please reply to this comment.

→ Reply
  • »
    »
    17 months ago, # ^ |
    ← Rev. 2   Vote: I like it +10 Vote: I do not like it
    Spoiler
    → Reply
»
17 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve B6 (Sorting) and A2 (Ones)?

→ Reply
  • »
    »
    17 months ago, # ^ |
      Vote: I like it +24 Vote: I do not like it
    A2 (Ones)
    → Reply
»
17 months ago, # |
  Vote: I like it +14 Vote: I do not like it

A6 can be solved with min cost max flow.

First thing to note is that we can limit number of different lifts using fake node which is connected to source node with edge having capacity k and cost 0. We can add edge between this node and every node representing some person.

Next, we will add edge with capacity 1 and cost abs(R_i — L_j) between person i and person j, i < j. This means that after person i, person j can call lift which will be empty for exactly abs(R_i — L_j) floors.

There is one problem, we need to make this flow visit all nodes. How we do it? We can for each person make in and out vertex and add edge with capacity 1 and cost -inf between them.

Ok, what about MLE? Trick is we can store only edges for which flow has changed, there will be at most N*K of them. (I haven't implemented this, but I guess this works).

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

    You can solve the problem in $$$O(n k \log^2 n)$$$ by reducing the dense graph to a more sparse one, by imposing extra vertices and edges in the flow network, using a virtual persistent Fenwick tree as a basis (there was a classical problem of simulating Dijkstra on a graph where you have edges between ranges $$$[l_i, r_i]$$$ of vertices, could someone please link to it if you know what I'm talking about?).

    Basically, process lifts in order, and then add edges via a Fenwick tree from all lower floors to the starting floor of the current lift of cost $$$l_i$$$ (using a Fenwick tree, again), and then from the ending floor of the current lift to all upper floors of cost $$$-r_i$$$. Do the same for the other direction (upper floors to starting floor, ending floor to lower floors). This way you reduce your network to $$$O(n \log n)$$$ edges, where you can do $$$k$$$ iterations of Dijkstra.

    Also, to compute initial potentials, notice that the network is a DAG, so you can relax edges in order of topological sort, instead of Bellman-Ford (although I suspect Bellman-Ford also fits the TL).

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

      I think this is pretty much the problem about simulating Dijkstra that you mentioned: https://codeforces.com/contest/786/problem/B, but it only has node — range edges. The range — range case can be solved in a similar manner anyway.

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

      That is pretty much the intended solution, with the only difference that instead of using a persistent tree, you can easily build the compressed network with divide and conquer.

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

Here is an official archive of the IATI '22. It not only contains the problems but also the attempts of all of the participants!

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

Does anyone know the solution to A5 Fork? I couldn't find the explanation in the contest material.

→ Reply
»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Here you can submit your solutions to problems from IATI 2020 to 2022!

→ Reply