Nov 112014

A. Choosing a Smartphone

Author: Suhendry Effendy
Prepared By: Suhendry Effendy, Hutomo Widjaja
(link to problem A)

This is the easiest problem in the contest. Attention please, this specific write up (Problem A) is not intended for any experienced contestants; this problem is easy, any experienced contestants will surely be able to solve this under 5 minutes, 10 minutes at most

Abridge problem statement: given an array of N integers, determine its category (based on the sum of all elements). This problem simply asked you to sum all the elements, and classify the accumulated sum into one of 4 available classes:
     0 < SUM ≤  16,000 : ANS = 16GB
16,000 < SUM ≤  32,000 : ANS = 32GB
32,000 < SUM ≤  64,000 : ANS = 64GB
64,000 < SUM ≤ 128,000 : ANS = 128GB

Following is an example of accepted C++ solution for this problem.

#include <cstdio>
int main() {
  int T;
  scanf( "%d", &T );
  for ( int tc = 1; tc <= T; tc++ ) {
    int N;
    int arr[105];
    scanf( "%d", &N );
    for ( int i = 0; i < N; i++ )
      scanf( "%d", &arr[i] );
    int sum = 0;
    for ( int i = 0; i < N; i++ )
      sum += arr[i];
    printf( "Case #%d: ", tc );
    if ( sum <= 16000 ) puts( "16GB" );
    if ( 16000 < sum && sum <= 32000 ) puts( "32GB" );
    if ( 32000 < sum && sum <= 64000 ) puts( "64GB" );
    if ( 64000 < sum && sum <= 128000 ) puts( "128GB" );
  return 0;

There were a lot of wrong submissions (from, which I assume, beginner teams) to this problem. Most of them have logic errors in their code. To all beginners (not all these can be applied to experienced team), you should always remember to:

  • Follow the EXACT output format. If the problem asked you to output “Case #1:”, then output it exactly, DO NOT output “Case # 1:” or “Case#1:”. Difference in white spaces will cost you a Wrong Answer.
  • If you got “No – Wrong Answer”, it simply means your code did not produce the correct output. Do not waste your time by arguing that you have tested your code and they’re correct. The judges have their own test data prepared to test the contestant’s submission. Of course they cannot share this test data with you, it’s secret, but you can be sure that the test data complies 100% with the problem’s constraint. If the problem said that N ≤ 100, then in judge’s test data, N will surely be ≤ 100. This also implies that you don’t need to do any input validation procedure. If you got “No – Wrong Answer”, it means your program did not produce the correct output for the judge’s test data, which means something is wrong in your code.
  • The same also applies if you got “No – Runtime Error” or “No – Time Limit Exceed”. Runtime Error (RTE) means your program crashed when run with judge’s test data. Time Limit Exceed (TLE) means your program took longer than allowed time limit to produce the output; in other words, your program is not efficient enough to pass. What is the point of TLE? Imagine if one contestant argue that his code is correct, but you have to wait for 10 hours (or worse, years) for it to produce the output. In worst case, your program caught in infinite loop (you know … halting problem – determining whether a program will terminate – is undecidable). In some problem, we also want the contestant to device an efficient algorithm to solve the problem, e.g. brute-force compared to smart and fast algorithm.
  • C++ users, make sure you first compile your code using console (command prompt in Windows or shell in Linux) before submitting. Usually this problem comes from teams who used IDE (e.g., DevC++, Code::Blocks, Microsoft Visual C++, Borland C++ – anyone using this? –, etc.) to code their solution. Your IDE might have different compile option than what is used by the judges (specified on the website: g++ -Wl,-stack=0x4000000 file.cpp -o file). What is the effect? In some cases, IDE can automatically include the needed libraries when you forgot to specify it in your code (#include). If you submit such code, then you might get “No – Compile Error”. Also, it’s better if you have the same compiler version as one used by the judge (we used MinGW 4.4.1). C++ compilers such as VCPP or BC are usually not compatible with MinGW. I understand that this might be confusing for you. But again, learning all these stuffs will help you a lot not only in programming contest, but in your future as programmer as well.

There are 961 submissions have been made for this problem, in which 306 teams managed to get accepted. The first team who solve this problem is Sylph (minute 3) from Bina Nusantara University.

  27 Responses to “ACM-ICPC INC 2014”

  1. “One popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang

  2. komen untuk prob J

    β€œOne popular approach was by first sorting all the strings and pair each succesive string whenever possible”, kode saya spt itu, hanya saja pasangkan dr yg terpanjang

    • koreksi, prob G

    • Ngga, kode kamu nggak seperti itu. Approach kamu itu jadi sama dengan approach greedy yang bener (pasangin dari leaves) — string yang paling panjang saat itu pasti leaf.

      Yang dimaksud “pair each succesive string whenever possible” itu comparenya bener-bener cuma sama 1 string di sebelahnya aja (sorted); sedangkan kamu compare dengan yang panjangnya lebih pendek.

  3. a bit curious about problem H. Did you use the real Kawal Pemilu data for judge’s test case? πŸ˜€

  4. nice problem, nice editorial, pretty helpful, thx πŸ™‚

  5. saya penasaran dgn problem yg blm sempat saya kerjakan (dan AC), apakah mungkin akan diupload ke situs online judge ?

    saya dpt ide sederhana utk problem J dgn menelusuri apakah suatu nilai bisa jadi pivot (menjadi ‘L’), setelah itu cek apakah bs dr index tersebut menjadi good segment, jika tidak cetak impossible, kode saya : [[REMOVED]]

    thx koreksinya πŸ˜€

  6. How about ACM-ICPC 2014 Jakarta write up?? Will it be published?

  7. How can I get input data ?

    Thank you for sharing.

    • Ah… I didn’t notice this comment before >.< I'll not share the input data publicly. You can test your solution in some online-judges, e.g., tokilearning or joj. (I think) I have sent the test data to the admin on those sites.

 Leave a Reply

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>