I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, 6 days ago, In English,

UPD: Editorial in Vietnamese: http://acmicpc-vietnam.github.io/2016/regional/solutions/ACMICPCRegionalVietnam2016-Editorial.pdf

Hi all,

On Oct 15th, 7pm Vietnamese time, we will have Vietnamese regional 2016 replay on Kattis.

  • The contest will last for 5 hours with normal ACM ICPC rules.
  • After the contest we'll publish editorial in Vietnamese and official solutions.
  • Teams are recommended.
  • It is not rated.

If you are not afraid of spoilers, see standings here. Team from Seoul National Univ were #3 in ACM ICPC World final 2016-2017 and LINUX from VNU were #39 in World final 2016-2017. Can you beat them? :p

The problems were prepared by I_love_Hoang_Yen, RR_PPAP, lythanh, beo_chay_so and some professors in Vietnam. The contest is uploaded to Kattis by prof.PVH.

 
 
 
 
  • Vote: I like it  
  • +54
  • Vote: I do not like it  

»
6 days ago, # |
  Vote: I like it +17 Vote: I do not like it

Could you please remove the LINUX's position from your blog post so that members of that team don't feel ashamed of their terrible performance at World-Finals-2017? :'(

  • »
    »
    6 days ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    Infact after your comment, people would be more curious to see their team (LINUX VNU whose rank was #39 in icpc world finals).

  • »
    »
    6 days ago, # ^ |
    Rev. 2   Vote: I like it +37 Vote: I do not like it

    39 at WF is fine. Just accept your past.

»
3 days ago, # |
Rev. 4   Vote: I like it +5 Vote: I do not like it

What I get for problem I:

Call f(x) the number of times that we can replace x which x / p where p is a prime. Then number x is equivalent to a pile of f(x) stones in a Misere game. The whole problem reduced to finding the number of subsequences such that their exclusive-or sum is 1, which is an easy DP problem.

What I didn't is that how to compute f(x) quickly (and I think most of the teams stuck here, too). Any idea?

  • »
    »
    3 days ago, # ^ |
    Rev. 6   Vote: I like it 0 Vote: I do not like it

    You can solve it like this: To calculate f[x]: For each prime <= 10^4, you can brute-force to count this part, and divide x for any of them. After this, any prime divisor of x will > 10^4, so x have at most 2 prime divisor. Use something like Fermat's little theorem or Miller–Rabin to check if x is a prime, then you're done.

    There are 1229 primes < 10^4, so I think this algorithm will have enough time to run. You can also do something like stop trying if x is greater than current prime^2, have a table for x<10^6 so you can look it up whenever x<10^6, ... . Because all the number we care about is >=a and <=b, so it's hard to give a and b such that it's take too long to calculate the whole sequence.

    Despite saying all that, I can't guarantee that this algorithm will pass. And I couldn't come up with your idea :(.

  • »
    »
    3 days ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    Let g[x] = x for x = [A, B]. For each prime p ≤ 106. Find the smallest st: p|C and do as follow:

    for (long long i = C; i <= B; i += p) {
        while (g[i] % p == 0) g[i] /= p, f[i]++;
    }
    
»
3 days ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

That Van Hanh Pham solved 10 out of 12 problems and the 2 problems he did not bother to solve are those almost everyone could solve. Does that means he alone could beat the best team from Seoul National University?

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    He's prof.PVH, contest uploader.

  • »
    »
    2 days ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    As above comment, he is contest uploader. He submitted to test author solution, time limit and judge programs. We tried to hide him from scoreboard but could not.