Hi,
This Sunday (Nov 15, 2020), there will be 2020 ICPC Vietnam National Contest on Kattis. This is the preliminary round before the Asia Vietnamese Regional. There will be online mirror after the contest.
Details of Online Mirror:
- Time: 1pm GMT+7
- Contest Link
Details of Official contest:
- Time: 8am GMT+7
- Contest Link
Problems prepared by:
- ngfam_kongu
- chemthan
- I_love_Hoang_Yen
- I_love_tigersugar
- laoriu
- ll931110
- khuebeo
- and some professors from Vietnam.
Contest difficulty won't be published before the contest. You can see our previous year contests below: (note that this year may be easier, more difficult or the same difficulty):
- 2019 Vietnam National; CF announcement
- 2019 Vietnam Regional; CF announcement
- 2018 Vietnam National
- 2018 Vietnam Regional
- 2017 Vietnam National
- 2017 Vietnam Regional
- Link to all ICPC Vietnam contests, some with solutions
UPD: For Vietnamese speaking folks, we will have a livestream at 8pm (GMT+7) where some problem authors will talk about solutions and other Q&A. Links to livestream will be put on VNOI page
UPD2: The problems are now on open Kattis
The problems are available in the official contest for you to read from 8AM UTC+7. But if you decided to participate in the online mirror, please refrain from reading the problems in the official contest :)
Wow.. I participated 2019 Danang regional and that was my last ICPC because now I'm graduated. Although our team was failed to promote WF, it was really good memories for me(includes sightseeing^__^)
Hope everyone in Vietnam stay safe from COVID and hope to see you again!!
Oh, i participate Online mirror after finishing Google Kickstart
How does team selection for WF work for colleges in Vietnam?
Asia rules are quite complicated..
This year (because of covid and limited travel), there are 2 rounds:
In other year:
There are other rules such as univ with last year medal go directly to WF.
If you qualified from one regional, you’re not supposed to go to another regional and officially participate in it right?
No. In Asia Pacific you don't know who go to WF until after ALL regionals are done.
We (the ICPC Asia Pacific secretaries) also don't know how many slots are allocated to Asia Pacific until several months before the world finals. Typically, we are informed in mid January -- at least one month later than any regional contest in Asia Pacific.
I would like to add that , iirc, in normal years each team in Asia-Pacific gains some number of points (based on placement) for each regional they participate in. Then the top 15 or so teams with the highest points go to WF.
Feel free to tell me if i'm wrong though.
I think that's the old rules. In latest rule (maybe since 2-3 years ago) only sites have scores.
Feel free to tell me if I'm wrong though. =)
The medalist bonus has been removed. There is no medalist bonus in WF 2020.
It's what they claimed. But things in practice work more similar to what I_love_Hoang_Yen has said. They claim they have some formula to calculate the WF qualification sequence but seems all coefficients are assigned after the regionals:( We only know the winner of each site qualifies and other slots are allocated according to the magic site score.
I've re-read the qualification rules for 2019 earlier today and I can confirm. For those who need the details:
Basically each regional is assigned a weight, which I will call S.
For each performance of a team at a regional, they are given a score, equal to (rank-1)/(S+0.02*(number of foreign teams in that regional)).
Then the overall score for each team is the score of their lowest-scored performance, and the top X teams with the lowest scores qualifies for WF.
So while technically teams are still qualified based on a final standing, this system in practice gives each regional a number of slots to WF, based on its weight (higher weight=more teams qualified.) And the winner of each regional is guaranteed a WF slot (since their score would be equal to 0.)
And the 0.02*(number of foreign teams in that regional) is apparently to promote foreign participation.
The site scores are based on the number of teams and the numbers of universities that solving at least one problem in the preliminary contests and the regional contests. In previous years, the rules also defined how to calculate the site scores. However, the Asia director might magically adjust the site scores without changing their order.
Any plans to upload the VN nationals and regionals to gym? As far as I know, kattis has not supported Virtual Participation yet.
On Kattis you can select some problems and create your own contest. Though you won't see other participated teams in it.
Maybe in future (though I don't have any plan yet) I will write some tool that can automatically add Kattis problems to Polygon. If anyone already wrote such tool, please let me know =).
Vjudge has a virtual contest functionality. You can clone the contest there and participate.
Here is an example contest from last year. All the ghost standings are available
Wow, never known it. Thanks.
Seem like the links to the CF announcement of regional and national are swapped xD
Fixed. Thanks.
Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).
Up! Open contest started 30 mins ago.
Is there any editorials for this contest ? :)
The plan is to have editorials in Vietnamese only. If you want to know about solution of some problem, you can ask here, and maybe some of us can comment.
Well, in fact I have a lot of questions lol
How to solve B and E?
What's the intended complexity of K?
$$$K$$$'s intended is $$$O(N^4)$$$. Surely, It can be solved faster, but we intend to make it easier.
Got it, thanks.
B: The cells that you block + wall should form a path from (left & bottom edge) to (right & top edge)
E: It's standard Segment tree problem. In each node, you should store expression value, left most number, right most number, position of last +/- sign, and some other things.
Thx, problem B is cool.
I_love_Hoang_Yen is there a way to get data for this contest?
UPD: Nevermind, found my bug.
The problemset is not available in Open.Kattis, how can I make a virtual contest in Vjudge or Kattis with this problemset?
Are you guys planning on making the contest public now for upsolving?
Also replying to tdas above:
Yes, we want to add the problems to open.kattis.com, but it requires staff from Kattis to upload them, so I don't know when that will happen.
For normal upsolving, I think you can submit normally to vietnam-national20.kattis.com or vietnam-national20open.kattis.com? I can see some submissions after contest.
Not really sure about requirements for virtual contest on vjudge. If it requires all problems to be on open.kattis.com, I think you will have to wait..
tdas tfg Problems are on open Kattis now
I_love_Hoang_Yen How to solve problem L (Looping Around) ?
Here's how I solved the problem:
Every point needs a horizontal ray and a vertical ray going out of it. We need to decide if the horizontal ray should go left or right, and if the vertical ray should go up or down. It turns out we can decide greedily.
Group the points by y-coordinate in rows, and process the rows in increasing order of y-coordinate. Inside each row we sort the points by x-coordinate. The first point must send its horizontal ray to the right, as there is no point to the left of the first point. Consequentially the second point must send it horizontal ray to the left to "catch" the first point's ray. This means that we connect the 1st and 2nd points, the 3rd and 4th and so on. If the number of points in a row is not divisible by 2 the answer is NO.
Now for the vertical rays. The first processed point cannot send its vertical ray downwards, as there are no points below it. We store that a point at its x-coordinate sends a ray upwards in a datastructure. If you have access to a balanced search tree (like
setin C++), use that. When we process a point we check if there is a point directly below it sending a ray upwards. If there is, we must send our vertical ray downwards to "catch" it, otherwise we insert an upwards ray in the datastructure.One thing we have to be careful of is cutting an upwards ray with a horizontal line. This would mean that the lines in the result would intersect, which makes it invalid. When we connect two points (x1, y) (x2, y) with a horizontal line, we check in our datastructure if there exists an upwards ray with x1 < x < x2. If yes, the answer is NO. If you do not have access to a balanced search tree (e.g. if you use Python), you can use a segment tree/fenwick tree with index compression to answer these queries.
When we are done processing the points, the answer is NO if there are still any uncaught upwards rays in the datastructure.
Finally we must make sure that graph we created only has one component. This can be checked with a simple graph traversal algorithm like BFS.
Complexity:
O(N log N)Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).
how to solve D?
Root the tree arbitrarily and compute 1) the longest path to a leaf and 2) diameter in each subtree with DP.
We can now consider each edge of the root for removal and quickly compute the answer using the values we computed previously. We can also quickly move the root to a neighbouring node and update the data accordingly. In this way we can consider all edges for removal and take the best one.
See also: https://codeforces.net/topic/76681/en17