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

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

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.

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

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

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

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

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

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

    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.

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

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

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

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

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

    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

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

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

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

can one give the contest unofficially ?

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

Where can i register for the contest ?

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

    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.

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

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.

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

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

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

    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)

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

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

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

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

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

Anyone ready to increase rank after practicing over summer?

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

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

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

I'm excited to get destroyed by plat problems!

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

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?

  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    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!
»
2 года назад, # |
Rev. 2   Проголосовать: нравится +48 Проголосовать: не нравится

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?

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

    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.

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

If I promote from x to y

Can I participate the next day and whenever? for y

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

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

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

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 ?

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

    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.

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

sry

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

    sry

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

      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)

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

        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'

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

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

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

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

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

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

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

      How can we see score?

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

        You have to calculate your score manually, I think.

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

          Does samples count towards scores?

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

            Yes, they’re basically free points.

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

              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

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

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

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

                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?

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

                  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.

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

.

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

    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.

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

    now i know a reason to improve in jitterclicking

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

Can I participant in this contest?

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

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

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

when will the editorial be published?

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

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

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

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

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

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

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

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

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

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

      Thanks

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

      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.

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

    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.

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

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

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

How to solve silver problem 3?

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

    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.

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

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

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

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

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

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?

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

    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
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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?

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

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

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

    Why?

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

      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.

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

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

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

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

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

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

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

How to solve Pt 2 ?

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

    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.

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

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.

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

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

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

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?

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

    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

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

    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$$$.

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

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

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

    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.

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

      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.

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

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

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

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

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

    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.

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

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.

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

    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.

»
2 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Gold P1
Gold P3
»
2 года назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

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

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

    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
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

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

        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.

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

          Oh, I see now.

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

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

      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?

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

        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.

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

    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
    • »
      »
      »
      2 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

        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.

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

        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

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

        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.

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

          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?

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

            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.

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

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.

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

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

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

      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.

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

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
  • »
    »
    2 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

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

      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.

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

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