483 – Word Scramble – UVA – ACM

Analysis :


 

Solved By:                          stevenha(Sayutee)
Theory Difficulty:            easy
Coding Difficulty:            easy
Algorithms Used:             strings
Solution Description:

For this kind of problem (which never states the maximum size of the lines), never ever read one whole line then start processing! Most likely we do not have enough buffer to do that. Instead, read character by character, buffer them into a small array, as soon as we encounter a space ‘ ‘ or other white spaces, quickly reprint these characters in reverse order, and then flush the buffer. This way, we will not get out of memory error :). The pseudo code will be something like this:

Initially set word to (“”) (empty string)

While not end-of-input
Set c = next character in the input stream
If c = whitespace or punctuation then
// word is complete
reverse word
output word
Else
Add c to word
End-If

Output c
end-while


 

Solved By:                          peter
Theory Difficulty:            trivial
Coding Difficulty:            trivial
Algorithms Used:             strings
Solution Description:

Take the input line by line.

Retokenize it, reversing each word with a for loop and outputting in the same order.

Print out the modified line.


Solved By:                           wesley
Theory Difficulty:             easy
Coding Difficulty:             easy
Algorithms Used:              strings
Solution Description:

Iterate through each line. When you encounter a non-whitespace character, set an index variable to the index of that character. When you encounter a whitespace character (or end of line) and the index has been set, then reverse the characters between the set index and the current index – 1.

In Java you can make quick work of this problem using StringBuffer.

I handled space, newline, tab (\t), and carriage return (\r) as whitespace. I’m not sure if tabs or carriage returns actually show up in the input.


Code:

 

How did Anudeep Nekkanti become so good at competitive programming?

Anudeep Nekkanti, “;” key hates me the most..

I came to know about online judge for the first time in 2012 Jan. That was because of IOPC (programming contest by IIT Kanpur). It was held on CodeChef then. I tried for about 10 hours but could not solve a single problem.

2012 March, I started to do CodeChef long contest. I spent 7 days to solve 3 simple problems. March 7th 2012 was the day when I decided not to take any contest till I am confident about making into top 50.

I only knew SPOJ and Codechef . Then, I started solving problems on SPOJ sorted easy to hard. I solved about 300 problems by July 2012. Practice was the only thing I did. I used to try a problem for 2-3 hours. If I don’t get it, I tried searching for solutions on forums. I read few tutorials on TopCoder, but I did not know that TopCoder also has algorithm problems.

I participated in following August’s long contest, I was lot better this time, I could solve 7 problems. Ended 35th in Global ranking. From then I became lazy. I did not do any practice. I only did long contest every month. So, August to November, I did nothing.

With this limited exposure to programming I went to participate in ACM ICPC Regionals, Amrita. I could solve 4 problems there at onsite. I then understood that knowing how to solve is not enough, it is the ability to think and code fast that is more important.

Jan 2013, I started solving TopCoder problems. I did like about 300 Div 1 250 Pointers. 500 pointers were Aliens. Dynamic Programming was my enemy. But solving 250 pointers fast was enough to become yellow on TopCoder. I also came to know about CodeForces in Jan. I even started doing some contests there. Following Feb to July, I did very little programming. I did not see much improvement in myself.

Continue reading How did Anudeep Nekkanti become so good at competitive programming?