On 12 April 2015, the Education Bureau of ICTSS organized a Crash Course for ACM ICPC. If this is the first time you heard of it, then we are terribly sorry for it. We only have about 4 day to publicize it including Friday. So that is probably the reason why you did not know about it. Anyway, around 20 participant attended the program. And on the second day we have a mini competition.
Congratulation to the winner of the mini competition. Third place, brother Khairul Azmi with 3 problem solved. Second place, brother Saad with 3 problem solved and the champion is brother Idriss with 5 problem solved.
Remember that the objective of this competition is not to find the best problem solver, but to familiarize with the competitive programming competition. Therefore the problem is not actually hard at all. It just have some tricks. If you ask me, win or lose in the mini competition, there are no significant different at all, unless someone answered question F which no one does.
The problem set for the mini competition was authored by me. I admit there are some issues with the problem set. So sorry about that. For those of you who want the dataset and sample solution, here is the link:
The problem set consist of 6 problem sorted from easy to medium. These are the summary for the questions:
- Question A is simply an A+B question. You just need to be familiar with getting the input in the correct way and output it correctly. Remember, the output need to be preceded with “Pair #N: X” where N is the pair number and X is the answer. Also there is a space between “:” and “X”.
- Question B is simply an AxB question. The trick here is that, the result will be larger than what a 32 bit signed integer can hold. Pay attention to the input size. 10^5 x 10^5 would result in 10^10 which a 32 bit signed integer cannot hold. Use the long long int data type.
- Question C is simply sorting. The objective of question C is to show you that there are built in function for basic processing like sorting and reversing. You do not need to implement your own sorting function. Also, the input size is 10^6 number. An O(n^2) sorting algorithm like insertion sort or bubble sort will result in Time Limit Exceeded (TLE) verdict. So you need an O(n log n) algorithm like heap sort or merge sort. Or you can just use the built in function in the which implementation can vary but it is required to be an O(n log n) algorithm. In the end, we consider those with TLE verdict to be correct as they have put some effort and correctly implement a sorting algorithm. Kudos for your effort!
- Question D basically require you to determine if the list is distinct. Or in another word, no repeated element. There are a lot of solution for this like making a set which track if the element already occurred or not. Or the solution in the dataset, which is to sort the list first, then iterate from start to end while checking consecutive element for equality. Most of the participant who attempted this question answer it correctly without much problem.
- Question E basically require you to find the LCM of two number. LCM is Lowest Common Multiple. Google it for more information. The solution formula is A*B/gcd(A,B). Where gcd is the Greatest Common Divisor. To calculate GCD, you can use the simple Euclid GCD algorithm. Again, google it. This question require some basic recall on Discrete Math subject.
- Question F is a classical Longest Common Sub-sequence problem which require the use of Dynamic Programming technique to run fast enough. We did not expect anyone to answer it, we just put it there to introduce the participant on one of the fancy technique that they would learn by participating in competitive programming competition.
These are the most common mistake that we found to cause a wrong verdict:
- Missing space after “:” character in question A. The answer must be EXACTLY the same.
- Using ‘system(“pause”)’ resulting in compilation error. ‘system(“pause”)’ is a hack on windows platform so that the terminal will not automatically close and you can see the result. So don’t do this, and run your program from command line to prevent the windows from closing when the program terminated. Linux operating system do not have ‘system’ function. So this will result in compilation error.
- Printing prompt like “Please enter A”. The judge is a computer. It do not understand English. It will consider “Please enter A” as an answer which is wrong.
- Using space and special character in source code name. Example, “add number.cpp”. For some reason, the judge software “pc2” are not built to be very robust. Putting a space in filename will result in error.
Again, the mini competition do not really measure a programmer’s ability very well. For that we need a proper programming competition, which we plan to have on early May in KICT. We are still working on the finer details on the competition. The good news is that it has been approved. So rest assure that once we get the details done, you will hear from us.
For those of you who did not attend the Crash Course, but are interested to join the competition, we will try our best to update this blog on what you need to know about competitive programming. So stay tuned. A forum is also available for more detailed discussion but it is not very ‘homie’ right now. Anyway, that is all I have for now. Thank you for reading. Tell your friends about this blog, and drop down any comment you have down below.