Suhendry’s Blog

When in doubt, do math ;-)

ACM-ICPC 2008 Jakarta - Problem Set & Analysis

with 26 comments

Well… I was FORCED by Felix Halim to write this review! Every time I went online in my YM, he bugged me and kept asking about the blog. Argghhh! He sure has the talent to be a debt collector :-) ! Now suddenly I feel to write my blog in English! Yes, English! Err.. maybe it will be more Inglish than English. No complain, no protest, no typo-report, no grammar-report! Just read, leave comment or discuss the problems >:)

You can download the problemset here:
ACM-ICPC 2008 Jakarta - Problem Set (634 KB)

REALLY THANKS to all the authors team: Andrian Kurniady, Andoko Chandra, Evan Leonardi, Felix Halim, Ilham Winata Kurnia and Ryan Leonel Somali; who have helped me to prepare all the problemset, solutions and test-data for this contest. And also for Timotius Sakti who have coded Java solution for some problems.

Pages: 1 2 3 4 5 6 7 8 9 10 11

Written by suhendry

November 19th, 2008 at 6:01 pm

Posted in Algorithm, Event

« ACM-ICPC 2008 Jakarta (20-21 Oct)
ZJU 3060 - Evil Game »

26 Responses to 'ACM-ICPC 2008 Jakarta - Problem Set & Analysis'

