lior5654's blog

[Discussion Thread] IATI 2020
By lior5654, history, 4 years ago, In English

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/

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

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

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

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

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

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

      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.

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

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

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

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

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

    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).

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

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.

→ Reply