I_love_Hoang_Yen's blog

By I_love_Hoang_Yen, 8 months ago, ,

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.

•
• +59
•

 » 8 months ago, # |   +17 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? :'(
•  » » 8 months ago, # ^ | ← Rev. 3 →   +9 Infact after your comment, people would be more curious to see their team (LINUX VNU whose rank was #39 in icpc world finals).
•  » » 8 months ago, # ^ | ← Rev. 2 →   +47 39 at WF is fine. Just accept your past.
 » 8 months ago, # | ← Rev. 4 →   +5 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?
•  » » 8 months ago, # ^ | ← Rev. 6 →   0 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 :(.
•  » » 8 months ago, # ^ |   +13 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]++; } 
•  » » » 8 months ago, # ^ |   0 Nice approach.
•  » » 8 months ago, # ^ |   0 i found out the way to calculate f(x) but didn't know about misere :(
 » 8 months ago, # | ← Rev. 2 →   +10 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?
•  » » 8 months ago, # ^ |   0 He's prof.PVH, contest uploader.
•  » » 8 months ago, # ^ | ← Rev. 2 →   +5 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.
 » 8 months ago, # |   0 Is there any way to see the running time when submitting as a spectator?