xiaowuc1's blog

By xiaowuc1, 11 months ago, In English

Hi all,

The first contest of the 2023-2024 USACO season ran from December 15th to December 18th. 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).

There are some new rules regarding the platinum division of USACO, please refer to the website regarding the updates, especially if you are trying to be invited to the USACO training camp.

For those unfamiliar with the USACO contest format, please refer to the contest instructions and rules. We provide a short FAQ but folks should read all the rules carefully.

I have a question about the contest. Where do I ask it?

Email the contest director via the instructions above. Do not post anything publicly about the questions (including but not limited to your scores, how you felt about the problems, any content of the problems, etc) until after the contest is over for everyone. Do not DM me or anyone else affiliated with USACO, only the contest director can assist you. The contest director does not monitor Codeforces, this blog post is merely a courtesy to inform other people of the contest.

When can I enter the contest?

The contest will open on December 15th.

If I submit multiple programs, which one gets evaluated?

Only the last submission will be evaluated for official scoring purposes.

Can I use prewritten code / templates?

No.

Can I use AI tools during the contest including but not limited to ChatGPT and Copilot?

No.

Am I allowed to use outside resources during the contest?

You may only refer to language documentation.

Why didn't I get an email from USACO when I registered my account?

Follow the directions on the USACO website regarding Gmail Delivery Issues to contact the contest director.

Can I solve problems in Rust?

No, the only languages supported are C, C++, Java, and Python. Consult the instructions for language-specific technical details.

Will Rust support be added?

Probably not. Petition IOI to add Rust support first.

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

»
11 months ago, # |
  Vote: I like it +42 Vote: I do not like it

MIT Early Action results releasing during Plat :eyes:

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good luck everyone

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Rip my 20 line debug template... :/

»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

These guys never forget dissing Rust

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the contest start ?

»
11 months ago, # |
  Vote: I like it -7 Vote: I do not like it

time to attempt the contest for 30 minutes and play genshin impact for the rest, as usual.

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Contest starting time?

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Sorry for this question as it is my first time, how do we actually enter the contest or does the contest window pop up only after it starts??

»
11 months ago, # |
  Vote: I like it -15 Vote: I do not like it

So, am I right that I can start solving the contest anytime within the weekend?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it -15 Vote: I do not like it

    The contest is 4 contiguous hours in length. You can take the contest during any 4-hour block of time you want during the larger contest window from Dec 15 through Dec 18.

    From here. Please ask questions after reading the rules.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      I read the rules and then asked the question. The point is that before the contest clist.by showed that the duration of the contest is 4 hours, that is why I asked it.

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it -23 Vote: I do not like it

        This is what on CLIST:

        Duration: 04:00

        Time left: 4 days

        It seems that it's your first time to participate in USACO. Wish you good luck!

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it -16 Vote: I do not like it

          I have said that it was written BEFORE contest, that is why I asked BEFORE the contest in order to know if I should start immedeately.

»
11 months ago, # |
  Vote: I like it -16 Vote: I do not like it

When start contest?

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

xiaowuc1 what time does the contest end on 12/18? 11:59 EST?

»
11 months ago, # |
  Vote: I like it +6 Vote: I do not like it

Anyone know how to solve Plat p2 ?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    Spoiler
    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      when you need to get answer of some vertice in some component, how do you get it because i think if we can not just naively push down lazy ?

      • »
        »
        »
        »
        11 months ago, # ^ |
        Rev. 2   Vote: I like it +14 Vote: I do not like it

        See my code for reference. The answer for a node will be $$$mul \cdot A+ add$$$. You "push down" naively for the smaller component (i.e. make $$$mul=1$$$ and $$$add=0$$$) and update the larger component's $$$mul$$$ and $$$add$$$ values.

        Spoiler
»
11 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Hopefully 791 (full on P1 and P3 and half of P2) is enough to promote to Platinum. Anyone knows the full solution to Gold P2?

  • »
    »
    11 months ago, # ^ |
    Rev. 3   Vote: I like it +13 Vote: I do not like it

    You can maintain hash values for each vertex's path and whenever you get 2 different paths with same (maximal) length you can binary search on the hash values (based on length of path) to find the first point at where they differ and check which edge has lesser value and choose accordingly.

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +63 Vote: I do not like it

    First calculate longest path starting at each vertex using dfs. Group vertices by their longest path length. Process vertices with equal path lengths together starting from vertices with 0 path length to longest. Rank all vertices with same path using pair comparison on {best edge to a neighbour,rank of neighbour}. Only consider neighbours whose longest path is 1 less than mine(optimal neighbour).

»
11 months ago, # |
  Vote: I like it +34 Vote: I do not like it

