xiaowuc1's blog

By xiaowuc1, 5 weeks ago, In English

Hi all,

The second contest of the 2020-2021 USACO season will be running from January 22nd to January 25th this weekend. Good luck to everyone! Please wait until the contest is over for everyone before discussing problems here.

Edit 1: The contest is now live! Please do not spoil anything about the contest publicly until the contest is over for everyone, and please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here.

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

»
5 weeks ago, # |
  Vote: I like it +29 Vote: I do not like it

The first contest of the 2020-2021 USACO

There is a typo first -> second.

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Hoping to make Gold. Do you think someone with my rating graph has a decent chance at making Gold?

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it -24 Vote: I do not like it

    f, i didn't expect that

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      WHAT?????

      I'm interested in why you think so...I mean I kinda base my progress on my rating.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 5   Vote: I like it +15 Vote: I do not like it

        It's just something people say when they feel bad about their rating to make themselves feel better (at least me :clown:). It's not perfect (especially for lower placement OI progress where it corresponds least), but it still is should be the unarguably the best measure of progress relative to others right now, assuming you have decent amount of data points.

        Most gold are high specialist or low expert I think, so you probably have somewhat decent chance.

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
          Rev. 3   Vote: I like it -18 Vote: I do not like it

          f, i didn't expect that

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

            I only said because of the existence of highs is not so proportional to your ability at all.

            This is why you need decent amount of data points, because highs and lows should average out to a close representation of your skill. But yeah, one large drop in rating, or one large rise, doesn't mean much on it's own.

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I'm a "her" FYI.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I hope too. Good luck for everyone and especially for you)

    Yes, it's possible. I think, you can get Gold. I believe in you!

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How do I register and participate? I opened the Contests page but there are only previous contests there.

»
5 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

Is there a way to see the standings? I am completely new to the USACO platform. Thank you.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    No, you can't see live standings. That's because it's an IOI-like contest.

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

    After the contest ends, you can see your standing.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    Why are people downvoting me? Did I ask something wrong? I already said that I am new to that platform :(

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      From post:

      please report any issues with the contest directly to the contest administrator via the instructions instead of posting them here

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +18 Vote: I do not like it

        Sorry for that. Will keep in mind from next time.

»
5 weeks ago, # |
  Vote: I like it -98 Vote: I do not like it

Solve all the silver using 3hours and 56 minutes.....

Think the problem for a lot of time, good problem!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +46 Vote: I do not like it

    Please don't discuss anything about the contest right now; I mean discuss literally NOTHING.

»
4 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

When can we discuss?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    It's best to wait until the USACO website states that the contest is over (though I don't know when that will be).

»
4 weeks ago, # |
Rev. 3   Vote: I like it +49 Vote: I do not like it

Here are my solutions to all of the gold problems:

Problem 1: Uddered But Not Herd
Problem 2: Telephone
Problem 3: Dance Mooves

Side Note: Was it intentional to make it hard to notice that there are $$$\leq 20$$$ distinct characters in the string in problem 1?

