A note on CF1809F (EDU145F) Traveling in Berland

Revision en6, by GrandLisboa, 2023-03-24 20:23:25

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

//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] gas 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); //By k gas at i using k burbles and the left get(i, curi) - k gas using 2*(get(i, curi) - k) burbles.
curi = ne(curi);
}
}
finish:

#### History

Revisions

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