computerbox's blog

OpenCup 2020-2021 GP of Siberia
By computerbox, history, 4 years ago, translation, In English

Hello everyone ! Let's discuss problems here . How to solve Problems: Find the Radio Operator, Morse Code , WoodCut ?

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

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

The quality of most problems of GP of Siberia is comparable with GP of Serbia.

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

Find the radio operator:

Let's make 2 queries from the point (-V, -V) where V > 1000 (we choose V = 5000): one where we point the antenna to right and another one with antenna pointing up.

If we note with f1 and f2 the angles defined in the statement, we observe that both f1 and f2 are less than 90 degrees and their sum is exactly 90 degrees. By dividing the two equations that we obtain after reading the values, we find the value of tan(f1) (as R is the same for both queries). Now we know that the radio station must be on a line containing the point (-V, -V) and having a known angle.

Repeat the process with point (-V, V) and antenna pointing down and to the right and you get another line. The radio station is the intersection of these lines.

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

Morse code:

Calculate dp[i] the minimum number of errors such that the suffix of the signal starting at position i represents a valid text formed by words from the dictionary (so there is a word starting at this position).

If we fix the first word, we can uniquely identify the position that the next word should start and we can also check if that word can start at position i (just check that the groups of '-' and '+' are the same and that the absolute difference between the corresponding ones from the signal and from the word is at most 1). If the check is done in complexity O(len(word)), then dp[i] can be calculated in complexity O(sum_len(words)).

To find the lexicographic smallest answer, pick the lexicographic smallest word (that minimizes the number of errors) at each step.

To ease our implementations, we represented both the words and the signal as vector of pairs (char, count) and written the dynamic directly on this.

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

How to solve in Div1:

  • 8 Text Editor
  • 5 Loggers Inc.
  • 2 Antiwaist
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

So, how to do 8 (Text editor) without banging the head against a wall trying to squeeze the solution in both TL and ML?

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

    I'm wondering the same thing (just from the side that was not able to squeeze it in TL)

    We encoded the state like:

    • current permutation: $$$8!$$$
    • cursor position: 9
    • state of the editor: 3 ( with clipboard data OR shift-pressed OR none)
    • size of clipboard data OR where was shift pressed: 9

    Then ran dijkstra on top of that graph with transitions computed in $$$O(1)$$$. Overall complexity was $$$O(3 \cdot n! \cdot n^2 \cdot \log(3 \cdot n! \cdot n^2 ))$$$

    That was not enough to pass TL.

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

      We had the same solution. We squeezed it in TL by replacing the priority queue in Dijkstra with an array of $$$100\,000$$$ vectors (since we could convince ourselves that the required time should never exceed $$$100\,000$$$). This gets rid of the $$$log(3 \cdot n! \cdot n^2)$$$ factor and is just enough to pass. Of course, you still need to optimize a bunch of other stuff... We had to reimplement the solution from scratch since the first code was just a bit too slow.

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

    Idk, just precalc all transitions and do 0-k bfs instead of dijkstra, works just over 1.5 sec:

    Code

    I even have $$$O(n! n^{3})$$$ transitions, and to calculate each transition I used $$$O(n)$$$ more, so complexity is $$$O(n! n^{4})$$$

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

Editorial on Russian language https://codeforces.net/blog/entry/84262 . I guess on Google Translate ,it will be ok.

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

I did not think O(n^2) would get accepted for #6. I think we can solve single cache in O(n) and unbounded cache in O(nlogn). Did anyone also do so?

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

    Actually, I did implement the O(N^2) DP and it worked in ~0.4s.

    → Reply