### nushio's blog

By nushio, 11 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.

• +1

 11 years ago, # |   0 it is sufficient map there is words with letters 'a'..'z' only in the input.map mp;for i from 1 to n{read(s);  if (mp[s] = =0) write("OK"); else write(s, mp[s]);mp[s]++;}
•  11 years ago, # ^ |   0 , which are all lowercase Latin letters. sigh... I missed it. Thank you for pointing out!
 » 2 years ago, # | ← Rev. 2 →   0 I didn't get problem3 in java,help me anyone
 » 10 months ago, # |   0 can someone help me explaining 2nd problem please? :(
 » 9 months ago, # |   0 hi, in the watermelon problem i dont understand why even number should be greater than 4. For example if w is 6, cant it be divided as 2+4.
•  » » 9 months ago, # ^ |   0 6 is greater than 4
•  » » 9 months ago, # ^ | ← Rev. 2 →   0 I think you made a little mistake. 6 is greater than 4. If you still struggle in this problem, I can give another solution.if(w%2!=0 && w==2) printf("NO");