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

[Discussion Thread] IATI 2020
Автор lior5654, история, 4 года назад, По-английски

Opening this thread to discuss XII International Autumn Tournament in Informatics (IATI) Problems.

Hope everybody had a great competition!

https://iati-shu.org/en/home/

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

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

Anybody managed yet to get 100 on Senior D1 P2? Would love to see the approach

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

    Can you please share the statements? I might try helping with that 100 if you do at least that.

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

      All statements should be uploaded to the website soon.

      That specific question was the following:

      Theres a secret array A that has n elements.

      You can ask queries of the form a,b,c,d — is A[a] + A[b] < A[c] + A[d] ?

      You want to sort all pair sums, namely You want to sort all pairs i,j

      Such that 0 <= i <= j <= n-1

      And if Ai + Aj < Ak + Al

      Then (i, j) is before (k, l)

      For example, for the array

      3 1 2

      You should return the vector 1, 1 2, 2 0, 0 1, 2 0, 1 0, 2

      Note that Because A0 + A0 == A1 + A2 You could swap their order in the output and the output will be still valid

      Your score for every testcase is min(1, ((2N^2 + 1) / (Q + 1)) ^ 1.25) * s

      Where s is how much that testcase is worth

      No one managed to get 51 or above in the competition, but Noam13 is the only person who got above 50. I also sent the exact statements in AC a while ago.

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

I think some of the time limits were really fucked up...

  • N^3 working for N=1000 in D2 P1 (cancer)

  • N*(logN)^2 with dynamic (lazy) segment tree on D2 P2 (rectpoints) after a lot of cancerous constant factor optimization got me 100 AC 0.395/0.4s

  • In the practice section, P1 map TLEd but set ACed

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

Junior D1 P3, I managed to get 45 points by using Fenwich tree to calculate inversions at start and then each of removals I did in O(N). Does anyone know how to get 100 on it?

Problem:

Given array of N numbers each one being between 1 and N. All numbers are different. Find number of inversions of the orginal array. After that there are N-2 moves. For each move you insert one number, value of element that is going to be removed from the array. After each move you need to output the number of inversions in the array without the removed element and all previously removed elements.

Constraints ● 3 ≤ N ≤ 100 000 ● in 10% of the tests: N ≤ 100 ● in 30% of the tests: N ≤ 5000 ● in 45% of the tests: N ≤ 15000

Sample: Input: 6 6 1 2 5 3 4 3 5 4 6

Output: 7 5 3 2 0

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

    Even though I didn't manage to make this solution pass, I hope this is the intended solution. Write the array on horizontal and the ordered permutation on vertical and mark (i, poz[i]) for each i, 1 <= i <= n. You should obtain something like: 

      6 1 2 5 3 4
    1 . | . . . .
    2 . . | . . .
    3 . . . . | .
    4 . . . . . |
    5 . . . | . .
    6 | . . . . .

    Now, when you delete an element you have a few cases to take into account and update the number of inversions. To compute these queries you can use a 2D Compressed Fenwick Tree. I think its implementation will decide whether you get 45 or 100 points. The total complexity should be around O(N*log^2N).

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

I am just curious, was it known before the competition that only official contestants will be counted towards medal distribution, or is it something that was decided later after the results came out? Honestly a really strange rule.

→ Ответить