Two languages, one Cup. Reflections on the RCC 2016 Rules

Hello, Habr! Here is a small post about the ongoing Russian Code Cup 2016 , or rather, my thoughts on which one of the tasks of the warm-up round prompted me.

Technical rules for the round are described in detail here . I will not copy them all, I will highlight only two points:

• You can send solutions in different languages ​​(Java, Python, C / C ++ / C ++ 11, C #, Perl, PHP, Ruby, D)
• All tasks have a limit on the time of execution of decisions

It's about the task "A" Secret code (direct link) :

Time limit of 2 seconds
256 MB memory limit

Description

Marty is now in the past and wants to return home in 1985. He had already fallen in love with his parents and found plutonium. All that is left to do is turn on the time machine and hit the road. Here Marty is waiting for another test. To enable the time machine, you must enter the secret code. Only Doc knows the secret code. Marty is aware that all the characters that make up the code are different, and he also knows the number of characters. While Marty waits for Doc to arrive, he tries to guess the code and enters various combinations of characters.

Your task is to write a program that, for each request, Marty issues two numbers — the number of valid characters that stand in their positions, and the number of characters that appear in the code, but they stand on the wrong positions.

Input Format

The first line contains the string s - the secret code. The code consists of Latin capital letters and numbers, all the characters in the code are different.

The second line contains a positive integer n (1 ≤ n ≤ 10 ⁵ ) - the number of Marty attempts.

Each of the next n lines contains the next combination that Marty enters. The combinations also consist of Latin capital letters and numbers. The characters in each combination are different. The length of each combination coincides with the length of the secret code.

Output format

For each request, Marty print two numbers a and b, where a is the number of correct, b is the number of characters that are found in the code, but are in the wrong positions.

Example

Input data:
BACKTO1985
3
BACKTO1958
BACKON1985
TOYEAR1985
Output:
8 2
8 1
4 3

Decision

The problem is not complicated. Virtually no tricks to solve is required.

Enumerate the combinations, comparing each with the secret code character-by-character. The next pair of symbols has coincided - we increase a , otherwise we see if this symbol is present in the secret code (we are looking for a conditionally logarithmic time, having first decomposed the secret code into an associative array with key symbols). If present, increment b .

Here is a simple Ruby solution, (the code is exactly the one I sent during the round):

input = STDIN.read.split("\n") code = input[0] tries_count = (input[1]).to_i tries = input[2,tries_count] #puts code #puts tries_count #puts tries code_a = code.split(//) code_h = Hash[code_a.map {|x| [x, 1]}] #puts code_h tries.each do |t| total_right = 0 missed_right = 0 t.each_char.with_index do |c, i| if c == code[i] total_right += 1 else missed_right += 1 if code_h.has_key?(c) end end puts "#{total_right} #{missed_right}" end 

What was my displeasure when I received in response to Time Limit Exceeded . Moreover, the funny thing is that later, at the end of the round, I decided to send the same code again for the interest. And he passed the test! That is, most likely, performed on the verge of a time limit. I decided to figure it out.

Wrote an identical (as far as possible) solution in C ++:

 #include <iostream> #include <map> int main() { std::string code; std::getline(std::cin, code); std::string s_tries_count; std::getline(std::cin, s_tries_count); int tries_count = std::stoi(s_tries_count); std::string tries[tries_count]; for(int i = 0; i < tries_count; i++) { std::getline(std::cin, tries[i]); }; std::map<std::string, int> code_h; for (char& c : code) { std::string s(c, 1); code_h.insert(std::make_pair(s, 1)); } for (std::string t : tries) { int total_right = 0; int missed_right = 0; for (int i = 0; i < t.length(); i++) { if (t[i] == code[i]) { total_right++; } else { std::string s(t[i], 1); if (code_h.count(s)) { missed_right++; } } } std::cout << total_right << " " << missed_right << std::endl; } return 0; } 

Yes, the code is bad, not least because of these conversions from char to string , but I set the goal to repeat the solution in Ruby as much as possible.
<CaptainObseness>
So, the code in C ++ was executed much faster than in Ruby!
</ CaptainObseness>

Shortly after the end of the round, test input data sets became available, and I downloaded test No. 17, where I received Time Limit Exceeded for the first time, it contained the code word OPYB4R7JNHVGEKC3I6285TU90ASMFXLZW1D and 94432 combinations.

Performance measurements

C ++ collected on g ++ 4.8.4
Script:

 g++ -x c++ -std=c++0x -O2 -o ./solution1.a solutions/solution1.cpp && echo "solution1.cpp (with diff):" && time diff <( cat data/output.txt ) <( ./solution1.a < data/input.txt ) && echo "solution1.cpp (> dev/null):" && time ./solution1.a < data/input.txt > /dev/null 

Conclusion:

 solution1.cpp (with diff): real 0m0.411s user 0m0.341s sys 0m0.171s solution1.cpp (> dev/null): real 0m0.347s user 0m0.319s sys 0m0.028s 

Ruby version 1.9.3
Script:

 echo "Ruby base solution (with diff):" && time diff <( cat data/output.txt ) <( ruby solutions/solution1.rb < data/input.txt ) && echo "Ruby base solution (> dev/null):" && time ruby solutions/solution1.rb < data/input.txt > /dev/null 

Conclusion:

 Ruby base solution (with diff): real 0m1.422s user 0m1.416s sys 0m0.009s Ruby base solution (> dev/null): real 0m1.413s user 0m1.404s sys 0m0.008s 

As you can see, more than threefold difference in operating time, with, in general, a similar algorithm.
The entire set (input / output data for test No. 17, cpp and rb sources, scripts for building and measuring performance (only * nix)) was written down here on the githab .

You might think that I have not yet closed the CaptainOht tag, but here are the conclusions that I put forward for discussion:

• The situation is absolutely fair for the real world, where each language has its own tasks.
• However , in olympiad programming, I consider this situation somewhat unfair
• In the championship, it’s as if the tools are laid out in front of us to choose from, they say, take any, a matter of taste; in fact, one of the tools is noticeably more efficient than others
• Yes, of course, Ruby has a gain in speed and ease of writing code directly, when a solution in your head has already been found
• But , I bet, if you plant alongside equally competent Ruby and C ++ specialists, the first one, if they write the code faster, then only within the framework of statistical error
• By setting a rigid framework for the execution of the decision code, the organizers, in fact, make some languages ​​"more equal" than others, although it would seem that the goals of the Olympiad are slightly different
• What would I suggest from my bell tower? Evaluate the computational complexity of solutions ( Big O )! Watch how the speed of code execution changes with an increase in the amount of input data n . And, for example, if the execution time grows more perceptibly faster than linear O (n log (n)) , the decision to reject
• And yes, protection from cunning comrades with solutions in constant O will be needed (100500)

Thanks for attention! It will be very interesting to know your opinions on the topic.