xiaowuc1's blog

USACO 2021-2022 First Contest
By xiaowuc1, 2 years ago, In English

Hi all,

The first contest of the 2021-2022 USACO season will be running from December 17th to December 20th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is live now! Please read the contest rules carefully, especially regarding how to ask clarifications or contact the contest organizers. Do not spoil anything (including but not limited to your scores or anything about the problems) about the contest until the end of the contest (four hours after the stated deadline of the contest).

Edit 2: Results have been released.

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

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

What are one's chances at plat with 1780 rating (peak 1930)? I've solved virtually all past gold problems since 2015.

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

    I think they're quite high, if this year's contests are like last year's. You got this :D

    I hope to plat as well xD

    EDIT: omg I did it!!!

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

    Hello CF, today starts the second USACO 2021-2022 contest!!

    USACO 2021-2022 Schedule.

    • Dec 17-20: First Contest.

    • Jan 28-31: Second Contest.

    • Feb 25-28: Third Contest.

    • Mar 25-28: US Open.

    • TBD (Late May): Training Camp.

    • Aug 7-14: IOI 2022 in Indonesia.

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

Thank you for your contests. Would you please also clarify the exact time of each contest?

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

    It's not xiawuc's contest, as far as I know. It's run by Brian Dean.

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

    The contests are open for several days, Dec 17-20, so you can pick the time window that suits you best. The time starts when you log into the contest, and you only have 1 attempt

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

Can a specialist with rating 1413 (peak 1553) reach gold in 2 contest?

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

can one give the contest unofficially ?

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

Where can i register for the contest ?

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

    You dont have to register for the contest — just login and click on start contest on the contest page when you are ready for your window.

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

Hope I reach Gold this contest — I am stuck on Silver for the last 2 years although I think my CF rating is high enough to clear Silver.

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

what's the duration for a contest in USACO? Does it vary in leagues(bronze, silver, gold, platinum)?

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

    The contest is 4 hours for each division. You can take this for any 4-hour window from Dec 17th-20th. Also if you promote in-contest, your timer resets (so for example if you ace Bronze, then you promote to Silver and have another 4 hours for that contest)

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

      I could not find any info on this but could you get promoted twice, if you full score two times?

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

        Yep, technically it's possible to promote to platinum in your first contest by acing everything.

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

Anyone ready to increase rank after practicing over summer?

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

What is the exact start & end time? I can't find it anywhere.

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

I'm excited to get destroyed by plat problems!

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

If you ace a division, does your timer restarts? If yes, does it start automatically or I will have the right to start whenever I want before 20th dec?

→ Reply
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    1. Yes, your timer restarts when you are promoted to a higher division.
    2. You have the right to start your 4-hour contest whenever you like before 20th December. Good luck!
    → Reply
»
2 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

Since the rules about the usage of the prewritten code are explicitly strict I want to clarify a couple of things. I'm not necessarily having anything against it, just want it to be more clear :)

  1. I suppose the rule literally concerns everything in the code so, for example, you have to type every include manually.

  2. Can you do all the includes and convenience stuff just once during one particular contest and reuse it between problems? Maybe one could even reuse something like a segment tree between 2 tasks, is this allowed? Or is it supposed to be from scratch in every single problem?

  3. If yes to the previous question — can you start doing this 10 minutes before the contest?

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

    In the future, you should email the contest organizer these sorts of questions, as the contest organizer does not monitor this forum.

    The answer to question 3 is very clearly no, independent of the answer to question 2, as that would be considered pre-written code, even if you do it right before you start the contest. The rules very clearly state that using pre-written code is forbidden.

    The answer to question 2 is probably (again, confirm with the contest organizer) yes. The intent of the rule is to emulate starting from scratch in a "clean" environment, so once you typed out the code, you should be able to copy/paste it freely within a problem or across problems.

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

If I promote from x to y

Can I participate the next day and whenever? for y

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

    Yes you can if you promote in-contest and it's before the deadline, your timer also resets.

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

I did not do well on gold. I wonder can I submit the solution out of contest to check whether my fixed version is right or should I wait until after 20th Dec ?

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

    You will have to wait until after the problems are available for practice. You can also check whether your solution is right with someone who may have solved that problem you resolved after the official conclusion of the contest. Also, note that the contest ends at around 7 AM on December 21st ET.

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

