### FiveSixFiveFour's blog

By FiveSixFiveFour, history, 2 months ago,

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

 » 2 months ago, # | ← Rev. 2 →   0 Anybody managed yet to get 100 on Senior D1 P2? Would love to see the approach
•  » » 2 months ago, # ^ |   0 Can you please share the statements? I might try helping with that 100 if you do at least that.
•  » » » 2 months ago, # ^ | ← 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,jSuch that 0 <= i <= j <= n-1And if Ai + Aj < Ak + AlThen (i, j) is before (k, l)For example, for the array3 1 2You should return the vector 1, 1 2, 2 0, 0 1, 2 0, 1 0, 2Note that Because A0 + A0 == A1 + A2 You could swap their order in the output and the output will be still validYour score for every testcase is min(1, ((2N^2 + 1) / (Q + 1)) ^ 1.25) * sWhere s is how much that testcase is worthNo 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.
 » 2 months ago, # | ← 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
 » 2 months ago, # |   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 6Output: 7 5 3 2 0
•  » » 2 months ago, # ^ |   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 41 . | . . . .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).
 » 2 months ago, # |   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.
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 It was like that on EJOI, so it was expected.