Subscribe to comments with RSS

  1. Hi, shouldn’t it be “Rabin-Karp” instead of “Booyer-Moore”?

    Ardian KP

    20 Nov 08 at 10:35 am

  2. ooops, you’re right :-D , thanks!

    suhendry

    20 Nov 08 at 11:20 am

  3. Hi, I’m a member of team Seed.
    It’s a great problemset, and it’s really responsible for the author team to write such detailed solutions after the contest.

    Here’s some of our experience:
    1. We use segment tree to solve E :(
    2. We solved I using DFS(4^n), only add a few pre-cut.

    Would you mind if I ask for the testdata of the contest, so we could use it for practice, and I could test my program for D & H.
    My email is: chy_charlie@hotmail.com

    ChengYu

    28 Nov 08 at 8:17 pm

  4. Oh, and also the time limit for each problem.
    Thanks a lot.

    ChengYu

    28 Nov 08 at 8:25 pm

  5. @Cheng Yu:

    1. Yeah, some other teams also used segment tree to solve E :-D
    2. Hm, interesting :-?

    Btw, I have sent an email for you :-) We will also upload the problemset and testdata to baylor’s archieve.

    suhendry

    2 Dec 08 at 5:04 pm

  6. Don’t worry, I won’t paste the exact value of 3^^^^3 as I know it wouldn’t fit in here… instead I would like to paste the exact values of the so-called “? scrapers” from this site, which make those hyper-mod numbers above insignificant http://www.polytope.net/hedrondude/scrapers.htm

    Ryan Leonel Somali

    5 Dec 08 at 3:54 pm

  7. i’am trying to solve the problem I using brute force , but my answer still judge wrong answer.
    is there any trick on the brute force one?
    still curious ^^

    Indra Suryatama

    6 Dec 08 at 11:11 pm

  8. @indra
    what problem you’re talking about?

    Felix J

    8 Dec 08 at 3:07 pm

  9. @Indra Suryatama:
    No, there isn’t any tricky case. It means your bruteforce solution was wrong :-)

    @Felix J:
    Clearly he’s talking about problem “I”

    suhendry

    9 Dec 08 at 2:27 pm

  10. Yap i’am thalkin about problem I….
    hmm still curious….
    is the judge test case can be downloaded? cause still curious in which test case my solution get wrong hehehe
    maybe my brute force solution was wrong….
    but until now i still dunno which test case hahah
    because at that time i make several test case and it passed hehehhehehe ^^
    maybe you can give me some advice heheh ^^

    Indra Suryatama

    9 Dec 08 at 11:12 pm

  11. by the way …. you said
    “New update. I have just tested the brute force solution and it did not pass the time-limit.”
    so we cant solve problem I with brute force solution…?
    hmmm hahah so i must moved on from BF solution tu DP solution ya… heheheh
    tq

    Indra Suryatama

    9 Dec 08 at 11:19 pm

  12. @Indra Suryatama:
    check your mail.

    Your bruteforce program failed on some cases. I suspect that your program didn’t properly check whether a combination/solution is possible to happen or not.

    If you do plain 4^N brute force then you’ll surely get TLE :-)

    suhendry

    18 Dec 08 at 6:44 pm

  13. Hi Suhendry!
    Great reviews for the problems! You mention in one of the comments that you’ll sen the dataset to the Baylor Archive. If you mean the CLI Live Archive, we didn’t recieved anything yet. We’ve already uploaded the problem descriptions, so having the datasets will be very very helpful for us.

    Please, contact me at carlos.marce@gmail.com

    Thanks!

    Carlos

    10 Jan 09 at 5:05 pm

  14. Hi Carlos!

    No wonder the problemset is still not available in Live Archieve, the email address was wrong…

    check your mail, thanks :-)

    suhendry

    10 Jan 09 at 5:45 pm

  15. Thanks to Carlos, now the problemset is available in CLI Live Archieve:

    http://acmicpc-live-archive.uva.es/nuevoportal/region.php?r=as7&year=2008

    enjoy it :-)

    suhendry

    10 Jan 09 at 9:31 pm

  16. Hi Suhendry! Could you please send the testcase to me for my practice these problems? I don’t know where the baylor’s archieve is…could you tell me? Thanks!
    mail: f7495622@mail.ncku.edu.tw

    electron

    4 Feb 09 at 7:34 pm

  17. Oh i means where can i find the testcase in the baylor’s archieve… i can’t find the correct link. Could you please tell me ??

    electron

    5 Feb 09 at 6:47 am

  18. Thanks a lot for this great and detailed review!

    If only every regional had these type of reviews :(

    Also I really loved the problem set and I can feel that it especially enriched my DP skills. Thanks to all problem setters.

    Seckin

    24 Feb 09 at 1:54 am

  19. hi :)

    I’m Ivan from the team from Ateneo de Manila University, Philippines. I was wondering if you can send the testdata to my email? I’d use it to analyze our solutions to the problems, and for our future training sessions as well.

    My email is ivan_pisay07@yahoo.com.

    And oh, your review of the problems is great! Thanks for this :)

    Ivan

    28 Feb 09 at 5:31 am

  20. So what’s the story behind problem I? :D

    Felix Halim

    21 Aug 09 at 11:54 pm

  21. Hi,

    will you please send testdata to me for our training contests?

    Thanks,

    – Kamran

    Kamran Bavar

    23 Aug 09 at 6:11 am

  22. plz ,Explain 3rd test case according to your algorithm,
    i,e min{ (ai-bi)mod 10,(bi-ai) mod 10} , then MST….

    rizoan toufiq

    27 Nov 09 at 4:27 am

  23. for problem A

    plz ,Explain 3rd test case according to your algorithm,
    i,e min{ (ai-bi)mod 10,(bi-ai) mod 10} , then MST….

    rizoan toufiq

    27 Nov 09 at 4:29 am

  24. The link for the CLI Live Archive is not working for me, can anyone update it?

    John Bull

    5 Jun 10 at 1:46 pm

  25. @rizoan toufiq
    First, compute the cost from each state to other state.

    For example,
    1234 to 5678 =
    min((1-5+10) mod 10, (5-1+10) mod 10) +
    min((2-6+10) mod 10, (6-2+10) mod 10) +
    min((3-7+10) mod 10, (7-3+10) mod 10) +
    min((4-8+10) mod 10, (8-4+10) mod 10) +
    = 4 + 4 + 4 + 4 = 16

    The matrix cost will be:
    0 16 12
    16 0 12
    12 12 0

    The MST for above graph is 24. Connect the MST with (0,0,0,0) and you will get 26.

    suhendry

    2 Jul 10 at 6:40 pm

  26. @John Bull

    The CLI Live Archive link is working…

    suhendry

    2 Jul 10 at 6:41 pm

Leave a Reply