sry

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

    sry

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

      In the future, it'd be best to read the announcement and rules more carefully:

      Do not spoil anything (including but not limited to your scores or anything about the problems)

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

        i got it, im sorry, i lost all my contribution already in literally a month i will be like 'i was so stupid back then'

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

    Thank youmy frmied!!!!!! With this information, I now know the problems givennin the contest and i can easily AK after i solve each one outside contest!!!!

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

If we get AC on most of testcases of a problem will we get some points from that problem or not?

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

    You can get partial score i.e getting 5/10 testcases in 1 problem will give around 333/2 points

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

      How can we see score?

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

        You have to calculate your score manually, I think.

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

          Does samples count towards scores?

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

            Yes, they’re basically free points.

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

              except, by law, you aren't allowed to just read the examples and print the example directly, as your program isn't computing anything per se (thus, a program that is just reading the input and checking if it correspond with some example to print some output would not be accepted). Hope, though, this will be the case, because spoiler

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

                Aren't you allowed to do so in case you have something else in your solution though? Meaning that if you are trying to solve a certain subtask which does not include every samples, you are allowed to print out sample answers. I think you are referring to the sixth note in the General Technical Details, which counters only solely printf solutions. (Furthermore, not allowing stuffs like that would be unreasonable, as USACO refuses to judge solutions which does not completely pass samples, and since some problems are essentially two independent problems, it would be impossible to solve one without at least solving a subtask for the other.)

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

                In fact, I don't really understand this rule. Does it mean that programs that do not contain any computational procedures, but only print statements, are forbidden?

                For example, suppose my program contains a corner case, am I violating this rule by directly outputting the answer to such case?

                Or, if I just guessed a random formula for a problem to pass all the examples. Is this a violation of the rule?

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

                  nah corner cases r fine

                  Programs that consist of essentially nothing more than print statements may be disqualified. If feedback for certain test cases is provided during a contest, you are NOT to submit repeated programs consisting of essentially print statments in order to reverse-engineer the inputs. Programs must actually compute the requested answers, not just print results from a pre-computed lookup table.

                  → Reply
»
2 years ago, # |
← Rev. 222   Vote: I like it -106 Vote: I do not like it

.

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

    Please reread this page carefully as it states all the contest rules.

    Note that this includes sharing your score and giving insight about the problem.

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

    now i know a reason to improve in jitterclicking

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

Can I participant in this contest?

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

    Anyone can still participate in the contest. Make sure to register for an account, and start the contest when you're ready. Good luck!

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

when will the editorial be published?

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

    The contest is still running. It should be available after the contest.

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

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

The contest is over now? How do you all perform?

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

Any idea for silver's problem 1? (The contest has already end acording to the usaco site)

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

    Consider the farms between two cows of Farmer Nhoj, using two cows of farmer john you can get all the farms between any two cows Farmer Nhoj. So for each such segment find maximum value of tastiness you can get using only 1 cow Lets call it $$$P_i$$$. and tastiness if you use two cows be $$$Q_i$$$. For a moment use 2 cows on each segment. Now number of cows used might be greater than $$$N$$$. So greedily Decrease the value by finding the minimum delta (that is either convert 2 cows to 1 cow for some segment, or 1 cow to 0).

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

      Thanks

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

      For each segment, if using 1 cow you gain $$$P_i$$$ while using 2 cows you gain $$$Q_i-P_i$$$, We also can easily prove that $$$P_i\geq \frac{Q_i}{2}$$$. Hence if we use 2 cows, then the event of 1 cow would be considered already. Then we have a sorted list of values, for each cow we used.

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

    Greedily select the intervals from starting. Start from the leftmost position and continue till you can select the patches. Also start as far as you can from the first patch you are selecting.

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

    I didn't participate in silver so I can't submit but here's my idea.

    Consider the $$$M$$$ cows, they divide the grass into $$$M+1$$$ intervals(if a grass is on one of these cows, just delete them).

    It's obvious that the placement of the $$$N$$$ cows in different intervals are independent.

    If we put two cows in one interval, we will put them in position $$$L+1$$$ and $$$R-1$$$ (the interval is $$$[L,R]$$$), so every grass in the interval will be choose (we just need one cow if the interval is the leftmost one or the rightmost).

    If we put one cow in one interval, one consecutive segment of the grasses will be chosen and we will find the maximum one.

    Define the total value of one interval $$$V2$$$, we consider the two ways of placing the one cow.

    • Put it in $$$L+1$$$

    • Put it in $$$R-1$$$

    It shows that these two segments of grasses will cover all the grasses in the interval, so if we define $$$V1$$$ as the maximum value of placing one cow, we know that $$$2*V1\ge V2$$$, which means $$$V1\ge V2-V1$$$.

    Now will put the $$$N$$$ cows one by one into the intervals.

    • Put one cow in the interval with $$$0$$$ cows has the value $$$V1$$$.

    • Put one cow in the interval with $$$1$$$ cow has the value $$$V2-V1$$$.

    Just sort all the values ($$$V1$$$,$$$V2-V1$$$) and take the maximum $$$N$$$ ones and it will be valid.

    (Because due to the observation $$$V1\ge V2-V1$$$, value $$$V1$$$ will always be taken before value $$$V2-V1$$$, so this method must be valid.)

    Complexity: $$$O(nlogn)$$$

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

