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

Автор xiaowuc1, история, 9 лет назад, По-английски

Hi all,

The first contest of the 2017-2018 USACO season will be running from December 15th to December 18th. Good luck to everyone as we start our season! Please wait until the contest is over for everyone before discussing problems here.

Update 1: The contest is now live!

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

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +11 Проголосовать: не нравится

How to register on this contest?

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

They say "pipe stdin / pipe stdout", but actually it's not. File names for Platinum :

  • Standing Out from the Herd : standingout.in / standingout.out
  • Push A Box : pushabox.in / pushabox.out
  • Greedy Gift Takers : greedy.in / greedy.out

It'd be great if someone share the filenames for other divisions too.

  • »
    »
    9 лет назад, скрыть # ^ |
    ← Rev. 2  
    Проголосовать: нравится +25 Проголосовать: не нравится

    This has been resolved.

    EDIT: I'm passing along a request from the contest admin, who would also like to request that for any sorts of technical issues, to contact directly as opposed to posting about them on social media. The admin isn't actively tracking all forms of social media where these issues might be discussed but will respond to any direct queries, and hopes that contestants who notice issues will escalate them properly so everyone can have a smooth contest.

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +8 Проголосовать: не нравится

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

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

UPD: found out

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

Is there a way to submit a solution after I have finished my window (to check if a solution is correct) or I must wait until the whole contest finishes?

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

How to solve G2: Barn Painting?

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

How to solve Platinum P3. Greedy?

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

    Simply binary search on the first cow which does not get a gift.

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

    Find a prefix such that each cow in that prefix will enter the queue inside the prefix. If this happens all remaining cows will not reach the front of the queue. You need to find such smallest prefix. I solved it in O(n log n) because I use max-segment tree but it can be solved with two sweeps in O(n) I believe.

    • »
      »
      »
      9 лет назад, скрыть # ^ |
      ← Rev. 5  
      Проголосовать: нравится +13 Проголосовать: не нравится

      Alternatively, you can find this prefix by noticing that two cows jumping to position i are as good as a cow jumping to position i and a cow jumping to position i - 1.

      So you can create a set with all positions {0, ..., n - 1}, and then go through the cows one by one, for each cow removing the last position no greater then n - 1 - ci. Once you remove 0 you have found such a prefix. (Because if you removed positions 0 through k - 1 and not k, you have k cows in your prefix all jumping to a position less than k.)

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

How to solve Plat 1 ?

»
9 лет назад, скрыть # |
← Rev. 2  
Проголосовать: нравится +5 Проголосовать: не нравится

When will editorial be out? Edit: Editorial is out

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +10 Проголосовать: не нравится

How to solve Plat. 2 ?

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

    DP[X][Y][4] — is cell (X,Y) reachable from B if the player was last is one of the 4 adjacent cells. Then the transition can be done by seeing if we can push the box to the four directions (cells of type (X+dirx[p],Y+diry[p])). That's possible if from the current player's cell we can reach cell (X-dirx[p],Y-diry[p]) without stepping on the cell with the box (cell (X, Y)). Well this is equivalent to checking if these two cells are in the same biconnected component (I'm not sure if that's the correct name, but I mean components such that by removing each vertex the component remains connected). During the contest I wasn't able to pass the problem as I implement Tarjan's algorithm in a wrong way, but I'm almost certain this solution should work.

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

    Could somebody please explain why bridge tree / finding 2-edge connected components isn't sufficient for solving this problem?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +5 Проголосовать: не нравится

Anyone have any idea when the results will be announced?

»
9 лет назад, скрыть # |
 
Проголосовать: нравится +15 Проголосовать: не нравится

To anyone who hasn't seen it yet, you can now check your rank in the contest by logging in to usaco.org and going to the December 2017 contest page.

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

Why does USACO consider the last submission to find the result? I got a good score first and then made some changes and score reduced and the time got over. I didn't know they checked as per the last submission. :(

»
9 лет назад, скрыть # |
 
Проголосовать: нравится -8 Проголосовать: не нравится

Pretty sure I just failed by a one line bug