Friday, September 8, 2023

AWTF22 day 1

AtCoder WTF22 onsite day 1 just finished (problems, results, top5 on the left, mirror resultsanalysis). I was actually able to get a problem accepted after two hours have passed, with the caveat that this was the only problem I got accepted :) I probably spent about an hour on B and about three hours on C, with no success. In C, I passed all samples except the last one. It turns out that I did have the correct "minimal representation" for a tree at the end, but then I tried to merge them to obtain a minimal representation for a forest in the same format, but it turns out that this was not possible at all: when merging trees B->W<-B (W is root) and W->B (B is root), the minimal representation is just B, but if we later merge it with a tree W->B<-W (B is root), we get a non-empty representation, while if we choose B->W<-B for the result of the first merge, then we can cancel everything out on the second merge. This counterexample stems from the correct solution idea, which tells that one of the conditions for being able to cancel everything is having at least two roots of different colors; hence any approach that merges the representations of trees has to be able to tell if we have seen two roots of different colors. I feel that this was pretty hard to come up with without actually coming up with the trick from the editorial directly.

Congratulations to everyone who was able to solve two problems in this round, and especially to ksun48 on the total domination and to hos_lyric for solving E!

Given that tomorrow's round has a 1000-pointer as the first problem, I might have to be content with the points I already have. But I will do my best ;)

No comments:

Post a Comment