How to solve plat1

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    So notice that for subtask 2 where all cows are infected you can do a greedy where you iterate cows from order of greatest depth to smallest depth. If not all cows are infected you need to find cows which could start the process infected, which means that all cows within d distance have to be sick. Then to do the greedy for some node if its not covered by any cow yet you take the cow with highest depth that can start infected within d distance. To check if a cow is covered by someone else you just check if a cow you picked is within d distance. You can do these operations all with centroid decomposition.

    • »
      »
      »
      11 months ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Then do greedy [..] take the cow with highest depth

      Depth with respect to what?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it -14 Vote: I do not like it

        The depth of the tree.Because this order is a perfect sequence of a chordal graph.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
          Rev. 2   Vote: I like it +6 Vote: I do not like it

          Can you explain what you mean? It’s difficult for me to understand how chordal graphs are related to this problem

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            A new graph is a chordal graph if we create a new graph that is concatenated with edges for two points u,v in the tree that satisfy dis(u,v)<=k. And the perfect elimination sequence of this graph is the sequence after each point is sorted by depth from largest to smallest.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Sir what does this even mean? We have a tree, what does chordal graph even mean?? And still, depth with respect to what :))??

          A greedy worked very well when all the restriction were loose and so long as all nodes were covered it was ok :)); but now you have tight restrictions meaning some nodes are at distance exactly d. These dont even give some tight/implementable restriction, i.e. you only need (maybe exactly) one node with distance exactly d.

          • »
            »
            »
            »
            »
            »
            11 months ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            I'm not sure if this is related to chordal graph, but I think the greedy strategy is correct. I'll post a proof below.

            Let $$$u$$$ is a lowest vertex needs to be infected. Let $$$v$$$ be the highest vertex can be chosen and $$$dis(u, v) \leq d$$$. The strategy claims that $$$v$$$ is one of the chosen vertex.

            Assume $$$v$$$ is not chosen, then another vertex $$$w$$$ with $$$dis(u, w) \leq d$$$ is chosen, and $$$dep(w) \leq dep(v)$$$. It can be proved that $$$v$$$ can infect all uninfected cows infected by $$$w$$$.

            Let $$$a$$$ be the LCA of $$$u$$$ and $$$v$$$.

            • Case 1: If $$$w$$$ is in the subtree of $$$a$$$, then:
              • In the subtree of $$$a$$$, $$$v$$$ infects all vertices of the subtree, since $$$dis(v, a) + dis(u, a) \leq d$$$ and $$$a$$$ is a lowest vertex to be infected. So $$$v$$$ infects no less vertice than $$$w$$$ in the subtree.
              • Outside the subtree of $$$a$$$, $$$v$$$ infects no less vertice than $$$w$$$ since $$$dep(v) \leq dep(w)$$$.
            • Case 2: If $$$w$$$ is not in the subtree of $$$a$$$, let $$$b$$$ be the LCA of $$$u$$$ and $$$w$$$, so $$$b$$$ is an ancestor of $$$a$$$.
              • In the subtree of $$$b$$$, $$$v$$$ and $$$w$$$ both infects all vertices of the subtree, since $$$dis(w, b) + dis(u, b) \leq d$$$, and $$$dis(v, b) \leq dis(w, b)$$$ since $$$dep(v) \leq dep(w)$$$.
              • Outside the subtree of $$$b$$$, $$$v$$$ infects no less vertice than $$$w$$$ since $$$dep(v) \leq dep(w)$$$.

            So it is not worse to changing the chosen vertex $$$w$$$ to $$$v$$$.

            I didn't come up with the greedy idea in the contest. I was inspired by the discussion here. I had a DP idea in contest with optimization to $$$O(N)$$$ but I didn't managed to implement it in contest.

            • »
              »
              »
              »
              »
              »
              »
              11 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              How does any of this relate to the restrictions imposed by uninfected nodes :))? Like, of course this works for "all nodes are infected", this was never the issue.

              • »
                »
                »
                »
                »
                »
                »
                »
                11 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                The only vertice can be chosen are those whose distance to nearest uninfected vertex is $$$> d$$$. When we choose vertices we only consider those vertice.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  And wby would this be optimal? What is to stop the greedy procastinating to consider a node as infected, but not to procastinate for long enough so it gets to consider a node that is "forbidden" by this principle? And even assuming we know the answer to this question, how can the greedy, knowing this, make an optimal local decision in a node when there are multiple other (non-local) similar scenarios (i.e. brother-ish nodes) in which choosing the alien node might eliminate the apparent need for choosing said node? (like, such issues break the necessarily local nature of greedy algorithms, and just this sort of band-aids dont seem to make for very compelling arguments, worse yet, I'd call them defective, else I am missing something :))

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  To the first question, I think it should be some data structure work to find the highest choose-able vertex within distance $$$d$$$.

                  To the second question, The proof just shows that if several vertices with same depth meet the condition, they are both optimal since they infects an identical subset of vertices need to be infected, so any one can be chosen as an optimal local choice.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  Why is the last part true? If I have to choose between two (brothered) vertices, how do I know which one is better? Like, it seems as though if one has a more shallow afferent subtree, while the other has smth like height exactly d, it is more optimal to choose the latter, and it is still unclear to me what criteria can set these two apart :))-- like, it seems as though it cant be just height, because this characteristic can obviously not tell the minimum number of needed nodes to infect on its own

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  As we are assuming that the vertex $$$u$$$ we are going to infect is the lowest one, it does not matter which subtree is shallower or deeper. If a chosen vertex infects $$$u$$$, it infects all vertice need to be infected in a whole subtree, and no vertice lower than $$$u$$$ need to be considered.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  11 months ago, # ^ |
                  Rev. 2   Vote: I like it +8 Vote: I do not like it

                  My friend let me write on his account as a joke, but the algorithm is correct.

                  If all cows start infected, it means any cow can be a source node that starts sick. So then the idea of choosing nodes is this: We root the tree arbitrarily, and we will loop through all nodes from greatest depth to smallest depth and select nodes to start infected in this process.

                  Let the current node be $$$i$$$. If $$$i$$$ is within $$$d$$$ distance from a some node we have infected, we need not consider it. So now assume $$$i$$$ is not infected. Note that it is currently an uninfected node with largest possible depth, as all previous nodes are infected and all later nodes have shorter depth. That means that, if we have two nodes $$$x$$$ and $$$y$$$ that are both valid we can choose to infect the node with smaller depth. fdironia provided a proof above.

                  So now hopefully it makes sense how this greedy works if all nodes are infected. We return to the original problem. The issue now is that some nodes can't start infected. This is when there exists some node within $$$d$$$ distance that is not sick at the end of all days. Any node that satisfies the condition such that all nodes within $$$d$$$ distance are sick at the end of the process can start the disease. So we have turned this into the original problem; we only consider nodes that have to be sick, and out of the available nodes to make him sick we pick the one with smallest depth.

                  Please direct the downvotes to me rather than my friend, I apologize ;w;. We were next to each other after school and we both thought it was funny.

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Participated for the first time in USACO contest. I solved P1, P2 completely and P3 for 2 subtasks. Is that enough for promotion?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If you did 2/14 subtask of P3 (I read subtask1 never count), you scored around 692 pts and promotion is about 700-750

    • »
      »
      »
      11 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      I solved 5 test cases including the samples.

      Btw, what is the scoring distribution of the problems?

      • »
        »
        »
        »
        11 months ago, # ^ |
          Vote: I like it +11 Vote: I do not like it

        Each problem is weighted equally (333 each) and each non-sample test case is worth the same for each question.

        • »
          »
          »
          »
          »
          11 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          So if I solved the first 2 problems completely, tha's 666 points. And 3/11 from the third are another 90 points. So I have 756 in total, right?

