### nushio's blog

By nushio, 10 years ago, ,
This was my first time on Codeforce. I'm amazed to see a contest maintained by a single person (maybe a team?), writing down problems and judges at this pace.  Thank you,  Mike Mirzayanov , for the contest site!

### Watermelon

This is an easy problem. Any even number >=4 is OK. B.t.w. I love watermelons, too!

### Before an Exam

This is easy, too. First, fill the minimum requirement and then fill the excess time in any order you like. I even used very unefficient algorithm O( sumTime ) .

### Registration System

This problem made me stop for a while to think of an appropriate data structure. If I implement the problem statement literally it'll be an O(n^2) algorithm and it will TLE. e.g. when all the 105 people register with "same_string + digits " name, like ["a", "a3", "a", "a4", "a12", "a", ...] I hope my solution, still in queue, is O(n log^2 n) and correct...

P.S. It was Accepted!! (2090ms / 5000ms, that was close!)

My basical idea is to have an unordered_map<string, set<int> > db so when one tries to register a name , I'll look db [name ] for a vacant suffix. Basically I have to lookup by brute force (1,2,3,4, ... ) but if I record the last_results , as the startpoints of the brute force search next time, the total number of continued brute force search step is O(N).

Some subtleties: username "a123" will conflict with the fourth request for "a12"; "a0" doesn't conflict with "a"; etc...

So, I break down a registered username as long as its last character is a digit, and update db [name ] and last_results , properly. It goes like:
db["a123"].occupy_raw();
db["a12"].occupy(3);
db["a1"].occupy(12);
db["a"].occupy(123);

### Mysterious Present

I thought O(n^2) will do for this problem. If you sort all the envelopes by their width, you'll know that an envelope won't fit in any of its predecessors. Somehow, I got WA.