Also: Does anyone know the solution for Plat Problem 3? I implemented Offline Dynamic Connectivity, but it had a complexity of $$$q*n*log(q)*log^2(n)$$$ with a bad constant, so it was too slow.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +47 Vote: I do not like it

    I agree, spent about 30 minutes thinking that there are <=26 characters instead and tried to find a polynomial solution because I thought <= 20 was a subtask. I wish they had stated that clearly in the problem statement, not just in the subtask list...

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +27 Vote: I do not like it

      Same here! Except in my case I spent a lot more than 30 minutes :(. The fact that they mentioned 26 in the statement made it even more confusing.

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

    Hii!!!!

    Was it intentional to make it hard to notice that there are ≤20 distinct characters in the string in problem 1?

    Are you sure ??????????... Because i solved it for 2 hours with this very obvious $$$n^{2}*2^{n}$$$ solution which is a kind of repeat to this problem https://codeforces.com/problemset/problem/1238/E

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

    Wait a minute!! I just went through the question and read it 10 times then i noticed the scoring portion. Are you talking about M i l d r e d ?? If yes, then its insane.

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

    For Problem 2, my friends qwerty190 osmium Freaksus got AC by doing Dijkstra, even there were n^2 edges. I am so confused why those solutions got passed.

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

      Would they be comfortable sharing their code? Sometimes brute force approaches with things like pragmas and heuristics pass, which is unfortunate.

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

        As far as I know, they don't use this kinda stuffs. I am contacting them, as soon as they reach me, they would reply to you in this comment!

        Edit: They didn't save their codes, so they can't get access to them right now. After this session's USACO problem page opens, they would get the codes. Moreover sorry for the misinformation, one of my friends got all ac by doing Dijkstra, but the other two got 12 test-cases out of 13.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Yeah, I also know some friends that passed with just a brute force (without any pragmas or the sort.) I hope USACO adds some tests and rejudges, because a naive N^2 dijkstra should not get 12 or 13 cases.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    You can solve plat problem 3 in $$$O(NM + Q(N+M))$$$; essentially, you approximate the answer by counting how many CC's have their upper left corner inside the query rectangle using prefix sums, and then you walk around the perimeter of the query rectangle to fix your approximation. There are various strategies to handle the details of the counting/overcounting; the cleanest strategy I know is to consider the (planar) graph of lattice points and use the Euler characteristic formula V-E+F = # cc's + 1.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How do you count the number of faces efficiently in this graph?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        Note that each face/cycle of the original graph is either fully contained within the query rectangle, or it merges with the "outside" face (that extends to infinity) and doesn't contribute to the count. Thus, we just need to count the number of original faces fully contained within the query rectangle. From now on, "faces" will refer to faces of the original, whole graph.

        First, number the faces, and for each lattice point (corner between 4 tiles), precompute which face it belongs to using flood-fill. Now, for each face, pick one lattice point in it as the "representative", and compute rectangular prefix sums for the number of representatives in a region. This is our approximation/overcount for the number of faces fully contained; it may include some extra faces whose representative point is inside the query, but are not fully contained. Fortunately, these faces must intersect the boundary of the query rectangle. Thus, walk along perimeter of the query region, and subtract off the number of faces which intersect the perimeter at least once and whose representative is inside the query region; we can count these in linear time with a boolean array or a hashset. Then, we will be left with exactly those faces which are fully included, so V-E+F will work.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    As ecnerwala said: the graph is planar, so we want to know the value of $$$V - E + C$$$, where $$$V$$$ stands for the number of vertices, $$$E$$$ for the number of edges and $$$C$$$ for the number of cycles. $$$V$$$ and $$$E$$$ can easy be calculated in constant time per query with prefix sums. To calculate general cycles we can just run DSU on the dual graph. Then for each connected component in dual graph we calculate its bounding box.

    So, we are given a list of rectangles (at most $$$n \cdot m$$$) and for each query we have to count how many of them are inside query's rectangle. It's easy to see that at this point complexity $$$O(q \cdot n \cdot m)$$$ is enough, as it's a very simple check.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +15 Vote: I do not like it

      Making strong tests is hard :(

      I think my original proposal had $$$Q \leq 5000$$$ and $$$N, M \leq 2000$$$ without the increased TL — do you think the $$$O(QNM)$$$ solution still would've passed with those constraints?

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +15 Vote: I do not like it

        Don't forget that you can count number of small bounding boxes (e.g. 1x1) insde of query in linear time, so this solution would have very small constant.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it +20 Vote: I do not like it

          I think if you use prefix sums for all bounding boxes with max side length at most $$$n^{1/3}$$$, you can get $$$O(1000^{8/3})$$$ runtime.

          • »
            »
            »
            »
            »
            »
            4 weeks ago, # ^ |
              Vote: I like it +5 Vote: I do not like it

            In case of generalization, we can try squeezing using different constants(for higher constraints) because I assume creating test with evenly distributed boxes is probably impossible.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Don't worry, it's not about the tests, just the limitations. As Andrew wrote it can be squeezed even more. I think that for all rectangles (assume there are $$$c$$$ of them and assume $$$n=m$$$) with fixed height and width limited by some $$$x$$$ we can solve the problem in $$$O(n^2 + c \cdot x + q)$$$, so we can solve rectangles with height and width small smaller than $$$\sqrt{n}$$$ in $$$O((n+q) \cdot n \cdot \sqrt{n})$$$. Then, there are at most $$$n \cdot \sqrt{n}$$$ rectangles, so the whole complexity would be like $$$O((n+q)^{5/3})$$$.

        Btw. there are always at most $$$20-30$$$ tests. Are they tests or are they really groups of tests?

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

          USACO doesn't use grouped tests, so they're just single tests. I think it's because their servers aren't powerful enough to handle so many tests for so many people. (The camp contests have grouped tests though)

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        Uhoh... I wrote some weird bitset shit that gives $$$O(\frac{NMQ}{B} + Q 2^B)$$$ time complexity. I thought I got the intended solution and thought the problem was weird, but the model solution is actually nice.

        If you had $$$Q \le 5000$$$ then I might try to use the brain :) It doesn't look like tight limit at all.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I think tests are actually a bit weak. I managed to AC dynamic connectivity (written in part by 12tqian) solution with $$$N^2 log^2{N} + N^3/64$$$ in about 2.7/3 seconds. It's worth noting because it's in essence the "trivial" dynamic connectivity solution with relatively few constant optimizations.

        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Here's my implementation: link.

          I have no idea why changing the types of g, h, v from int to short makes it AC, but apparently it does.

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

    gold P2 can be solved with djikstra,you can reduce the number of edges to $$$O(nk)$$$ with the following observation :

    given node $$$v$$$ and the set of groups that is compatible with $$$v$$$,you only need to connect $$$v$$$ to two nodes in each such groups namely the node closest to $$$v$$$ from the right and closest to $$$v$$$ from the left

    the proof is as follows:

    assume you have a optimal path $$$A$$$ $$$\to$$$ $$$B$$$ $$$\to$$$ $$$C$$$ and that $$$B$$$ is neither the closest node to the right or left of $$$A$$$ (within the same group as $$$B$$$),then you can modify $$$B$$$ accordingly to be one of the two nodes described above with some casework

    the final step is to connect edges to $$$n$$$ whenever possible,each node atmost have $$$2k+1$$$ edges so there are atmost $$$2nk + n-1$$$ edges

  • »
    »
    4 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Could you share the "minimum feedback arc set" dp solution on the topsort pls?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      See 46:06 of this Algorithm's Live! video by tehqin. The problem Order of the Hats mentioned in the video is the minimum feedback arc set problem, and this gold problem can be reduced to it as I mentioned in my comment above. Also my solution ended up being pretty much the same as the editorial, so reading that will definitely help.

»
4 weeks ago, # |
  Vote: I like it +66 Vote: I do not like it

There were problems initially with the output files of Gold P1. Spent 2 hours before rage quitting wondering why my '3' is not their '3'.

Really appreciate though that the issue was recognised and quickly resolved after I sent an email.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +72 Vote: I do not like it

    ^ why you never take USACO at the start of the contest window

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

How to solve Silver P1 ? Does it involve bitsets ?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was the classic swapping graph-theory problem! See my code below if you're curious.

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    Consider the cycles in the final permutation produced after doing the $$$k$$$ moves. Each cycle is independent, and it can be shown that every node in the cycle has the same answer. The answer for some node in the cycle is the size of the union of the sets of all distinct locations each node in the cycle visited in the first $$$k$$$ moves (this is because each node in the cycle visits the locations of every node in the cycle). This value can be calculated in amortized linear time, as the sum of sizes of the sets is $$$\leq 2k$$$. The final complexity is $$$O(n+k)$$$.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Very Nice Solution. Thanks for the explanation!

»
4 weeks ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

My USACO Silver solutions (finished with 15 minutes to spare, only)

Problem 1
Problem 2
Problem 3

Full Disclaimer: My solutions are somewhat messily written due to the time pressure.

»
4 weeks ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

I will also share my solutions for the gold division. I’ve managed to get full credit on Problem 1, got 12/13 tests on Problem 2 (will talk about that when describing its solution), and 5/20 on Problem 3.

Problem 1
Problem 2

I won’t describe Problem 3, since I’ve only managed to solve the first Subtask. Overall, a pretty interesting and hard Gold Round. Def easier than December though (In December I’ve scored around 400 and now around 720). What do you think will be the score needed to promote?

EDIT: Regarding problem 2, I only care about the first and the last cow of each type, not about the first 2.

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

    Can you share your code for problem 2? I want to try to break it, but I don't fully understand the solution. I can also stress test it (I have a generator and a correct solution already), and I'll tell you if I can find a counter test.

    As for the promotion cutoff, I would guess either a 700 or a 750. I'm probably biased here because I solved all of the problems (and I'm good at graph problems), but this contest didn't feel absurdly hard (unlike the last one). For reference, last contest I got a 200 on gold, but in this one I ICP'd and got a 450 on platinum. I think a 700 or a 750 cutoff would be reasonable, but we'll have to wait and see.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Code on Pastebin

      It's terrible, don't judge it, please.

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

        I found a counter test, your lemma is wrong.

        Counter Test
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thank you! I guess I got lucky with the tests. I will now try to solve it properly.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +34 Vote: I do not like it

      i have 749 points (full + 11/13 + 8/20) and I'm praying for 700... Missing plat by 1 point will be super sad...

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

