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 ?

Can you please provide me test cases where i can fail?

My code is here:
http://www.ideone.com/396m3

I understand that we are only concerned with the points mentioned, and not all the points between 1 and 10^9. After forming a segment tree and making all the updates, how can we find the longest white colored segment?

Thank you.

Also pay attention to the fact that according to the example - segment is (a;b]. I used this approach and got accepted. (O (N*N) btw :) )

WA #5:
2
-2000 0 -1000 0
0 -1000 0 -2000
> 367.0796326795

WA #7:
2
935 973 -16 438
867 30 196 463
> 1040.9330224527

WA #13:
2
0 7 0 8
6 10 6 1
> 12.7006778631

What can cause a "wrong answer" in 7-th test?

The total length of all strings (including the first one with the number N) exceeds the specified size of 4000000 bytes.

Hi,

Kindly add support for ocaml to execute timus problems.

Thanks.