Monday, October 29, 2012

UVA: 10082 Programming Challenges (Skiena & Revilla) Volume-3

UVA:10082 - WERTYU


Background- WERTYU is keyboard key position based encoding. This problem has taken least time to code and I found it to easiest one. This has 0.008 of run time over uva judges input but ranking is pretty bad. C++ implementation is exactly one line of code - 

C Implementation - 
#include <iostream>
#include <algorithm>
#include <iterator>
using namespace std;

char CODE[]={0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14,\
15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30,\
31, 32, 33, 34, 35, 36, 37, 38, 59, 40, 41, 42, 43, 77, 48, 44,\
46, 57, 96, 49, 50, 51, 52, 53, 54, 55, 56, 58, 76, 60, 45, 62,\
63, 64, 65, 86, 88, 83, 87, 68, 70, 71, 85, 72, 74, 75, 78, 66,\
73, 79, 81, 69, 65, 82, 89, 67, 81, 90, 84, 90, 80, 93, 91, 94,\
95, 96, 97, 98, 99, 100, 101, 102, 103, 104, 105, 106, 107, 108,\
109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 119, 120, 121,\
122, 123, 124, 125, 126, 127};

inline char Decipher(const char& ch) {
    return CODE[ch];    
}

int main() {
    transform(istreambuf_iterator<char>(cin.rdbuf()), istreambuf_iterator<char>() , ostream_iterator<char>(cout), Decipher);    return 0;    
}
After thoughts - 
1. I am unable to think of any optimization.
2. Some how I am forced to think that UVA is broken because it is not possible to achieve 0.000 timing if the above implementation gives 0.008 sec.
3. There is one line of code and all the operations are o(1). Reading and Writing is done in O(n) time and that is the minimum complexity anyway unless you know inputs in advance.

No comments:

Post a Comment