Доброго Вам утра, дня, вечера, ночи.Приветствуем Вас на прекрасном рандомизированном контесте, который подготовила для Вас команда Саратов СУ 3 (Давтян Эдвард, Холкин Павел, Кудряшов Игорь). Сегодня вам предстоит поближе познакомиться с Валерами и Валериями и помочь им во всем, чего бы они не попросили. Надеемся на то, что соревнование Вам понравиться, ведь мы очень старались. Благодарим за помощь в подготовке контеста Артема Рахова, Юлию Сатушину и Валерия Дмитрия Матова. Кроме того отдельное спасибо компании ВКонтакте.
История нашей команды началась в этом году в летней школе "Дубки" и едва там не закончилась. Нас спасли Петрозаводские сборы, на которые мы и уехали из "Дубков". Как вы могли заметить по предыдущему предложению, у нас в команде два капитана: один капитан и один Кэп (всего два). Но несмотря на это, мы очень дружная и серьезная команда и у нас очень хорошо развит командный дух. Тем временем до начала соревнования остается совсем немного.
Всем участникам мы желаем успехов и высокого рейтинга!
Высокого рейтинга !!!!
Ты слишком незадрот, чтобы быть в СУ 3.
СУ З в смысле СУ ЗЕ.
"В следующих n строках заданы два символа Ai и Bi, (...), означающие, что разрешено заменить символ Ai на символ Bi"
Где здесь неоднозначность?
Пусть в строке 1 первая буква а, во второй б.
И есть правила например такие
a c 1
b d 1
d c 1
а - > c и b -> d -> c
Понятно?)
а транзитивность переходов я учел Флойдом
а я думал над ней около 1 ч 50 мин, всматриваясь во все возможные опечатки, которых там не было)
a -> d -> e -> c
b -> f -> c.
Ну про это уже выше написали :)
Хотя возможно, он зарегил 20 ботов abc, abcd, abcde и т.д. =)
Умный человек. Он вот на скорость валит решения, а я вообще не разобрался, где и как это делать =(
Что-то у меня траблы со взломом.
Пишет посылка уже взломана, хотя 100 раз обновлял комнату, смотрел историю кода, там никаких взломов не показано.
У кого-то были такие проблемы?
Может из-за того что в моём тесте 20000 чисел? через Ctrl-C - Ctrl-V вбил, так как генератор не удалось отправить((.
I also want to know the spected solution for problem B.What is wrong in this idea?I have used a combination of printf and cout. Will that be a problem?
a
e
4
a b 1
b c 1
c d 1
d e 1
Я единственный такой наивный мальчик, который писал LCA в D? =)
Хоть оно и прошло, но все же можно было обойтись куда более простым решением =( Не подумал я, что на этом серваке 1000 * 100000 прокатит. Где вообще можно характеристики системы глянуть? И описалово для компиляторов и все такое. И как например чужие решения валить? Я видимо совсем от жизни отстал, что не разобрался на контесте. Вот просто не нашел, как просмотреть чужое решение, и все тут.
А 1000*100000 проходило? Я например побоялся писать. Кроме LCA работало битовое сжатие. Для каждой точки захраним в каких окружностях она лежит и проксорим для ответа на запрос. Итого 1000*100000/32.
А как тогда посчитать количество единичных битов?
Нам ведь нужно просмотреть все 1000 бит?
заходило с запасов в 5 - 6 раз
Идея в следующем:
1. Если искомые префикс и суффикс пересекаются, то общая их часть остается с искомым знаком, и следовательно этот случай эквивалентен случаю когда взяты те же суффикс и префикс, но без общей части, например:
(s1 [s2 )s3 ] эквивалентно (s1)s2[s3] (s1,s2,s3 - некоторые подпоследовательности).
2. Пусть сумма последовательности элементов A1 .. An равна S. Тогда при инвертации знаков получаем -A1, -A2 .. -An, а сумма соответственно изменяется на -S, то есть сумма чисел на отрезке при инвертации просто изменит свой знак.
3.Исходную задачу можно рассмотреть в таком ракурсе: нужно выбрать из последовательности непрерывную подпоследовательность (ту, что останется между префиксом и суффиксом), а вне ее инвертировать все числа. Тогда если сумма чисел всей последовательности равна S, а сумма выбранной подпоследовательности S1, то итоговая сумма даст -(S-S1) + S1 = 2*S1 - S - это и есть та самая величина, которую нужно максимизировать. S- постоянная, => нужно максимизировать S1, т.е. найти в заданной последовательности непрерывную подпоследовательность с максимальной суммой, а это делается линейно:
mx = 0;
Hope this will be useful :)
UPD: во, нашел кнопочку "редактировать". отредактировал.
4
bbbb
or
10
4
bbbb
for (size_t i = 0; i < LETTER_CNT; i++)
for (size_t j = 0; j < LETTER_CNT; j++)
for (size_t k = 0; k < LETTER_CNT; k++)
Неправильно:
ranges[i][j] = Min(ranges[i][j], ranges[i][k] + ranges[k][j]);
Правильно:
ranges[j][k] = Min(ranges[j][k], ranges[j][i] + ranges[i][k]);
// in the main function
if(strlen(sa)!=strlen(sb)){
puts("-1");
return -1;
}
Unfortunately, my code is always getting Runtime Error for test 3.
However, if "return 0" replace "return -1", I get Accepted.
Why?
sorry for my poor English!Thanks!
In that case, O(MK) solution will get TLE, and problem D can be a bit harder to get accepted.
Print the maxSum;
PS: Sorry for my poor English...
3
-1 -2 -3
there are many possible answers:
(1) -1 -2 -3 sum= -6 (here the prefix is empty and suffix is empty)
(2) -1 -2 3 sum=0 (here the prefix is empty and suffix is {-3}, multiply by -1 become {3})
(3) -1 2 3 sum=4 (here the prefix is empty and suffix is {-2 -3}, multiply by -1 become { 2 3} )
(4) 1 2 3 sum=6 (this is the maximum possible answer, prefix is empty and suffix is {-1 -2 -3} multiply by -1 become {1 2 3})
etc
*for all numbers in the prefix and suffix, multiply all numbers in prefix and suffix by -1. so for test case:
Hope that this help :http://codeforces.net/blog/entry/735
Test case 1 in final test of problem E is same as example test 1. Right or wrong?