대회후기: Ozon Tech Challenge 2020 (Div.1 + Div.2)

또 밀린 후기. 이번에는 퍼플 복귀전이다.

And today I can't be bothered to switch between Korean and English all the time, so I'll just go with English.

I mean, this blog is for me to read anyway... right?

---

A: Kuroni and the Gifts

Again I was braced to clear A as fast as possible. Read through the description in a breeze; skipped the examples.

Sort the two arrays and print them out.

AC at 2 minutes

---

B: Kuroni and Simple Strings

Question: Given a string of brackets(i.e. '(' and ')'), you can repeatedly remove a subarray of the given string if the subarray to be removed is a 'balanced parenthesis'. In as few operations as possible, you are to reduce the given string into one on which you cannot apply any more valid operations.

You are to output the indexes for the removal operations.

 

Didn't think too much about the solution. My algorithm greedily picked up opening and closing brackets from the front and end of the given string, respectively, in matching numbers. It did so until no more brackets could be removed - what I didn't realise at the time of submission was that I only needed to run one of such operation at maximum.

The implementation took a bit of time.

AC at 17 minutes

---

C: Kuroni and Impossible Calculation

Question: You are given a whole lot of integers to process. What you have to calculate is the product of the differences between every pair of integers - but there's a catch. The solution has to be output to a modulo of $m$, which's value maxed out at 1000.

 

First I tried to optimize the calculations - in vain. 6+ minutes must have passed when I stopped my efforts and re-read the problem name: the "Impossible" Calculation. Then I saw it: the absurdly low value of $m$. I almost instantaneously saw the pigeonhole principle at play. When more integers are given than $m$, the pigeonhole principle guarantees that the answer is 0. Else, you can actually go about the calcuation in full. Implementation is trivial.

AC at 26 minutes

---

D: Kuroni and the Celebration

An interactive problem. I don't know why, but I seem to like them.

We are given a graph. But it's actually a tree.

Except we don't know where the root is - our goal is to find out.

 

We can ask the judge what the lowest common ancestor of two nodes is, maximum $\lfloor \frac {n}{2} \rfloor$ times.

Then we have to guess the root node - and better guess it right.

 

I have no precise reasoning behind this that I can put into words of logic, but I thought that It'd be ideal to ask a query of two nodes as far apart as possible in order to get as much information from their lowest common ancestor. So I then asked myself what would happen if I got the answer to such a query. The answer has to be on the path between the two nodes(which would naturally be leaves) of the query, as there exists only one path between any two nodes of a tree. If the ancestor node was a node with a degree of 2 or less, that itself would be the root. Else, we just found out that every other node on the path cannot be the root. Sever the connections to the path from the ancestor node, and continue our search for two leaves far away from each other from that very node. Repeat and you will get the root. One more thing I realised afterwards is that I don't need to necessarily take the two furthest leaves for queries - just two leaves will do. Any query of two leaves is sufficient to remove 2 nodes from being root candidates(or to find the root itself), which in turn is sufficient to guarantee the algorithm terminate in $\lfloor \frac {n}{2} \rfloor$ queries or less.

Wordy algorithm, took long to debug too.

AC at 1 hour and 23 minutes

---

E: Kuroni and the Score Distribution

I was so close on this one, but failed by a sliver.

Input: integers $n$ and $m$

Output: An integer array of length $n$ and balance $m$, if possible. The balance of an array $a$ is defined as the number of integer triples $(i, j, k)$ such that $i<j<k$ and $a_i + a_j = a_k$. If impossible, ouput -1.

 

If you think for a bit, you can quickly see that having consecutive numbers is the way to maximise balance. So you should have consecutive numbers starting from 1 for as long as the balance doesn't exceed $m$. Then the next single number should be placed not consecutive but with a gap with the previous number so that it can create exactly the number of triples needed to make the balance total to $m$. => This is as far as I got with the problem.

 

Next we need a way to place the remaining elements of the array so that no more triples are created. The integers in the array had to be below $10^9$ so simply increasing the elements exponentially wouldn't do. The editorial revealed that doing $10^8+k \cdot 10^4+1$ for the remaining elements was satisfactory, as two odds don't ever add up to another odd.

Should have thought more on parity.. wasn't too far off track when the competition ended.

3 WA

---

총평

The problems didn't require knowledge of complex data structures or algorithms, which I think is why I scored good on this one. E를 해결하지 못한 것은 너무 아쉽지만... 퍼플 복귀지만... 아쉽다 ㅎ

 

레이팅 변화 1882 + 39 = 1921

My Performance: ★★★★☆

 

연습지