I don't know whether this idea has been discussed somewhere before, but I find it quite interesting.

PT07X — SPOJ

Summary of the problem: Given a tree find a largest set of edges such that no two edges share an endpoint (maximum matching), or to find minimal set of nodes such that each node outside the set must be adjacent to at least one node in the set (minimum vertex cover).

Usual algorithm: Dynamic programming (refer to this blog : Codeforces blog)

My (maybe-wrong) greedy idea:

1. Root the tree at arbitrary node, let say node 1.

2. Find the distances of other nodes to node 1 (means find the height of each node). Sort the nodes according to their distances to node 1 (means sort by height).

3. Go from the node with greatest height, if this node is not used and its parent is not used, then we match this node with its parent.

My correct submission to above SPOJ problem: https://ideone.com/CeWhlr

Could anyone prove or disprove it? Thanks in advanced!

Hello Codeforces,

I am Trung, co-founder and head organizer of HNOI Civil War 2019. We believe that organizing contests for high school students to inspire about competitive programming, computer science and algorithms is not enough, so that we have taken further steps to contribute to our community. By sharing knowledge/ideas via interesting visual-audio content, we hope to bring the sense of real sport in competitive programming: enjoyable yet challenging.

So feel free to enjoy our first video on Youtube channel: HNOI Civil War Youtube channel. Subscribe to receive interesting videos about programming and algorithms. Also, our fanpage HNOI Civil War FB fanpage

We open a form for you to contribute any ideas/knowledge that you want to share with community via multiple social medias! https://forms.gle/g8KE9MTNdxqkuZFu5.

Finally, good luck with your Codeforces rating! And round 581 tomorrow!

This blog might appear weird and confusing to all of you. But nevermind, I was just blogging a bit to relieve the tension that harbored in my brain for a week before one of the most crucial competition in my life, Vietnamese Olympiad of Informatics (VOI for short).

Complaining

Here I would list all (or not all, maybe I was too illusive to think so):

Algorithms sucked

Not because I am not good at what they say, Algorithmic Thinking (attention here: this might be the case of illusive thinking again), but I did not keep track of my thinking on a much more complex problems, like constructive-related problems. I learned Math, so indeed I was a bit confident of my ability in competitive programming, but via some try-hards at constructive algorithms, I was totally disappointed. The reason is that, maybe I came up with general idea, but somehow I could not figure out the all process of algorithm, thus got stucked on my way to the Accepted verdict (or Happy New Year verdict).

Buggy code

Ah I hate to say it, but my coding ability was not a constant function all time, but indeed, it was a combination of the most complicated functions you could think of. The point is sometimes my code was so clean, clear and short that I felt proud of the day, whereas on an another beautiful morning, I realized that today I wrote a trashy bunch of code and got WA (in other word: BURNED) in the contest.

Emotional state unstable

Oh dear, this thing was more challenging to keep in control that previous problems. Half of the official/online contests, I felt perfect and got ++ratings, but the other half were the seeds of nightmares. For the very moment I really place hope that my mental state function would got it peak in the next two days, when I participated in VOI.

Boom. In short: An imaginary doctor gave me a prescription: All symptoms were palliated, but it might cause a headache every morning until you quit. Ah good idea, I do only have three days left before I could "quit".

Hoping

------------------ -------------------------

Despite all those sucks, I do place hope in the game. I want a good prize in VOI (second prize might be acceptable), but I'd love to go beyond that. My life at high school was nearly perfect to the end, and it would be bright if I could at a shiny medal as a tiny decoration to it (oh my gosh I am illusive again). I do dare have a big dream, because somehow dreaming was the only way I got motivation when I woke up every morning, the only barriers between me and my decision to jump out of the bridge, dumping my self to Red River. I got terrible events in my life, and that was the only reason I hate my "superhuman" memory so much. But dreaming was the an exit to me, an excuse to me when I said: "Tomorrow might be a bit brighter than this.".

Last — Showing gratitude.

------------------ --------------------------------------------

Well I want to say "Thank you so much" to my best friend, also my teammate, who had guided me so well when I was just a toddler in competitive programming, to the very day, when I made such a progress. low_, without you, maybe I would be on a brighter path with no worries, no pressure that I had to suffer these days. But after all, you have shown me, that I had enough bravery to immerse myself in a foggy lifepath, that in the end, return countless rewards. I do know if you see this blog, you will say "F**k you, practice so you could code faster rather than blog faster", but I believe you will sober when reading those lines.

Conclusion

To end here, I remember the previous 10 minutes when I first wrote few words, I did realize that all of these were too sentimental for me. But I have to write, for competitive programming. For me, for my career also.

In short, good luck everyone in the educational round 58