What does everyone expected the gold cutoff to be? I'm thinking 750-800.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm pretty curious about the silver-->gold cutoff. I made it with a 1000, but since last contest I got only 350, I was thinking maybe I got lucky and it was just an easy contest. Did you guys think it was an abnormally easy silver contest?

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

    A friend and I both found this silver contest much harder than the December contest, but maybe that's just because our skill set is different than yours. I'm interested in checking out the official solutions and cutoff scores after they come out though.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Admittedly, I still don't get the intuition behind the second December silver problem. I get the solution, but I still don't get how to come up with the solution, I guess.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I definitely thought it was easier — Q3 in the December contest felt way harder than Jan Q3

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Interestingly enough, Q3 took me the least amount of time. My times:

      Q1--2 hours (bugs :)

      Q2--1 hour

      Q3--45 minutes

»
4 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

Is it intended to make P1 < P2 < P3 or is it rather random?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    From the USACO Guide:

    Problem difficulties can be out of order, so keep that in mind before focusing down 3 hours on problem 1 and not getting anywhere. Do a good amount of thinking on each problem before deciding which ones to focus on and which to put aside. Historically, the first platinum problem has never been the hardest (though you shouldn't count on this).

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I actually found P1 the hardest, any hints on its solution?

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Try to think about the shortest odd and even paths in every graph.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Waiting for hint/editorial for P1 platinum also.

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it
        Solution for Plat P1
        • »
          »
          »
          »
          »
          4 weeks ago, # ^ |
          Rev. 3   Vote: I like it +20 Vote: I do not like it

          There is no need for a segment tree. Using the fact that

          $$$min(max(d[x][0]), max(d[x][1])) = max(d[x][0]) + max(d[x][1]) - max(max(d[x][0], d[x][1]))$$$

          helps a lot. Infinity contributes 0 to the answer.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Platinum P2 and P3?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it +5 Vote: I do not like it
    Solution to Plat P2

    For P3, ecnerwala described a solution in a comment above.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      What do you mean by not being sure? Do you mean that the tests might be not strong enough to detect an incorrect solution or that you haven't submitted during the contest?

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

        I finished this right after the contest, so I couldn't submit. I stress-tested it after against the obvious $$$O(n*m)$$$ dp.

        Edit: Submitted it after the contest and it passed.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    I wrote about P3 above. P2 is a history exam about problem "Icy Roads" from Gennady Korotkevich contest 1 from 2013.

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Where do you find these contests?

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    P2 intuitive solution w/o knowing some obscure contest
    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      A general summary of the technique is to consider the values of the "naive DP" as a function in one of the state variables, and try to identify/prove if it's convex; if so, try to maintain it or its derivative as piecewise linear or quadratic. (Depending on the problem, you may want to store inflection points or segments or something else.)

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

        Oh, this strategy seems sort of similar to the slope trick I guess (which is only for linear functions).

»
4 weeks ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

sorry to comment something during the contest. (got so many downvotes...)

This is my first time to do usaco contest brozon & silver.

I spend nearly one hour to figure out the simple dp solution for the 3rd problem, and another one hour to transfrom the second question to a well known question.

For the second, get L[i], r[i] be the first smaller position from left and right of i-th number, then answer is about distinct elements in range. This is a well known problem called D-query in spoj.

For the third, consider by row, thus two rows will be the same or complete different. We can do it using dp[N][2]. Then swap the element by main diagonal, do the dp again.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    DP was actually not needed for the 3rd problem!

    Hint
»
4 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

When will the results post?

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

For Gold problem 2, if you're currently at cow A and are looking to travel to a cow of breed B, is it correct that you only have to check the cows in B closest to A in either direction and the rightmost cow of B? Because (I think) the only time it's optimal to go all the way right is if you can get to cow N. Otherwise, let's say that the next cow you want to travel to is cow C, the cow from breed B closest to A on the left L, and the cow from B closest to A on the right R. Since the answer can be represented as (N-1) + 2 * (backwards distance traveled), the goal is to minimize the total backwards distance traveled. If C is left of L, then no matter what you'll have to travel at least A-C distance to get there, so one of your best paths are guaranteed to be A -> L -> C. If C is right of L and left of R, then at least one of the optimal paths are A -> L -> C or A -> R -> C, whichever of the two travels backwards less. Otherwise, if C is right of R, then your one of your best paths are guaranteed to be A -> R -> C.

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Welp I implemented and submitted and it got AC so I'll assume for the time being that the idea is valid xd

»
4 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Results are out!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

(int) m%k instead of (int) (m%k)

What a great way to miss an icp.