How to solve silver problem 3?

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

    You can subtract the number of invalid pairs from $$$N^2$$$.

    Notice that invalid pairs are of the form:

    1. $$$a_1 + a_2 \gt k$$$

    2. $$$b_1 + b_2 \lt k$$$

    these are $$$2$$$ dsjoint sets.

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

    If you go from 0 to 2M, you see the event $$$a_i+a_j$$$ your results increase by 1, while you see $$$b_i+b_j$$$ your results decrease by 1. Complexity $$$O(M^2)$$$.

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

      Isn't O(N^2) too slow?

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

        It is $$$O(M^2)$$$, sorry for the typo, since $$$a_i$$$ and $$$b_i$$$ are bounded by $$$M$$$.

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

    Observe that M was quite less. So store the count of all possibilities of ai + aj and bi + bj. Now you can create a difference array, and iterate for all possible sums from 0 to 2*m, add cnt[] to the difference array for sum values of a (because range starts here) and -cnt[] to the difference array for sum values of b (because range ends here). Finally, calculate the prefix sum to get the answers for all k.
    Overall time complexity : O(max(n,m2))

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

Okay... How to solve Gold 1 ?

For t=1 i solve it with dp[i-th element][choose or not], but t=2 I try to use dp[i-th element][previous one statue][current state]

status

0 = not choose

1 = choosed and will make pair with later one

2 = choosed and paired with previous one

i wrote the dp for a long time and finally find the bug at the last minute but can not submit.

Can anyone tell me is it correct?

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

    For t=2, how will you check that any pair of not chosen elements are not within a range of k with this dp state? Also, there is an easy greedy approach for t=1 as well.

    First observe that if you know which elements you have to keep single, then greedily you should select the remaining consecutive elements to pair up.
    For t=1, there will be some disjoint ranges. You can separate ranges when abs(a[i+1]-a[i])>k. Now a particular range will always contain an odd number of elements, there will be several cases to remove at max one element, start pairing from the end and calculate the min value until you can pair from the end.

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

      I used DP, but my state is whether the last 3 guys are used. It's getting wrong answer, and I cannot fix it.

      here

      Help?

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

I think it's not very healthy how almost every Platinum problem is being set by the same person for quite a while now.

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

    Why?

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

      Every author comes up with problems that share a distinct taste, which inevitably favors some contestants— just look at the number of counting problems. Personally, many of these statements feel quite artificial, and just not very interesting.

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

        Well, at least the counting problem wasn't mine this time. :)

        I think it's not very healthy how almost every Platinum problem is being set by the same person for quite a while now.

        I agree with this, it's not very healthy for me. Unfortunately, there are not very many Platinum proposals in the database that are not by me ...

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

    Totally agree, I think people who are not xiaowuc1 should stop setting Platinum problems

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

      Can you be hired to set platinum problems? I think USACO would benefit from some data structures problems and some matroid intersection problems.

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

