# Something need to say

first of all, this is my first tutorial of one whole round, so there must be some places that i need to improve, if you find bug, just comment it and i will be pleasure to update.

Secondly, this round i got rk 151 in div2. it's too stupid that i came up with a wrong idea which made me waste lots of time, but after the competition, i finish them, it seems the offical tutorial still not okay. Therefore, i published this one.

Third, i wanna say thanks to my friends: samzhang[15120] & quailty[quailty]

# A. Night at the Museum

We know if we are *pos*_{a} now and we wanna go to *pos*_{b}, there are two ways.

1.clockwise, which cost |*pos*_{a} - *pos*_{b}|

2.counter-clockwise, which cost 26 - |*pos*_{a} - *pos*_{b}|

just choose the smaller one.

# B.Coupons and Discounts

there are two ways to buy pizzas:

1.one day, two pizzas.

2.two day, one pizza each day.

We know it is always better if we can buy exactly *a*_{i} pizzas in that day

but sometimes *a*_{i} can't be divided by 2

so we need to buy option#2 : one pizza each day

then *a*_{i} - 1 can be divided by 2

but don't forget *a*_{i + 1} shoude decrease 1

why only one? beacause the main idea is to make smaller influence

btw, when *a*_{i} < 0 ( after decreasing ), stop and exit.

# C. Socks

consider *l*_{i}, *r*_{i} as a non-directed edge.

so the question changes into: there are some conected components, one component must be the same color, query the minimum times to modify one vector's color.

it's easy to solve with *dsu* , first of all, we use dsu to get all conected components. For each conected component, we use the color which has the most frequency to colour this connected component.

so we get an algorithm.

# D.80-th Level Archeology

imagine we need to sort an array *A*

we want *A*_{i} < *A*_{j} (*j* > *i*), we just need to make *A*_{i} < *A*_{i + 1}

this problem is the same way, if we want all words are sorted, we just need to compare each pair of adjacent words.

consider about the following two words:*A* *and* *B*(*A* *is* *in* *front* *of* *B*)

According to the notice, we know for each *i* we need *A*_{i} ≤ *B*_{i}

let x represent the answer, consider two elements, *A*_{i}, *B*_{i}

if *A*_{i} = *B*_{i}, skip

if *A*_{i} < *B*_{i}, absolutely

if *A*_{i} > *B*_{i}, we also say that

as soon as *A*_{i} ≠ *B*_{i} is satisfie, we can skip the rest.

how to solve these inequalities? just use Segment_Tree or Bit or Difference

i recommend Difference because *C* ≤ 10^{6}

# E. Funny Game

let *dp*[*i*] represent the maximum difference when Petya is first,and he got prefix [1, *i*]

it's easy to see that

*s*[*i*] represent

do a change, we have

use suffix maximum array is enough.

consider transform as swaping characters.

# F. Video Cards

it is easy to notice that *A*_{i} ≤ 2 × 10^{5}

so we use an array to count the number of *A*_{i}

after that, we suppose *A*_{i} is the base

then we know all *P* that *P* = *k* × *A*_{i}, find how many times *P* appears after modifying

it is easy to solve by the array we created.

because of this is harmonic progression, so it is an algorithm.

Thanks for reading!

if you have questions or some places i am wrong, just point it out to make me improve!

You don't need a segment tree for problem D, just store three segments and update them each time you consider a new pair.

A question considering problem F: "then we know all P that P = k × Ai, find how many times P appears after modifying it is easy to solve by the array we created." What do you mean by this? Could you elaborate further on this statement?

Using terminology of the question , suppose we fix

Aias the leading video card , all secondary cards that we pick must be multiples ofAii.eP=k*Aifor somek, wherePis the secondary card . To find the maximum sum we can get by fixingAias the leading card , notice that in the original array elements less thanAican't be picked while all elements > =Aican be picked . Another observation is that since you can change secondary cards that you pick every number in range [k*Ai, (k+ 1) *Ai) would have to be reduced tok*Ai, and count of such numbers can be obtained by maintaining a prefix count array .Thanks, but I still don't get this: "and count of such numbers can be obtained by maintaining a prefix count array ." What do you mean by "such numbers"? How do I use a prefix array to count them?

Ah, I started understanding this. Do we have to sort the initial array in a decreasing order?

s[a[i]] ++;

ask how many a[i] appears in [L,R] equal to ask

prefix sum array can solve it in

O(1).Would you explain your solution of problem D?

which part you don't understand? :)

I do not understand the dp in E. Your dp implies if first person chooses i , then second person will select atleast first i indices. Also how is the effect of new stickers is being taken care of.

that's why we need solve this dp from n to 1.

keep mind that dp[i] represent maximum difference when the first person took [1,i]

so we don't care who is end.

I am asking the reason for it. It is still not clear to me.

let A represent the score of Petya

B represent the score of the other person

then

because the other person also takes the best choice

so we need

s[i] -dp[j] =s[i] - (A-B) =s[i] -A+Bjust like you do a change.

you may ask, then dp[i] represent B not A

but remeber, we've rotated, so it is equal to from B to A.

Sorry I misunderstood the problem.. Got it now!

:) in fact i misunderstood the problem at first too.

Auto comment: topic has been updated by PengsenMao (previous revision, new revision, compare).