12
12 5 3 11 2 8 4 9 1 6 10 7

answer: 34650  in example output.

But, following full check test prints 6300.

-----
static bool match(int a[], int n, int b[], int m){
    if (n != m) return false;
    if (n == 0 && m == 0) return true;

    int i = std::max_element(a, a + n) - a;
    int j = std::max_element(b, b + m) - b;

    return i == j && match(a, i, b, j) && match(a + i + 1, n - i - 1, b + j + 1, m - j - 1);
}
int main()
{
        int n = 12;
        int a[] = { 12, 5, 3, 11, 2, 8, 4, 9, 1, 6, 10, 7 };
        int b[] = {  1, 2, 3,  4, 5, 6, 7, 8, 9, 10, 11, 12};
        int ans = 0;
        do{
            if (match(a, n, b, n)) ++ ans;

        } while (std::next_permutation(b, b + 12) );

        printf("ans = %d\n", ans);
        return 0;
}

I solved it using pretty straigtforward DP O(n * m^2), obviously it's just a complexity without any additional factors but it doesn't seem to be fitting time limit. Somehow it did. But I wonder, is there any more intricate idea for a faster solution?

how to know when there are no more inputs

Что за 26 тест? Никак не могу его победить

why wa#17?
help pls

Edited by author 23.11.2018 08:05

New tests have been added. All accepted solutions have been rejudged. 15 out of 20 authors lost the Solved status for this problem.

def word_to_num(word):
    d=
{'a':'2','b':'2','c':'2','d':'3','e':'3','f':'3','g':'4','h':'4','i':'1','j':'1','k':'5','l':'5','m':'6','n':'6','o':'0','p':'7','q':'0','r':'7','s':'7','t':'8','u':'8','v':'8','w':'9','x':'9','y':'9','z':'0'}
    s=''
    for i in word:
        s+=d[i]
    return s
from itertools import permutations
while True:
    num_dict={}
    num_list=[]
    word_list=[]
    num = input()
    if num=='-1':
        break
    loop_len = int(input())
    for i in range(loop_len):
        word_list.append(input())
    for item in word_list:
        num_dict[word_to_num(item)]=item
        num_list.append(word_to_num(item))
    perm = permutations(num_list,2)
    x=0
    for k,v in list(perm):
        if k+v==num:
            print(num_dict[k]+' '+num_dict[v])
        else:
            x += 1

    if x==loop_len*(loop_len-1):
        print('No solution')

Правда вне рейтинга:)

One way I can think of is to sort edge by cost
and use dynamic connectivity

But it's very hard to implement :(
What's the better solution?

O(n*sqrt(n)*log(n)) enough?

Upd: OK with this complexity. But 2.7 c++. How to solve with 0.1 second?

Edited by author 21.02.2026 00:26

Any way to remove test miners from the board?

Oleg Vasilenko (Chelyabinsk) - https://acm.timus.ru/status.aspx?space=1&num=1589&author=55499&from=10681678

Ruben Ashughyan - https://acm.timus.ru/status.aspx?space=1&num=1589&author=202317&from=10649282

kostan3 - https://acm.timus.ru/status.aspx?space=1&num=1589&author=121982 (looks suspicious, is it a system account or something?)

Can you give me some "extra" test or smth like that... My prog passed all my tests but i get wa#3...

Thnx!

Accepted:)

Edited by author 18.02.2026 21:32

тест 1: n=9 k=2
тест 2: n=1 k=1
тест 3: n=10 k=1
тест 4: n=8 k=1
тест 5: n=10 k=2
тест 6: n=7 k=2
тест 7: n=1 k=2
тест 8: n=2
тест 9: n=10 k=5
тест 10: n=9 k=5
n=3,4,5,6 не встречается...

incorrectly selected transfer

static void Main(string[] args)
{
   int n = int.Parse(Console.ReadLine());
   int[] values = new int[n];
   for (int i = 0; i < n + 1; i++)
      {
         string[] str = Console.ReadLine().Split();
         int a = int.Parse(str[0]) - 1;
         int b = int.Parse(str[1]) - 1;
         int c = int.Parse(str[2]);

         for (int j = a; j <= b; j++)
            {
               values[j] += c;
            }
      }

   Console.Write(string.Join(" ", values));
}


It's simple algorithm. How to speed it up? Which algorithm should I use?

Edited by author 21.01.2026 21:22

pls some test for W6

Hi, I writed this post because I wanted to share with you some of the test cases* that helped me a lot at the time. I hope it helps you :)

--> Test 1:

1
A B C

--> Answer:

A undefined
B undefined
C undefined

------------------------------

--> Test 2:

5
Isenbaev A B
A B C
D Q P
C H N
G N P

--> Answer:

A 1
B 1
C 2
D 5
G 4
H 3
Isenbaev 0
N 3
P 4
Q 5

------------------------------

--> Test 3:

13
Fominykh Isenbaev BBB
BBB CCC AAA
Ayzenshteyn Oparin Samsonov
Ayzenshteyn Chevdar Samsonov
Dublennykh Fominykh Ivankov
Burmistrov Dublennykh Kurpilyanskiy
Cormen Leiserson Rivest
Oparin AA AAA
Isenbaev Oparin Toropov
AA DD PP
PP QQ RR
RR SS TT
TT Toropov Oparin

--> Answer:

AA 2
AAA 2
Ayzenshteyn 2
BBB 1
Burmistrov 3
CCC 2
Chevdar 3
Cormen undefined
DD 3
Dublennykh 2
Fominykh 1
Isenbaev 0
Ivankov 2
Kurpilyanskiy 3
Leiserson undefined
Oparin 1
PP 3
QQ 4
RR 3
Rivest undefined
SS 3
Samsonov 2
TT 2
Toropov 1

------------------------------

--> Test 4:

3
Isenbaev A B
A B C
A Q W

--> Answer:

A 1
B 1
C 2
Isenbaev 0
Q 2
W 2

------------------------------

*(All test cases were made by other users, so you'll probably found them in other Posts/Topics/Discussions).

Acknowledgments to:
-> "Vit Demidenko" & "Nathalie"
-> "Pavel Nikolov"
-> "mccolt89"
-> "Megakrit"


-How I solved it:

I solved this problem in Java, for that, I used:

->1 java.util.Scanner
->1 java.util.HashMap
->1 java.util.TreeMap
->3 java.util.HashSet
->1 java.util.LinkedList
->? java.util.StringTokenizer (or you can just simply use the Scanner method "next()").

(The structures can be declared inside loops or other structures).

Hope all this helped you :)


Edited by author 08.04.2020 00:48

Edited by author 08.04.2020 00:49

See title I can currently solve problems under a rating of 50(I am a newbie) comfortably but I don't quite get how the difficulty scales really with some problems having a rating of 15000 which seems confusing. I just would like someone who has some knowledge to explain how difficulty scales numerically relative to some standard problems take codeforces or any major competitive programming competition as a reference

Edited by author 08.01.2026 08:49