Блог пользователя I_love_Hoang_Yen

Автор I_love_Hoang_Yen, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +173
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +27 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Oh, i participate Online mirror after finishing Google Kickstart

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +26 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 4   Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
          Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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.

»
3 года назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +26 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +18 Проголосовать: не нравится

    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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Up! Open contest started 30 mins ago.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Is there any editorials for this contest ? :)

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Well, in fact I have a lot of questions lol

      How to solve B and E?

      What's the intended complexity of K?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

UPD: Nevermind, found my bug.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I_love_Hoang_Yen How to solve problem L (Looping Around) ?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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)

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve D?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.com/topic/76681/en17