A note on CF1809F (EDU145F) Traveling in Berland

Revision en3, by GrandLisboa, 2023-03-24 20:08:49

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) The next $$$1$$$ in the loop: rt(x). We will describe it later. 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$$$.

while(true){
    (1) If you are at the destination, break.

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

    (3) When you stay at an i where b[i]==1:
}
outer loop:
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)