How to solve Pt 2 ?

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

    First, split the two types of cows into two arrays sorted by their position, afterwards, $$$t=1$$$ is pretty simple, since you can use $$$dp[i][j]$$$ = minimum sum of weights of unpaired cows if we've paired up or left unpaired the first $$$i$$$ cows of the first type and the first $$$j$$$ cows of the second type. For this dp we won't have to worry about the maximal matching part since the needed cost is minimal so we won't ever leave unpaired two cows which could have been paired together.

    For $$$t=2$$$ though, the maximal matching requirement becomes a problem, so the first ideea here would be something like $$$dp[i][j][k][0/1] =$$$ maximum sum of weights of unpaired cows if we've paired up or left unpaired the first $$$i$$$ cows of the first type and the first $$$j$$$ cows of the second type, and we aren't allowed to leave any cow unpaired in the next $$$k$$$ cows of the first or second type (given by the 0/1). This works in $$$n^3$$$.

    In order to optimize this, let's define $$$dp[i][j][0] =$$$ maximum sum etc. ---||--- if we don't have any restriction going forward (we can leave a cow on either sides unpaired) , $$$dp[i][j][1] =$$$ ---||--- if we are only allowed to leave a cow unpaired on the left side , and $$$dp[i][j][2] =$$$ ---||--- if we are only allowed to leave a cow unpaired on the right side. Notice that in all of these states, we can always pair up the next cows.

    Let's see how to calculate this, I'd suggest doing it forward. Say we're in a state of the form $$$(i,j,0)$$$ meaning we paired up all the first $$$i$$$ cows on the left, $$$j$$$ cows on the right, and we can now leave a cow unpaired on either side, then, we can either:

    • pair up the cows $$$i+1$$$ and $$$j+1$$$ (if possible) going to $$$dp[i+1][j+1][0]$$$
    • leave a cow unpaired.

    WLOG, let's assume we leave the $$$(i+1)$$$th cow on the left unpaired, this means we now have some $$$k$$$, for which we aren't allowed to leave any right cow unpaired among the next $$$k$$$ cows. So, if we assume we are going to pair up the next $$$k$$$ cows on the right with the next $$$k$$$ cows on the left (and if this is possible) this means, this dp could update $$$dp[i+1+k][j+k][0]$$$. But maybe, we're gonna leave some more cows unpaired on the left, since there isn't anything stopping us, so we should also update $$$dp[i+1][j][1]$$$. It turns out these two are sufficient, since whenever we're going to leave a cow unpaired on the left, that'll also update a dp of type $$$0$$$ in some $$$k'$$$ steps (I'm not sure how clear I explained this, but if you try to prove it, it will probably make sense). Finally, the transitions from other types of dp (such as $$$dp[i][j][1]$$$) are very similar, the only difference is the fact that we aren't allowed to leave a cow unpaired on some side.

    Damn! this is a big block of text, sorry for that but idk how to format xD.

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

Okay so for Silver problem 3 there is a very funny solution that works in $$$\mathcal O(n+m\log m)$$$ time. For all pairs $$$(i, j)$$$ setup polynomials

$$$P_{i, j} = \sum_{k = a_i+a_j}^{b_i+b_j} x^k$$$

Notice how the numbers $t_i$ we want from $$$0$$$ to $$$2M$$$ are essentially the coefficients of monomials $$$x^i$$$ in the sum $$$\sum_{i, j} P_{i, j}$$$. In order to solve this problem efficiently note that $$$(1-x)P_{i, j} = x^{a_i+a_j}-x^{b_i+b_j+1}$$$ and thus when we sum this over all pairs, we obtain a sum of

$$$\dfrac{(\sum_{i} x^{a_i})^2 - x(\sum_{i} x^{b_i})^2}{1-x}$$$

. Now we can use FFT and $$$\mathcal O(m)$$$ computations to solve the problem completely.

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

Does anybody knows how to re-open problems (or have screenshotted the problems)? (I would really like to ask the solutions from strong CPers who haven't participated in the contest, but I don't remember the samples.)

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

There is a subproblem I encountered which seems pretty standard but I couldn't come up with a good idea quickly.

Given a set of $$$n$$$ segments and online point queries you need to return all segments that contain this point and you haven't returned before.

