UPD: Author's solutions are published here.
Hi all,
This Sunday (Nov 05, 2017), there will be ACM ICPC Vietnam National Round 2017. This is the qualification round for Vietnamese teams participating in ACM ICPC Vietnam Regional.
There will be online mirror on Kattis.
- Time: 8am Vietnamese time
- Normal ACM ICPC rules will be used.
- Standings will be frozen in last hour.
I hope that many of you will enjoy the problemset, especially the teams that will come to our Vietnamese regional. Good luck & have fun :).
For problem L, I only read the description part of the problem. And, I can't believe there are so many ACs on the scoreboard of the online mirror.
After contest, I finally found out the most important key points in the Constraints section...
Yeah, That is a tricky one. In the official contest, noone realize that and there is no serious attemp to that problem
Can you explain the solution?
Notice that the given graph is DAG, and there's no point in buying house, so this become a trivial DP on DAG problem (dp[u] is the largest amount of money one can get if they start from vertex u).
Seriously, noticing the unusual constraints is much harder than solving the problem itself (and no one in the official contest was able to do this, we all thought that this problem is an insanely hard game problem and didn't even bother finish reading the statement).
Actually, there is one more important tricky constraint that solves the problem.
106 ≤ K
While admitting that the author purposely tried to hide that key information, I am still curious why you did completely ignore the constraints section before trying to solve the problem. Being aware of how large the graph is was helpful in thinking of solution, wasn't it?
Yes, I did read the constraints til the 4th one(1 ≤ sa ≤ N, 1 ≤ sb ≤ N). And, I thought rest of the parts may be something like
no self-loop,no multiple edges, etc. as usual graph-related problem.It looks like a normal graph size(N, M ≤ 105) and 106 ≤ K seems to let the game go into some stable state. Thus, I thought I totally understood the problem and decided to skip it first.
If the graph is some special graph(tree, DAG, functional graph, etc), I thought it would be better to mention it in the description.
Anyway, the contest is still very nice!
I thought that I can't solve this problem no matter what is the constraint of N and M so I just skipped this problem without even reading the constraint.
What if N, M are at most 10 and K is at most 100? It becomes a trivial dp problem, doesn't it?
Probably I was being too haunted by the game on graph problem to a point that I skip all problem involved those. Perhaps I should practice this kind of problem more.
You should practice reading statement more. "didn't even bother finish reading the statement" is not acceptable in any ACM ICPC contest. You have 15 people hours. Read everything carefully.
I guess this is a lesson for me and also, everyone in Vietnam who participated this round. And I learned it the hard way.
I want to die.
me too :'(
Any hint for problem A? Or even better, will there be an editorial?
For problem G, I would not expect that the graph can contain many loops and many roads between 2 vertexes :'(
There will be editorial in Vietnamese. I'm writing it but keep getting interrupted by work, so it will take some time to finish.
Thanks a lot!
I'm waiting for the solution of Problem F.
F just has few simple steps:
DP to calculate how many numbers in [L, R] where digits are in bitmask S. You do this with a DP function:
f(length, digit_mask, is_lower_than_upper_bound).For a number like 1234, you actually want to add
fto all its subset (not just set {1, 2, 3, 4). You can do this with O(210) for all bitmask, but simple O(310) can pass.Now the problem becomes a combinatoric problem where you want to count number of ways to select K elements. This can be done using inclusion-exclusion.
If you still don't know how to solve it, wait until judge's code are published.
I wonder how you do in O(210)? Is it O(10 * 210).
Yes, I meant O(10 * 210).
Thanks!
Author's solutions are published here
For problem G, I also didn't know the fact for an hour. After that, I solved with parametric search for L whether there is a cycle or not.
For problem A, we can use segment tree — lazy propagation with some coefficients of arithmetic sequence for each degree in polynomials.
Did I understand problem H right? I thought that statement means finding the number of sequence {b_n} that satisfies
0 <= b_i <= a_i for all 1 <= i <= n and there are at least two k satisfies b_k = a_k (1 <= k <= n).
I submitted code and I expected the result should be TLE, but it was WA.
And the bit-wise XOR of the sequence b should be 0 so that the second player wins the NIM.
How to solve problem C (Cumulative Sum)?
It has 0 accepted submissions.
A query version of https://projecteuler.net/problem=551, if someone have some tips to the PE551, I will be thankful too...
Sorry, Mrs. Hoang Yen!!! Regarding solution of problem A, would you mind elaborating on the "update" method? Why did you take derivatives of the function? I am completely confused about that.
It's not derivatives of function. You can read editorial in Vietnamese here.
What is the approach for C, the editorial simply mentions the oeis link, with no formula/explanation as to how to calculate the sum efficiently.
Do you read Vietnamese? It says problem is too difficult, in VN only very few people can solve it, including author. Editorial authors can't solve it.
Key idea is that: sod is not too big. So if start with xxxx000...000yyy, we want to jump to xxx(x + 1)000...000zzz. Count the number of that jumping and the sum of them.
Thank you. It is clear now.
Mrs. Hoang Yen, not Mr. Hoang Yen
edited, sorry