Это первая реакция сообщества на такие посты — минус не раздумывая. Затем, чем ближе к началу, тем больше плюсов от людей вроде вас. После же контеста такие посты обчычно плюсуют те, кто писал решения, спрашивал решения, читал решения.

P.S Все, кроме первого предложения — мои догадки)

По моему лучше всего смотреть на clist.by. Не забуду никогда :)

И об lunch time завтра.

Java C++

Whisper to admins.

Вроде и этого не хватит.

Смотри тест типа 1 3 1 4 2 4

Тут рулит интервал (2,3) без концов

такой тест 0 1 0 1 0

Тест 0 2 0 2 0 2 0 оптимальное y = 1.

Может y[i] — 0.5 (или же +-1 если умножить все на 2)?

Рекомендую посмотреть на вот этот тест: 0,2,1,2

Потому что ответ не обязательно в вершине ломаной достигается. Вот тест: 0 3 -4 7 2 6.

Ну надо проверять не только концы, например, тест "1,2,1,2,1,2,1,2,1". Я удвоил координаты и проверял середины — привет integer overflow :(

Можно так:

1)Посчитаем для каждой пары династий (i и j) l[i][j] и r[i][j] — насколько влево и вправо можно сдвинуть одну относительно другой, чтобы не было противоречий (считается просто с учетом сражений). Потом запускаем для l и r Флойда.

2)Посчитав l и r, на запросы отвечать легко: просто смотрим, возможно ли пересечение правления соответвующих королей.

If the length of the string is at most 26, we can build a string using each letter only once. If the length is more than 26, we should use all the letters and always put all occurrences of a letter next to each other. The answer can be calculated using dynamic programming.

For L <= 26:

The answer is 26*..*(26-L+1), since we have 26 letters for the first choice, 25 for the second one, etc. The minimum weight of a word is 0.

For L > 26:

First of all, we should use each letter at least once (since we could easily lower the weight using the unused letter). What to do with the remaining L — 26 choices? Actually, it doesn't matter which letter we pick for each of these choices, since, as long as all occurrences of a letter are next to each other, they contribute to weight identically. For example, if we already have AAB (for simplicity assume that A and B are the only letters in the alphabet) picking A and forming AAAB, or picking B and forming AABB adds the same weight (+1). So we have L — 26 "balls", and we need to distribute them to 26 "urns". The number of ways to do that is
C[balls+urns-1][urns-1] = C[L-26+26-1][26-1] = C[L-1][25]. Also, we can arbitrarily rearrange groups of identical letters, and the answer becomes
C[L-1][25] * 26!. The minimum weight of a word is L — 26.

Brute Force, каждый раз добавляешь в какой-то список одного игрока, сперва в 1 команду, потом во 2, потом в 1 и так далее. Добавляешь первого не добавленного из векторов preference1 и preference2.

У меня вопрос. Я решил, но тестирование не прошло. Затем в practice я отправил тот же код, но теперь я получил ac. Как так?

#include <iostream>

using namespace std;

#include <vector>


    int us[10000];

class
TeamsSelection{
public: string simulate(vector <int> preference1, vector <int> preference2){
        int i, j; i = j = 0;
                string s = "";

        while(i < preference1.size()){
            while(i < preference1.size() && us[preference1[i]] != 0) i++;
            us[preference1[i]] = 1;
            while(j < preference2.size() && us[preference2[j]] != 0) j++;
            us[preference2[j]] = 2;
        }

        for(j = 1; j <= preference1.size(); j++)
            s += char(us[j] + 48);
        return s;
    }
};