Блог пользователя Nerevar

Автор Nerevar, 14 лет назад, По-русски

Всем доброго времени суток.

Сегодня на Codeforces необычный день: сразу два раунда, днем, да еще со столь небольшим перерывом. А объясняется это тем, что сегодня в Саратове проходит IX Региональная командная олимпиада школьников по программированию, и задачи с нее (а они весьма неплохие) решено было дать на раунды Codeforces.

По этой причине авторов у сегодняшних задач много. Не поленюсь перечислить весь состав жюри олимпиады, все члены которого хорошо знакомы вам как авторы задач на Codeforces. Это Артем Рахов, Николай Кузнецов, Наталья Бондаренко, Геральд Агапов,Полина Бондаренко, Иван Фефер, Эдвард Давтян, Игорь Кудряшов, Павел Холкин и я. Все мы отлично потрудились и надеемся, что вы оцените наши задачи.

Отдельное спасибо стоит сказать Марии Беловой и Юлии Сатушиной за перевод задач на английский язык.

Обращаю ваше внимание на то, что сегодня во всех задачах будет файловый ввод-вывод. Однако генератор для взлома, как обычно, должен выводить в stdout.

Желаю всем удачи на контестах!

UPD: Результаты 35-го раунда. Поздравляем победителя, участника с ником Naginchik, с впечатляющим дебютом!

UPD: Результаты 36-го раунда.

Ссылки на разборы задач: A, B, C, D, E.

  • Проголосовать: нравится
  • +27
  • Проголосовать: не нравится

