I_love_Hoang_Yen's blog

2020 ICPC Vietnam National Contest on Kattis
By I_love_Hoang_Yen, history, 4 years ago, In English

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:

Details of Official contest:

Problems prepared by:

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):

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

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

»
4 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

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 :)

→ Reply
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

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

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Oh, i participate Online mirror after finishing Google Kickstart

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How does team selection for WF work for colleges in Vietnam?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +26 Vote: I do not like it

    Asia rules are quite complicated..

    This year (because of covid and limited travel), there are 2 rounds:

    • Vietnam National Round: this is a prelim round. Most teams will go to Regional round.
    • Vietnam Regional Round: top 2-4 will go to WF (exact number of qualifying team depends on Asia rules which is complicated).
    • Only Vietnamese team can officially participate in VN regional.

    In other year:

    • In Asia Pacific, there are some regionals (e.g. Vietnam, Indonesia, Thailand, Taiwan, Japan, South Korea, etc). (Each regional may also have prelim round to limit number of local teams)
    • Each team can go to at most 2 regionals (no restriction).
    • Top few teams in each regional will go to WF.
    • If multiple teams from same univ qualify, the univ will decide (because they can qualify from multiple regionals).

    There are other rules such as univ with last year medal go directly to WF.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      If you qualified from one regional, you’re not supposed to go to another regional and officially participate in it right?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        No. In Asia Pacific you don't know who go to WF until after ALL regionals are done.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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. =)

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          The medalist bonus has been removed. There is no medalist bonus in WF 2020.

          → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 5   Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
»
4 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Any plans to upload the VN nationals and regionals to gym? As far as I know, kattis has not supported Virtual Participation yet.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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 =).

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    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

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Seem like the links to the CF announcement of regional and national are swapped xD

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Up! Open contest started 30 mins ago.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Is there any editorials for this contest ? :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, in fact I have a lot of questions lol

      How to solve B and E?

      What's the intended complexity of K?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        $$$K$$$'s intended is $$$O(N^4)$$$. Surely, It can be solved faster, but we intend to make it easier.

        → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I_love_Hoang_Yen is there a way to get data for this contest?

UPD: Nevermind, found my bug.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The problemset is not available in Open.Kattis, how can I make a virtual contest in Vjudge or Kattis with this problemset?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are you guys planning on making the contest public now for upsolving?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I_love_Hoang_Yen How to solve problem L (Looping Around) ?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 set in 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)

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by I_love_Hoang_Yen (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solve D?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    → Reply