nushio's blog

By nushio, 9 years ago, In English,
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.
 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

it is sufficient map<string, int> 

there is words with letters 'a'..'z' only in the input.

map<string, int> mp;

for i from 1 to n

{

read(s);

  if (mp[s] = =0) write("OK"); else write(s, mp[s]);

mp[s]++;


  • 9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    , which are all lowercase Latin letters.
    sigh... I missed it. Thank you for pointing out!
»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I didn't get problem3 in java,help me anyone