My friend kept telling me to do this, so here we are.
I will be writing solutions to the problem(or at least the ones I know), but they won’t be good.
The time written means how much time has passed since the round started
00:00 ~ 00:02
Read Problem A and solved it. It was easy to see that you had to move $\frac{|a-b|}{2}$ grams of water, and therefore the answer was $\frac{|a-b|}{2c}$.
00:03 ~ 00:07
Read problem B. Each time you pass a trap, the maximum length you can go and come back until the trap closes is chosen(use have the time to go forward, the rest to come back). Therefore for all traps, we just have to take the minimum of that value.
00:08 ~ 00:18
Read problem C. I first misread the problem as $l \leq a, b \leq r$, which created some time loss. If $r \leq 3$, there is no answer. If there is an even number between $l$ and $r$ that isn’t two, we can just return half of that even number, since the greatest common divisor of two equal numbers won’t be 1. If there isn’t any, then $l = r$, and all we have to do is find one divisor of the number, then just multiply the divisor in any way so that the sum equals $l$. If there is no divisor, there is no answer.
00:19 ~ 00:23
Read problem D. It was obvious that the largest numbers had to be placed in $p_{k \cdot x}$, and the smallest numbers had to placed in $p_{k \cdot y}$. If a number is a common multiple of $x$ and $y$, we can ignore it. If we call the least common multiple of $x$ and $y$ as $l$, the answer would be the sum of the $\lfloor \frac{n}{x} \rfloor - \lfloor \frac{n}{l} \rfloor$ largest numbers, minus the sum of the $\lfloor \frac{n}{y} \rfloor - \lfloor \frac{n}{l} \rfloor$ smallest numbers.
00:24 ~ 00:40
Read problem E, and the first thing that came to mind was lazy propagation. However, I didn’t think that would be the solution, but I couldn’t get it out of my head, and therefore wasted some time.
I eventually figured that for every query of the first type, I can maintain the xor value by just xor-ing the xor sum of numbers from $l$ to $r$, which can quickly be found using a prefix xor sum. This works because all the numbers that were previously in the xor sum would be gone, and the ones that weren’t there would be added, which is the same as changing the 1’s and 0’s in the string.
I kind of didn’t wish it took me that long, but whatever.
00:41 ~ 01:48
Read problem F. I first tried thinking of a greedy or dynamic programming solution, but it didn’t seem like it would work so I dropped the idea.
Then I thought that if I created a directed graph where $i$ pointed to $a_i$, then I could use strongly connected components to change it into a DAG, because then the only thing I need to worry about are the cycles that don’t point to other cycles. It would have worked, but I was having a hard time thinking on how to implement it.
After some time has passed though, I figured out that since one node only points to only on other node, it is impossible for a cycle to point to another cycle, hence the need for SCC’s were gone. I just had to start from nodes with an indegree of 0, then just deal with the cycles.
For cycles, it’s obvious that the node with the smallest cost had to be sold last. I didn’t really think about the orders of the other nodes in the cycle, which led to 3 wrong answers. But I changed it so that it would start from the node after the cheapest one, then make its way around the cycle, and I got accepted.
I thought about problem G, but I was too tired(it was like 2am), so I just stopped here, and the contest ended.
Post-Round
I solved problem G after the round ended. The solution was, that if the product of all the numbers go over a certain threshold(say one million), then it is best to pick the smallest range so that all the non-one numbers are included. Otherwise, there are only very few non-one numbers, and therefore we can bruteforce by trying all ranges where each end is not one to find the answer.
Knowing the solution, the problem doesn’t seem that hard, but I’m not sure if I would have managed to thought of it during the contest. It’s definitely not something I’m that used to.
Overall I wished I managed to solve E and F faster than I did. Guess I just have to keep practicing.
Results
- Problems solved: 6, A~F
- Total performance(according to carrot): 1983
- Standings: 535 unofficial, 163 official
- Rating change: 1579 $\rightarrow$ 1692 (+113)