I strongly feel like it should have a clean $$$n \log n$$$ solution that is not too hard to implement but for now I can only solve it in $$$n\sqrt n$$$ with some slightly unpleasant code complications. Does anybody know it or have any ideas?

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

    You can maintain a segment tree over the values.If there is a segment (a,b) you basically need to add the index of the segment to the log(n) nodes which cover the (a,b) range.When there is query you can extract the values present in the log(n) nodes which cover the query index i.You have to erase all the values in these nodes also

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

      Oh wow, it's very nice and clean indeed) Thank you! Can't believe I spent a very considerable amount of time on that.

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

    Here's another (maybe dumber lol) method: for each left endpoint $$$a$$$, sort all segments $$$(a, b)$$$ in increasing $$$b$$$ order. Then maintain a segment tree which stores the maximum $$$b$$$ for each $$$a$$$. Finding whether there currently exists a segment which contains $$$x$$$ can be done by seeing if the max of values in the range $$$[0, x]$$$ is at least $$$x$$$. To get the segment, the segment tree can also return the index of the max, and then it can be replaced with the next longest segment which begins at $$$a$$$.

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

Is there a way to solve Platinum problem 1 in less than $$$O(N+K\log^2 K)$$$ time?

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

    The problem reduces to dijkstra on O(N+K) vertices and O(N+KlogN) edges, however, only O(K) edges are non-zero, so I suspect that you can solve it in O(N+KlogN) with some modified priority_queue.

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

      I got that it reduces to Dijkstra on $$$O(K)$$$ vertices and $$$O(K\log K)$$$ non-zero edges. It's possible my graph differs from yours.

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

    Fibonacci Heap? $$$O(NlogN+KlogN)$$$

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

    My solution works in $$$O((N + K) \log (N + K))$$$ time.

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

    I think my solution works in $$$O((n+K)\log(n+K))$$$ but I can't find it now. It tested so in random cases(but very slow).

    I used a segment tree to optimize Dijsktra directly, instead of adding $$$K\log n$$$ edges.

    Reverse the graph first.

    For every ticket, insert $$$[l_i,r_i]$$$ into the segment tree.

    For each node on the segment tree, only the cheapest ticket might become the next one to use, let its value be $$${mn}_p$$$, and it may start from any station in the segment, let $$$d_p$$$ denote the smallest $$${dis}_i$$$ among $$$l\sim r$$$(where $$$l$$$ and $$$r$$$ are endpoints of the segment).

    Every time find $$$\min{{mn}_p+d_p}$$$, by carefully implenting it we can get a $$$O(n\log n)$$$ solution.

    But it seems that the constant is rather huge(a lot of maintained on segment tree), I spent a lot of time optimizing it.

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

How to solve 2nd problem of silver division? I tried to do that with DSU but was unable to get the minimum distance between two pairs of DSUs.

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

    To calculate the cost between two connected components you can use lower_bound to find the closest element in the second set for each one in the first.

    Now you can simply brute force the connected component that will be connected to 1's and n's component as it allowed to add at most 2 edges.

    To reach O(n*lg(n)) complexity we shall consider each element of the smaller set when calculating the cost.

    → Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Gold P1
Gold P3
→ Reply
»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Hint for Gold Prob2 please?