14 лет назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится
Удачи всем!!!
Высокого рейта!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I don't understand what would be the difference if all problems have file IO?? can anyone please explain??
  • 14 лет назад, # ^ |
      Проголосовать: нравится +4 Проголосовать: не нравится
    It means that you should read input data from the input file and write output data to the output file. Names of the files will be in problem statements, I think
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      i havnt seen these replies of you guys and had plenty of idleness limit exceed during contest :(( and many coders had the same problem too. 
      I think it should have been explained before :(

  • 14 лет назад, # ^ |
      Проголосовать: нравится +12 Проголосовать: не нравится
    You should read and write from and to files input.txt and output.txt.

    So, for exaple, in C++ you should have something like
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    at the beginning of your solution.
    And usually you should not.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Всем удачи! Особенно HKL-ышникам ;)
14 лет назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
См. комментарий ниже на английском.
14 лет назад, # |
Rev. 3   Проголосовать: нравится +16 Проголосовать: не нравится

For those who are not familiar with file IO, there are several solutions of "A*B" problem in some popular programming languages:

Pascal / Delphi:

var
    a, b: longint;
begin
    assign(input, 'input.txt');
    assign(output, 'output.txt');
    reset(input);
    rewrite(output);
    read(a, b);
    writeln(a * b);
    close(input);
    close(output);
end.
C/C++:
#include <stdio.h>
int main() { int a, b; freopen("input.txt", "rt", stdin); freopen("output.txt", "wt", stdout); scanf("%d %d", &a, &b); printf("%d\n", a * b); return 0; }
Java:
import java.io.*;
import java.util.*;

public class Solution {
    public static void main(String[] args) throws FileNotFoundException {
        Scanner s = new Scanner(new File("input.txt"));
        int a = s.nextInt();
        int b = s.nextInt();
        s.close();

        PrintWriter writer = new PrintWriter("output.txt");
        writer.println(a * b);
        writer.close();
    }
}
14 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
edit: I had misunderstood the problem
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Can contestants from division 1 find out their rating in this contest if they were in div. 2?
14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится
Хорошая утренняя тренировка; пора на лекции :D
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
What is test 8 for problem B? (Round 35)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня бага на восьмом была из-за того, что я сначала не стал юзать map и искал нужную строку в векторе бинпоиском. Потом стало понятно, что бинпоиск работает только для сортированного массива.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
объясните как работает система взлома чужих исходников?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
Лучи ненависти за файловый ввод/вывод. Не делайте так больше, пожалуйста. А если делаете, то предупреждайте заранее капсом полужирным 20 кеглем красного цвета.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Повезло, что писал 2-й див сначала. Получил -5 с ошибкой решение "зависло". Порадовался, и увидел маленькую черную надпись о том, что таки input.txt.
    +1 к красному капсу. Лучше даже инпут и аутпут красным выделять.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Интересно, почему картинки http://codeforces.ru:8080/renderer не отображаются. Или это только у меня?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Задача D в 35 раунде - обычный рюкзак, но многие сдали ее, использую жадную эвристику. Слабые тесты, или жадность здесь дает оптимальное решение?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Жадность дает оптимальное решение. Задача сводится не к рюкзаку в общем случае, а к рюкзаку, где все вещи имеют одинаковую стоимость (единицу). А такой рюкзак решается жадно.
14 лет назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится
Я многое понимаю, но по-моему давать настолько известную задачу  - уже чересчур!
P.S. - условие конечно немного отличается на самом деле, но ведь метод решения тот же
P.P.S - интерестно, какой ответ на тест
2
5 10 10
5 10 10
Из условия не ясно, это 5 или 10(так как толщиной стенок  и дна можно пренебречь).
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Общие разве что картинки. В той задаче необходимо выбрать такой порядок составления, при котором высота будет минимально и вывеси эту высоту. Сам я раньше задачи такой не видел, да и вообще не люблю геометрию. Зато бинарный поиск люблю, что меня и спасло.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится
      порядок там, судя по ограничениям, просто перебирается.
      дальше это та же самая задача.
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    В условии сказано: "1 <= r < R <= 10000".

    Такого теста не может быть.

  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится
    deleted
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Чего-то я не понимаю в задаче C (Тарелки) раунда 36.

Мне кажется, что нужно рассмотреть каждую пару тарелок (нижняя, верхняя).

Разобрать три случая для дна верхней тарелки (оно < r нижней, > R нижней и в промежутке).

Разобрать два случая для верха верхней тарелки (как вторая тарелка во втором примере и как третья тарелка во втором примере).

Взять по всем случаям всех нижних тарелок максимум позиции, и это будет позиция верхней тарелки.

Поскольку край тарелки - отрезок прямой, условия можно проверять только на концах отрезков.

Все ли случаи тут учтены?
  • 14 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    Да, я тоже эту задачу про тарелки где-то уже решал.

    (не помогло правда =) )

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Что означает вердикт по challenge'у 

"Неизвестный вердикт:OTHER"?

14 лет назад, # |
  Проголосовать: нравится +12 Проголосовать: не нравится

Вот это да!

До этого даже не предполагал, сколько можно "наломать", причем используя мега-элементарный тест. Оказывается, что ну очень многие забывают проверить задачу не только на максимальном тесте, но и на минимальном.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
хотелось бы узнать 15й тест задачи C в 36ом..
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
А тесты на этот раз будут доступны для скачивания?
14 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится
А разбор задач планируется? Особенно интересно как B и D в Codeforces #36 решать, может кто-то рассказать?.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    в D написать наивное решение, и внимательно посмотреть на получающийся паттерн :)
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      Да я понял что наивное, но я какой-то ньанс не учёл, в результате решение отдельные тесты не проходило.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    И еще про С и E хотелось бы услышать.
    • 14 лет назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
      В задаче C можно сдать решение за O(N2).
      Поставим первую тарелку. Далее будем действовать по следующему алгоритму.
      Возьмем очередную тарелку с номером i. Необходимо определить, на какой высоте от нулевого уровня она будет размещена. Очевидно, что эта величина будет находиться в пределах [Hi - 1, RES], где RES - решение для башни из (i - 1)-ой тарелки. Бипоиском можно подобрать такое положение из этого интервала, что никакие из тарелок не пересекаются. Это сделать несложно, достаточно знать школьную геометрию.
      Если надо найти радиус тарелки с нижним радиусом R1 и верхним R2 и высотой H на высоте h от дна, то она равна R1 + ((R2 - R1) * h) / H.
      Ну и для каждой итерации бипоиска можно пробежаться по всем уже поставленным тарелкам и проверить. Достаточно проверить не превышает ли R1 ширины этой тарелки на данной высоте. Если R2 ниже верхней отметки данной тарелки, то проверить не больше ли она ширины этой тарелки на этой отметке. Если же R2 выше, то надо проверить верхний радиус данной тарелки с радиусом тарелки с номером i (текущей) на заданной отметке.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится
      Е сводится к построению Эйлерова цикла или пути.
      Сначала смотрим сколько компонент связности.
      Если больше 2, то очевидно "-1"
      Если равно 2, то в каждой компоненте связности нужно построить либо Эйлеров цикл, либо Эйлеров путь.  Если хоть в одной компоненте не получается "-1"
      Если 1 компонента связности. Смотрим кол-во вершин с нечетными степенями.
      Если 0 вершин, то находим Эйлеров Цикл. А его не сложно разбить на два пути
      Если 2 вершины, то находим Эйлеров путь. И его тоже не сложно разбить на два пути.
      Если 4 вершины, то можно добавить вспомогательное ребро соединяющее две нечетные вершины. Найти Эйлеров путь и удалить вспомогательное ребро и получится два пути.
      Иначе "-1"
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Задачу D не сдал.
    Задача B сдается рекурсивным моделированием. Одна из реализаций:
    Передаем рекурсии 4 параметров: X1, Y1 - координаты левого верхнего угла области, N - его размерность и F - надо ли закрасить полностью всю область в черный цвет (TRUE) или же надо продолжить зарисовывать фрактально (FALSE). Если N = 1, то при F = FALSE необходимо просто покрасить всю область (1 клетка) в белый цвет.
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

    B:

    Рассмотрим точку (x,y) ответа.

    Если для какого-то c=n^d где 0<=d<k точка ((x/с)%n,(y/c)%n)  шаблона черная, то и (x,y) - черная.

    За O(N*N*K) задача сдается тремя вложенными циклами.

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is test 13 for problem D? (Round 36)
14 лет назад, # |
  Проголосовать: нравится +2 Проголосовать: не нравится

В задаче D почти все валились на очень простом тесте:

1 1

3 3

Дело в том, что общая закономерность не выполняется в этой задаче для K = 1

  • 14 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится
    Да уж) Мне жутко повезло, что за 12 минут до конца меня на этом тесте взломали, и я успел перепослать. Спасибо))
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Из-за чего появляется ошибка тестирования "ошибка тестирования"? Без указания теста, красненьким шрифтом. Посылка номер 150120 у меня, например, или 150118 у uwi?
  • 14 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится
    это ошибка проверяющей системы... ваш код тут не причем!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I got this error : Idleness limit exceeded on test 1, what does that mean? This was for problem A (round 36)
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    If you dont take the input from input.txt file (which is added just for today's contests)then it shows that error.
14 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится
 
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Прорешал задачи 35-го контеста, очень интересные, спасибо авторам!
Было очень забавно допустить одну и ту же ошибку в задачах 35D и 35E: использование set вместо multiset :)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Please tell me how to solve problem D of round 36(new game with chess piece).
14 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится
Где можно найти тесты???
У меня слетела задача, которую я написал за 30 мин, и часа мне не хватило, чтобы найти ошибку..
Очень хотелось бы узнать в чем дело..
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Round 35 Problem E I hate test 3
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
what is test 22 on prob E?  (round 35)