A note on CF1809F (EDU145F) Traveling in Berland

Revision en12, by GrandLisboa, 2023-03-24 20:46:55

Problem: Link

Submission: Link $$$O(n)$$$, 92ms!

Part1: Hint

By looking at the $$$4$$$ test cases, we find that answers for $$$b[i] = 1$$$ are the same.

Part2: The greedy strategy (for each index $$$i$$$)

First, we define some macros for convenience:

The previous index of $$$x$$$: #define pr(x) ((x) == 1 ? n : (x) - 1)

The next index of $$$x$$$: #define ne(x) ((x) == n ? 1 : (x) + 1)

If $$$b[x]==1$$$, rt(x) denotes the place of the next $$$1$$$ in the loop: rt(x). For example, let $$$b$$$ be an $$$1$$$-indexed array $$$[2, 1, 2, 1]$$$, then $$$rt(2)==4$$$ and $$$rt(4)==2$$$. Note that $$$rt(i)==i$$$ could happen, for example, $$$b==[2, 1, 2]$$$, then $$$rt(2)==2$$$. rt could be pre-calculated using a stack.

get(i, j): The liters of gas we need to go from $$$i$$$ to $$$j$$$, both inclusive and $$$1$$$-indexed. For example, if $$$a=[1, 2, 3, 4]$$$, then $$$get(1, 2)==a[1]+a[2]==1+2==3$$$ and $$$get(4, 2)==a[4]+a[1]+a[2]==4+1+2==7$$$. The $$$get$$$ function could be pre-calculated using the prefix sum.

We need to maintain an array $$$c$$$ in the algorithm. $$$c[i]$$$ denotes the minimum burbles we need to pay from the previous place $$$j$$$ where $$$b[j]==1$$$ to $$$i$$$. $$$j$$$ may be equal to $$$1$$$. For example, if $$$b==[1, 2, 1]$$$, then $$$c[3]$$$ denotes the minimum burbles we need to pay from $$$3$$$ to $$$3$$$, which is $$$a[3]$$$. $$$c[2]$$$ denotes the minimum burbles we need to pay from $$$1$$$ to $$$2$$$. Note that this $$$c$$$ is well-defined iff there's at least one $$$i$$$ such that $$$b[i]==1$$$. So we just need to output the case where all $$$b[i]$$$ equal to $$$2$$$.

//The Initialpoint
int i = initialpoint;
while(true){
    (1) If you are at the destination, which is the same as the initialpoint, goto finish.

    (2) When you stay at i where b[i]==2, just pay 2a[i] for a[i] liters that enables you to move from i to ne(i). let i = ne(i);

    (3) When you stay at i where b[i]==1, set initialized2 = true and curi = i, and do the following inner while loop. Also, we need to calculate the array c.
    while(initialized2 || curi != rt(i)){ 
        //rt(i): The next i in this trip with b[i]==1
        //Why do we need this initialized2? Because curi before the loop is i, which may be equal to rt(i) at the beginning, in this case we still need to go into this loop!
        if(curi == initialpoint) goto finish;
        initialized2 = false;
        if(get(i, curi) <= k) c[curi] = get(i, curi);
        else c[curi] = k + 2*(get(i, curi) - k); //Buy k liters at i using k burbles and the left get(i, curi) - k liters using 2*(get(i, curi) - k) burbles.
        curi = ne(curi);
    }
}
finish:

You may worry about the line if(get(i, curi) <= k) c[curi] = get(i, curi);. In this line, if get(i, curi) <= k, we just buy get(i, curi) instead of filling all $$$k$$$ liters into the tank. You may think it would be better if we grasp the chance (that we are at some good place that $$$b[i]==1$$$) to make our tank full. But, our algorithm is correct. Whenever our algorithm is forced to buy one liter using two burbles, every other strategy needs to. If we have not met an $$$i$$$ such that $$$b[i]==1$$$ in our trip, then we can only buy one liter using two burbles, no matter what our strategy is. Otherwise, if we are forced to buy one liter using two burbles at some place $$$i$$$ where $$$b[i]==2$$$, let $$$j$$$ be the last $$$1$$$ we meet ($$$b[j]==1$$$). According to our algorithm, $$$get(j, i) > k$$$, which means our algorithm already makes the tank full at place $$$j$$$. Even if that, it still faces the lack of gas issue at $$$i$$$ and has to pay for more expensive liter. For other strategies, the gas amount is at most $$$k$$$ at place $$$j$$$, so it must also face the lack of liter issue at $$$i$$$, and has to pay for more expensive liter also!

When there is at least one $$$b[i]==1$$$ in the array, it would be beneficial to decompose our journey into 1222222 blocks. There is at least one block. We would discover that when our journey starts at the start of the block, it always has $$$0$$$ liter!

Tags greedy, implementations, stack

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en25 English GrandLisboa 2023-03-24 21:36:45 71
en24 English GrandLisboa 2023-03-24 21:17:21 2 Tiny change: '$get(i, j) liters of' -> '$get(i, j)$ liters of'
en23 English GrandLisboa 2023-03-24 21:16:32 8
en22 English GrandLisboa 2023-03-24 21:16:05 6 Tiny change: ' $O(n)$, 92ms!\n\n**P' -> ' $O(n)$, 93ms!\n\n**P'
en21 English GrandLisboa 2023-03-24 21:11:47 8
en20 English GrandLisboa 2023-03-24 21:10:54 0 (published)
en19 English GrandLisboa 2023-03-24 21:10:42 31
en18 English GrandLisboa 2023-03-24 21:09:50 398
en17 English GrandLisboa 2023-03-24 21:06:58 98
en16 English GrandLisboa 2023-03-24 21:05:42 158
en15 English GrandLisboa 2023-03-24 20:56:25 333
en14 English GrandLisboa 2023-03-24 20:53:59 159
en13 English GrandLisboa 2023-03-24 20:52:42 442
en12 English GrandLisboa 2023-03-24 20:46:55 381
en11 English GrandLisboa 2023-03-24 20:43:09 473
en10 English GrandLisboa 2023-03-24 20:36:26 518
en9 English GrandLisboa 2023-03-24 20:30:55 321
en8 English GrandLisboa 2023-03-24 20:27:55 27
en7 English GrandLisboa 2023-03-24 20:27:23 369
en6 English GrandLisboa 2023-03-24 20:23:25 541
en5 English GrandLisboa 2023-03-24 20:17:28 573
en4 English GrandLisboa 2023-03-24 20:11:33 120
en3 English GrandLisboa 2023-03-24 20:08:49 310
en2 English GrandLisboa 2023-03-24 20:05:22 573
en1 English GrandLisboa 2023-03-24 19:56:21 194 Initial revision (saved to drafts)