And also what is the solution for the second subtask of the same problem? (I really hope it's not something randomized, please!)

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

    I don't remember the subtasks, and the problems aren't visible right now. Here are some hints, I hope they are helpful! :)

    Hint 1
    Hint 2
    Hint 3
    → Reply
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      The second subtask had one constrain that the permutation is randomly generated.

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

        Ah. I think that just means that there are no malicious testcases (no testcases which intentionally lead to $$$O(N.Q)$$$ time if you build and query the binary tree naively.

        Now that you say it, I do remember that my first $$$O(N.Q)$$$ submission passed those randomly generated testcases.

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

          Oh, I see now.

          And also this idea of binary tree is fabulous, do you remember any other problem using similar ideas like this?

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

            Can't say I do, sorry :(

            Glad I could help :)

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

      Hello, I'm sorry but I don't quite understand what a "binary tree" is referring to. Do you mean that we should make a binary heap over the array, or a binary search tree, or is it something else?

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

        Draw the binary search tree and note that on the path from a node to the root, if you mark left edges as L and right edges as H, then the problem reduces to finding number of HLs on path to the root.

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

    Here was my solution (around 30 lines of working code):

    Hint 1
    Hint 2
    Hint 3
    Hint 4
    Hint 5

    This solution eliminates the need for extra data structures like a BIT (which I think many others used), and is really short to implement.

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

      Woah, you made it seem very simple.

      I wonder, was the second problem an easy one for other people? Because, for me, it was a pain to think about it, while on the contrary, the first and the last were somehow trivial.

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

        My code was 350 lines and included a lot of casework + segment tree with lazy propagation (it turns out seg tree isn't needed, but I understood that 50 hours after contest ended). It is different than the binary tree idea and much messier, but I'll share anyways.

        The main idea is that if you look at the matrix formed with all the "H"s and "L"s, then all columns have some "?"s followed by some "H"s followed by some "L"s followed by some "L"s. We can identify the transition points, where things change, and since there are at most $$$3N$$$ updates, if we can point update and query number of "HL"s in $$$O(1)$$$ or $$$O(\log N)$$$ we're good. Also, we should stop querying after we know our number.

        To point update just look at 2 characters to left and 2 to the right and figure out if things change and if so, by how much.

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

        I wonder, was the second problem an easy one for other people?

        Well, the final idea and code are simple, but in reality this idea wasn't extremely easy for me to think of. In fact, it took the longest time out of all three problems (around 1 hour and 30 minutes) of thinking for me to come up with this solution XD

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

        Keep the set of pairs (value, position). When you add a new pair $$$(v, p)$$$ check the existing element to the left $$$(v_l, p_l)$$$ and to the right $$$(v_r, p_r)$$$. If $$$p_r > p_l$$$ you need to add 1 to answer on $$$[p, p_r)$$$, which you can do in linear time. If you put proper initial values into the set there are no corner cases. It is about 15 lines of code.

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

          Yep, if I'm not misunderstanding this is what I did (my code isn't the most concise).

          Small correction: shouldn't it should be O(n log n) time not linear, since you use a set?

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

            Yeah, you are right actually it is the same, my bad. I was slightly thrown off by your hints 2 and 3 and haven't read the code close enough until now, just skimmed through.

            For linear I meant just the part with adding to the answer.

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

I would like to mention a thing about Silver S1. It was a wonderful problem but I submitted a very random code and it managed to pass 8 tests (obviously it's totally wrong) so doing S2, S3 and a random code on S1 could have allowed one to pass silver.

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

    But maybe S1 is the easiest problem among the three problems.

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

      I didn't find it to be that way for me it was as such S1 > S3 > S2 but it could be just me since I am inherently bad at problems involving greedy.

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

I just upsolved HILO from USACO Gold. I don't see my solution in the editorial. But I think it's a simple O(n) solution:

I simulated the process backwards. I maintain intervals of numbers $$$x+0.5$$$ that are not distinguishable. At the end, all numbers are distinguishable, so all $$$n+1$$$ intervals are of length 1. As you simulate backwards, the intervals above and under the current p[i] get merged, because those weren't distinguishable before.

I only maintain the boundaries between the intervals in an "array linked list" and for each interval, what the number p[i] was that merged it last. (last[a] = the last p[i] that merged the interval underneath a).

Merging is then just removing from the linked list and updating one number.

Which numbers could get a "HILO" in their string at this moment in time? If we have the interval $$$(a,b)$$$ that gets split into $$$(a,p[i])$$$ and $$$(p[i],b)$$$, it can be verified that all numbers $$$x+0.5 \in (last[a],i)$$$ get an extra "HILO". Since we need to support range adds and only query at the end, we can maintain the difference array and do prefix sums at the end.

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

    Sorry, I don't think I understand what "not distinguishable" is referring to. Is it referring to when a number is skipped for consideration since another number before it already revealed enough info (Like skipping 4 because we already know 3 is too high?)

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

      You can think of Elsie's procedure for guessing the number as follows: Elsie keeps the search range [l,r] (at the beginning [0.5, n+0.5]), which is the interval where the number could still be. Her search interval becomes smaller when she does a query, and she gets the answer HI or LO, just like binary search. If the number she's was going to guess is outside the search range, she doesn't ask it at all.

      The intervals stored in the array linked list, are exactly the intervals which Elsie could have at this point in time as her search range. So in this way, you can simulate all possible ways for her search to go at once in O(n). If you look in the forwards direction in time, if she guesses a number, it splits the interval that this number lies in in two: The portion where she would answer HI, and the portion where she would answer LO. If you go backwards in time, this corresponds to merging of the intervals above and below the number guessed.

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

December Silver is very hard for me... I hope next contest silver will not be like this :(

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

    Don't worry. It will be just harder.

    → Reply