Nov 192008
 

Hyper-Mod

Author: Ryan Leonel Somali

This was the hardest problem in the contest. I could not solve this problem without any help or hint from the author (Ryan Leonel).

Hyper operator of level n is defined recursively as a repetition of level (n – 1) hyper operator. I will note hyper operator of level n as hypern (e.g. hyper2, hyper3, etc.).

We can write each of hypern as:

hyper0(a,b) = a(0)b = 1 + b
hyper1(a,b) = a(1)b = a + b
hyper2(a,b) = a(2)b = a + a + ... + a  = a x b
hyper3(a,b) = a(3)b = a x a x ... + a  = a^b
hyper4(a,b) = a(4)b = a^(a^(...^a))    = a^^b
hyper5(a,b) = a(5)b = a^^(a^^(...^^a)) = a^^^b

and so on…

I’m sure most of you are able to solve hypern-mod for n <= 3 (addition, multiplication and exponentation). If you have solved UVA 10692 (Huge Mod), then solving hyper4-mod would be easy for you, as UVA 10692 is a generalized version of hyper4-mod. The figure below will give you some ideas about how to solve hyper4-mod (tetration).

hyper4-mod: (2^(2^(...^2))) mod 40

hyper4-mod: (2^(2^(...^2))) mod 40

Any hypern can be expressed by hyper(n-1). It means that any hypern for n >= 4 can also be expressed by hyper4. Let me show you some examples:

2^^^3 = 2^^(2^^2)
      = 2^^(2^2)
      = 2^^4

2^^^4 = 2^^(2^^(2^^2))
      = 2^^(2^^(2^2))
      = 2^^(2^^4)
      = 2^^(2^(2^(2^2)))
      = 2^^(2^(2^4))
      = 2^^(2^16)
      = 2^^65536

3^^^^3 = 3^^^(3^^^3)
       = 3^^^(3^^(3^^3))
       = 3^^^(3^^(3^(3^3)))
       = 3^^^(3^^(3^9))
       = 3^^^(3^^19683)
       = ...... I give up!

Ryan, If you read my blog then I beg you… please DO NOT paste the exact value of 3^^^^3 in my blog’s comment!!

To solve hypern-mod for n >= 5, you’ll need this amazing fact: “The cycle size in each exponentation level will decrease VERY FAST!”. What make it more amazing is, the maximum level to decrease the cycle size from m to 1 never reaches 20 (for any valid input in this problem). It means that the value of 2^^99999999 mod m will be the same as 2^^20 mod m. To be exact, any hypern(a,b) mod m where n >= 4 and b >= 20 will be the same as hyper4(a,20) mod m. This fact REALLY decreases the search space significantly.

No team solved this problem.


  35 Responses to “ACM-ICPC 2008 Jakarta – Problem Set & Analysis”

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

  2. ooops, you’re right 😀 , thanks!

  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

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

  5. @Cheng Yu:

    1. Yeah, some other teams also used segment tree to solve E 😀
    2. Hm, interesting 😕

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

  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

  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 ^^

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

  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”

  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 ^^

  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

  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 🙂

  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!

  14. Hi Carlos!

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

    check your mail, thanks 🙂

  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 🙂

  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

  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 ??

  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.

  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 🙂

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

  21. Hi,

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

    Thanks,

    — Kamran

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

  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….

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

  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.

  26. @John Bull

    The CLI Live Archive link is working…

  27. You did a good job.

  28. hi everyBody…

    i have a problem about Palindrome number .
    i want to find a Palindrome number By index of numbers ( numbers are subset of natural numbers = N )
    like this :::

    input | output
    9 | 9
    10 | 11
    29 | 202
    40 | 313
    & so on…

    i want an algorithm to find this

    (someone said : e.g. : if input = 12 /// output => 12 + 21 = 33
    or 64= > 64+46 = 110 go on = > 110+011 = 111 /// But not true for all numbers)

    please help me

    • //in c++
      #include
      #include
      using namespace std;
      int main()
      {
      char s[22],a[20],b[20];int i,j;
      cin>>a;
      for(i=0,j=strlen(a)-1;i<strlen(a);i++,j–)
      b[j]=a[i];
      for(i=0;i<strlen(a);i++)
      s[i]=(a[i]-48)+(b[i]-48)+48;
      for(i=0;i46 && s[i]<58)
      cout<<s[i];
      cout<<endl;
      return 0;
      }

  29. mohammed just out of curiosity what do you need this algorithm?

  30. I got TLE in ICPC team strategy, altough I’ve used DP bitmask. Can someone suggest me please..

  31. Hi Suhendry, I praticed solving this contest some days ago and I used brute force for this problem (ICPC Team Strategy). I tried all the possibilities and I got AC in 2.6s. After that, I add only one line of code for checking some variables and then I submitted again and got AC in 0.104s. I’m really surprise! 🙂

  32. HI!!
    I have some problem with ICPC team strategy : (
    I use DP + bitmask , run for all the state by 5*for,
    and the time complexity is the same as yours , but still TLE : (
    Is there any cut or tip ?
    thanks.

  33. Can you please email me the test data for the contest , we are a team from Egypt and we will use this data to prepare for the coming regional contest
    here is my e-mail: kamokim2@gmail.com

    Thanks

  34. Could you mind if I you send me test data of the contest specially D and F , so my team could use it for practice.

    E-mail : yasser.csd@gmail.com

    Thanks

 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>

(required)

(required)