Блог пользователя computerbox

OpenCup 2020-2021 GP of Siberia
Автор computerbox, история, 4 года назад, перевод, По-английски

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

  • Проголосовать: нравится
  • +32
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +80 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How to solve in Div1:

  • 8 Text Editor
  • 5 Loggers Inc.
  • 2 Antiwaist
→ Ответить
»
4 года назад, # |
← Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +10 Проголосовать: не нравится

      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.

      → Ответить
  • »
    »
    4 года назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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})$$$

    → Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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?

→ Ответить