xiaowuc1's blog

USACO 2021-2022 US Open
By xiaowuc1, 2 years ago, In English

Hi all,

The final contest of the 2021-2022 USACO season will be running this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing anything contest-related (including but not limited to your scores or anything about the problems).

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

Comments Comments (29)
| Write comment?
»
2 years ago, # |
  Vote: I like it +27 Vote: I do not like it

I always fully solve exactly (but no more than) one problem each USACO contest (trend is ongoing for last 6 contests, I think).

Good luck!

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

    This happened to me too, when I was in Gold. Now I'm in Plat and I solve exactly zero problems each contest.

    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it -14 Vote: I do not like it

      same :(

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

        Update: I finally broke the trend, this time by solving a whopping 0 problems in the gold division.

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

          I have a feeling #1 on gold was flows

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

            I also thought flows, but O(NM) seems slow.

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

              I also solved 0 problems in gold. But for P1, after the contest I saw that the version where every apple/cow has n=1 is equivalent to https://atcoder.jp/contests/abc245/tasks/abc245_e (after rotating the position-time graph by 45 degrees)

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

              Nah it was just a sorting + greedy problem. It was a similar question to the BOI2009 — Candy machine which you could find on the Gold section of the USACO Guide

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

    Same! except generally I get luckier on the us open. I wish us both good luck :D

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

How to solve Silver 2nd problem?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it -55 Vote: I do not like it

    By not asking the solution when the contest is going on :))

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

    Hi, I solved it so maybe I can help you, but I've now forgotten which was the second lol. Was it the one where you were given two strings with letters from a to r and had to answer some queries and say yes if the strings were the same taking into account only the letters given in the query? For that problem, the observation I made was that, for a string to be equal with letters abc, it also has to be equal for ab, ac and bc (maybe it could be further simplified but I'm not sure). With that observation it sufficed to check if the strings were equal for each pair of letters from a to r, which can be done in O(18^2 * n) where n is the size of the largest string.

    After precomputation, for each query just check if for every pair of letters of the query, both strings were equal, using the precomputed information.

    I hope it helped, I'm not sure if I've explained myself clearly.

    (I've checked thrice and I think the contest has ended but if it's still going on pls tell me soon so I can delete all of this lol)

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

      How many cases did you get? I used this and missed the last case. It might just my implementation though...

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

        I got all of them, must be your implementation

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

      I exactly did this and got TLE T_T

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

      I stucked in this problem for 3.5h. Finally I got accepted using similar solution.

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

    precomputation on all 18^2 pairs of letters

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

How to solve Silver P3?

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

    If you can change any letter to the other two letters, that means that those two letters = the first letter (WO = C, WC = O, CO = W). Same letter pairs can be ignored, so you skip them or use another letter to represent a "void" and then take it into account when joining letters(so you won't join a letter with a void). So the brute-force approach would be to divide the length of the string by two each time, by transforming two letters into one until there's only one letter left, if it's C then answer is YES, if not then answer is NO. That would pass for tests 1-5 or something like that.

    The same approach could be optimized by using data structures as segment tree (and probably sparse table too).

    That approach is the one I used, but I've got the feeling that there's probably a better one, if anyone has another approach pls comment it down :)

    UPD: From a comment that I've seen down below, the order of operations doesn't matter so you can just keep joining letters and there's no need of data structures. Now I feel dumb lol :(

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

    If you notice the operation between two characters in the string was nothing but the XOR of them. Since C(1) ≡ O(2)W(3) , CC ≡ ""(0) , also the order of operation doesn't matter here , so we can just check if XOR of S[L..R] == 1(C) or not.

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

      Wow that is a lot better than my approach lol

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

      damn, i noticed the XOR part but didnt realise the xoring of the entire string part... F

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

        Yeah , i mean i considered few strings like for eg. COWC , COWO , COWCO , and then tried operations in different orders and saw that order too doesn't matter which made me realise that xor operator perfectly works here. So i guess in such problems considering the dependency of order of operations simplifies the problem a lot.

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

Any ideas how to solve plat P1 or P2?

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

    P2 :

    First , you need to calculate the scc of the graph. (If one scc has only one vertex , then it is impossible to win ).

    Second , if there is a vertex whose out degree is 1 , then merge the vertex and the vertex it can go to .

    Keep doing the second step until every vertex's out degree is not equal to 1.

    Each query is to check whether u,v is the same vertex.

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

Results are out at http://usaco.org/index.php?page=open22results

Personally, I qualified for gold with an 833 :)

→ Reply