What's special in test 7 ? I tried all the tests given here and I get right answer.

My algorithm is to use bfs to calculate shortest path from source to each destination. If destination is reachable, source is updated to destination else source remains same.
Anything wrong with my method ?

Why for D = 8  answer is 10?  Why 9 is not answer ?

indexes               :  0 1 2  3   4 5  6  7  8  9  10
prefix-sum of a[1..10]:  0 7 11 18 18 23 29 33 37 42 46
prefix-sum of b[1..10]:  0 5 8  13 14 16 19 22 29 31 31
diff                  :  0 2 3  5  4  7  10 11 8  11 15

t = 9, diff 11, t = 10 diff = 15   and minimum t which diff >8  is 9.

a,b=map(int, input().split())
if a==1:
    print(2)
    exit()
if (a*2)//b<a*2/b:
    print(a*2//b+1)
else:
    print(a*2//b)

when trying to update from (ux,uy) to (vx,vy)  i was checking if (vx,vy) was already popped from priority_queue.

this got me wa 22 many times. later, just out of frustation i removed the check and let (vx,vy) be updated even after it was once popped. and u know what, mysteriously got AC. of course, there has to be some logical explanation behind that.

please explain anyone?

Thanks in advance.

4
1 3
1 4
2 4
1
2 4

The correct answer is 1.

Hint: convert first tree some middle special case tree , and from this make isomorph to target tree.

Thanks!!!

Can be solved using two DFS calls and tree rerooting in O(N) while maintaining a DP array where DP[node] = sum for all paths from node to all the nodes in its subtree (considering 1 as the initial root). Tree rerooting can be used to calculate the sum for all nodes.

Hi all.
I use dfs to find the number of connected components.
If there are 2 components,then i output each of them as a single team.If there is only 1 CC,then i output numbers from 1 to n/2  and from n/2+1 to n.
Otherwise "No solution".
It seems to me correct,but....
Or tell me some tests that prove my idea's fail)

If you use Aho-Korasik+DP you should delete forbidden words which contain other forbidden words.
Example:
alphabet = "01"
forbidden words = ["100", "10", "11"] -> forbidden words = ["10", "11"]

50 50 10
qwertyuiop[]\asdfghjkl;'zxcvbnm,./ QWERTYUIOP{}|AS
aegaegu
etoijqt
tquqi
witowwt
zxcjnc
oeit
potieq
iojge
nvoq
piqper

ans=8881647922834867244791415981705771412427494861672253136057167374729235842468240763290

1 1 1
a
a

ans=0

5 10 3
abcde
abc
bc
c
ans=1048576

Edited by author 05.04.2012 20:51

1) Стоит рассмотреть, какие суммы мы можем набрать с помощью n \ 2 цифр билета (от 0 до 36, в случае с n равным 8)
2) Когда мы нашли количество сумм размера n, находим ответ, складывая их квадраты

Почему квадраты? Пусть у нас n сумм размером k. Это значит, что мы можем сопоставить в пару к первой сумме вторую, третью, ..., n - 1 и n. Со второй и последующими - аналогично

1. The given graph of "two people contradict" is bipartite (good don't contradict each other and bad don't contradict each other).
2. If two people saw third person in different places, these two people contradict.

Edited by author 20.06.2026 01:29

So, what is the statement? What am I asked to find?

I guess, to minimize the suffix, such that difference of score at the beginning of it is greater (or equal?), than six times length of the suffix.

There is O(N*log(N)) solution with O(N) memory, and only due to sorting

https://en.wikipedia.org/wiki/Prime_number_theorem

Prime numbers meets often. You can check that head-on decision (check every a XOR i, i=0,1,2...) uses a few numbers

For example:

text
5 5
1 2
2 4
3 4
1 3
3 5
2 5
Optimal route:
Start with the 'down' gear.
2→1: go downhill (0 shifts, gear stays 'down').
1→3: go uphill → 1 shift (gear becomes 'up'), score = 1.
3→5: go uphill (0 shifts). Total: 1 shift.

My algorithm outputs 2 because it doesn't account for the current gear when storing distances.

Nevertheless, I got Accepted.

1) Start with the FOUR final states.
2) Use only 15 states.
3) If it doesn't work out, then read the hint further.
unsigned char constexpr stopStates = 4;
auto constexpr go = []() {//state machine (2D array)
    std::array<std::array<decltype(+stopStates),256>,15> g;
    for(auto&e : g)    //default
        std::fill(e.begin(), e.end(), g.size());//wrong state
    for(size_t i = 0; i!=stopStates; ++i)    //default
        g[i]['i'] = stopStates, g[i]['o'] = stopStates+1;
    //===== stop states =====
    g[0]['p'] = 8;   //puton
    //in \ out
    g[1]['p'] = 12;  //put
    //input \ output
    g[2]['o'] = 14;  //on
    g[2]['p'] = 8;   //puton
    //put_on
    g[3]['p'] = 8;   //puton
    g[3]['e'] = 0;   //e
    //===== non stop states =====
    g[4]['n'] = 1;   // i -> in
    g[5]['n'] = 6;   // o -> on
    g[5]['u'] = 7;   // o -> ou
    g[6]['e'] = 0;   // on -> one
    g[7]['t'] = 1;   // ou -> out
    g[8]['u'] = 9;   // p -> pu
    g[9]['t'] = 10;  // pu -> put
    g[10]['o'] = 11; // put -> puto
    g[11]['n'] = 0;  // puto -> puton
    g[12]['u'] = 13; // ?p -> ?pu
    g[13]['t'] = 2;  // ?pu -> ?put
    g[14]['n'] = 3;  // ?puto -> ?puton
    g[14]['u'] = 7;  // ?puto -> ?putou
    return g;
    //todo: Timus - automatic construction of a MINIMAL state machine (NP ?)
}();

For this test what should be answer?
3
0 0
1 1
2 2

---
1 2 3  or 1 2 2 ?