»
11 months ago, # |
  Vote: I like it +11 Vote: I do not like it

How to solve pt p3?

  • »
    »
    11 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$dp_i$$$ indicates the minimum answer of the first $$$i$$$ trains if the $$$i-th$$$ train is forced to satisfy $$$a_i=t_i$$$. Then consider $$$dp_i\rightarrow dp_j$$$ and find that the middle process must be left to go, right to go immediately and left to go immediately, so the start time of $$$(i,j]$$$ these trains can be determined, so the time complexity is $$$O(n^2)$$$.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How can you know the number of trains that have left from the other side?

»
11 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Is it rated?

»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Fun fact: it seems that the tests of plat P3 is quite week.

Here is a dp solution: dp(x,y,0/1) represents: considering the first $$$x$$$ As and the first $$$y$$$ Bs, the last one is A or B. This is wrong because you can not find out the current time. But I keep the pair (cost,time), that is, keep the solution with the minimum cost, if there are more than one, keep one with the minimum time. It only failed on two test cases of the largest subtask (xd.

»
11 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

In bronze, I solved full A, 1-6 of B, full C. Is my point 333 + 138 + 333 = 804? Will I pass bronze to silver?

»
10 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

What's the difficulty of the problems in silver/gold? What would their rating be in CF? Are the difficulties of the problems the same every month or do they get harder every month?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think there is something wrong with system.

After solving the gold problems, I clicked the "Promote Me" button.

At the final minutes, I just shortened my code (for fun) and sent it again, but it seems I had a bug, but there wasn't any time left to fix that.

And now it seems that the judging system somehow considered my last submission even though I did this after pressing the "Promote Me" button?!

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I know the rules (last submission rule) but when you press "Promote Me" it means you are done!?