Если вы используете C++, пожалуйста, выберите в качестве компилятора при отправке решения: C++14 (GCC 6-32) или C++17 (GCC 7-32). ×

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

Автор socho, история, 4 года назад, По-английски

Hey all!

We would like to invite you all to an online replay contest for UWCOI 2020. UWCOI 2020 is an OI-style contest hosted by UWCSEA Dover which was used to select members for the UWCSEA Dover team for the Singapore National Olympiad in Informatics for this year. The online replay contest will be held as a round rated for both Divisions on CodeChef.

Here are some details:

  • Time: Tuesday, February 25, 2020, 21:00 hrs IST (Indian Standard Time). Please check your local timezone here.
  • Contest Format: 7 OI-style tasks (all tasks have subtasks) in 3 hours
  • There is no time penalty for non-accepted verdicts; however, time will be used as the tiebreak.
  • The contest is rated for both divisions (all ratings).
  • The writers are astoria, kimbj0709 and socho.
  • The technical committee also includes smjleo.
  • The contest is hosted on CodeChef, at this link.
  • For all questions, please email us at [email protected]

We hope you enjoy the contest!

Update: Just a gentle reminder that the contest begins in about 3 hours from now! We hope to see you there!

Update 2:

Thank you all for participating! We hope you enjoyed the contest. Here are the problems and editorials:

Please let us know if you have any comments / feedback!

Update 3: All editorials are now available!

Thanks,
The UWCOI Committee

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

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

7 questions with subtasks in 3 hours :o

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

Nice problemset.

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

problemset was good but most unbalanced contest i have ever given.

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

How to solve Mercury Poisoning?

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

    Process queries offline. Then you can count number of reachable cells using ufds.

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

      I thought about this, To sort the queries in the ascending order of powers and solve them in order. When we reach a cell which is already visited due to a previous query, add the size of that set to the answer and combine the present set of cells to that set using ufds.

      But, there could be some cells(A[i][j] > Power(previous query) but A[i][j] < Power(current query)) which are reachable from already visited(from previous queries) cells but are not directly reachable just through unvisited cells from the current starting cell, right? How did you take care of that? I hope my question is clear...

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

        Maintain another vector of cells and sort them by power. When you process a new query you process cells that are newly reachable.

        Idk if theres a faster method... my code got 1.9s

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

          I did exactly this. I also converted the grid into linear n*m array and carried out the union find operations. But it is not passing the TL on last subtask. Can you catch the bug here

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

            Just use vector pair and sort them instead of using map. It will work smoothly. Bcz simply inserting random 1e6 elements into the map takes almost a second, more precisely 0.91 as measured on ideone by me. You are doing it for 2 test cases + dsu + map with vector is also a bit slow (arrays are faster than vector).

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

        You need to sort both the queries and the matrix(in a temporary array) and process them using two pointers and join matrix elements using DSU while checking appropriate conditions.

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

      What is udfs?

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

        Union-disjoint find set

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

          I read it udfs in place of ufds which is why I got confused. But you then also changed the abbreviation to make it Union-disjoint find set? haha xD

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

Is there a more elegant method for Escape than running O(K) dijkstra to compress the graph?

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

    Not that I know of.

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

    sadly the following method didn't work (and don't know why):
    do a multi-source dijkstra from all important nodes, and save for every node in the graph the closest important node to it, and then build the new graph from the edges that have ends closest to different important nodes.

    for more details about this method please see F. Cheap Robot Editorial.

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

      I think because cheap robot you only care about the nearest imporant node. But here we cannot just ignore that. Suppose A,B and C are all keys.

      You have edge from AB and BC.

        B
        |
      A-D-C
      

      Suppose A-D and D-C is very long, you will only have edge from A-B and B-C in your new graph, so now when you find the weight of A-C, it will be the length of (A-C) + (D-B)*2.

      But not entirely sure as maybe your implementation may be different. maybe i can look at your code?

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

        yes you're right, sometimes in the compressed graph we can't reach some key nodes which we actually can reach in the original graph, so the solution is wrong.
        here is a simple counter-test:

        counter-test

        thanks for debugging the idea, and here is my code.

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

    Can you please elaborate on the approach you had

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

How to solve Blocks?

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

    240 = maximum number of divisors of number less than million. Iterate over divisors, how to check whether some number $$$k$$$ can be answer? It is easy to see that answer for query $$$n / k$$$ should be $$$n$$$ — $$$n/k$$$. Then to solve a problem fully you need to iterate over prime divisors of $$$n$$$, and use the fact that if some number $$$k$$$ can't be an answer, than no number divisible by $$$k$$$ can't be an answer too.

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

    For $$$Q \le 240$$$, simply brute-force all the factors of $$$N$$$.

    For $$$Q \le 20$$$, factorize $$$N$$$ as $$${p_1}^{k_1}{p_2}^{k_2}\dots {p_n}^{k_n}$$$. Since $$$2^{20} > 10^6$$$, it is enough to make queries for each $$$\frac{N}{{p_i}^{k_i}}$$$.

    For $$$Q \le 9$$$, use binary search to the power of each prime factor.

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

1st two problems was very easy but after those two difficulty gap was huge! Problems difficulty should be balanced for a good contest :/

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

Please provide some tutorial ,question link of counting problems