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

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

404A - Валера и X

В данной задаче нужно было проверить, выполняются ли ограничения, описанные в условии. Чтобы это сделать, можно было завести два множества. В одно множество сложить диагональные элементы матрицы, в другое — остальные. Элемент ai, j стоит на главной диагонали, если i = j, и стоит на побочной, если i = n - j + 1. После того, как мы сложили все элементы в множества, нужно проверить, что размеры обоих множеств равны единице, и элементы этих множеств различны.

404B - Марафон

В этой задаче нужно было заметить, что пройдя расстояние a, Валера окажется в той же точке, откуда стартовал. В момент, когда Валера получит i-ое питание, он пробежит расстояние i·d. Давайте посчитаем величину — сколько полных кругов пробежит Валера по стадиону. Тогда на своем последнем кругу Валера уже пробежал L = i·d - c·4·a метров. В зависимости от этого L можно легко определить позицию Валеры. Например, если a ≤ L ≤ 3·a, то Валера будет находиться в точке с координатами (3·a - L, a). Аналогичным образом разбираются остальные 3 случая.

404C - Восстановите граф

Заметим, прежде всего, что в массиве d должен быть один и только один 0. При этом d[start] = 0 обозначает, что start именно та вершина, от которой Валера считал расстояние до всех остальных. Заметим, что любая вершина u, для которой d[u] = i должна быть соединена ребрами только с вершинами v, у которых d[v] ≥ i - 1. При этом хотя бы для одной вершины v0 из соседей u должно выполняться d[v0] = i - 1. Будем строить искомый граф добавляя по одной вершине в порядке увеличения их расстояния до start. Изначально в нашем графе будет одна вершина с номером start. При добавлении вершины u с d[u] = i рассмотрим все вершины v, у которых d[v] = i - 1. Выберем среди таких вершин вершину минимальной степени. Если эта степень равна k, то ответа не существует. Иначе добавим в граф вершину u и ребро (u, v). Если вершин с расстоянием до start равным i - 1 нет, то ответ также  - 1. В противном случае после добавления всех вершин, мы получим граф, удовлетворяющий условиям задачи, который при этом будет деревом, а значит количество ребер в нем n - 1 ≤ 106.

404D - Сапер 1D

Задача решается методом динамического программирования. Будем считать d[i][type] — количество корректных способов заполнить префикс полоски длиной i так, что последняя заполненная клетка имеет один из пяти типов. Типы последних клеток будут следующие:

  1. в клетке записано "0"

  2. в клетке записано "1" и слева от нее стоит бомба

  3. в клетке записано "1" и слева от нее нет бомбы

  4. в клетке записано "2"

  5. в клетке находится бомба

Когда мы хотим заполнить очередную клетку, мы перебираем, что туда запишем, и проверяем два условия. Во-первых в заданной строке значение заполняемой клетки должно либо совпадать с тем, что мы хотим записать, либо быть равно "?". Во-вторых новый префикс должен оставаться корректно заполненным. Это значит, например, что если мы находимся в состоянии (i, 1) (то есть в последней заполненной клетке записан "0"), то в следующую клетку мы можем либо записать "0" и перейти в состояние (i + 1, 1), либо записать "1" и перейти в состояние (i + 1, 3). Записать "2" мы не можем, так как у клетки с "2" оба соседа должны быть заполнены бомбами. Поставить бомбу после "0" мы не можем по очевидным причинам. Обратите внимание, что записав "1" после "0" мы переходим именно в состояние (i + 1, 3), а в состояние (i + 1, 2) мы можем перейти лишь записав "1" после бомбы. Аналогичным образом разбираются остальные переходы динамики.

404E - Лабиринт 1D

Рассмотрим случай, когда последовательность ходов робота заканчивается буквой "R". Если она заканчивается на "L", то можно заменить в исходной строке все "L" на "R" и все "R" на "L" и ответ от этого не изменится. Покажем, что количество препятствий, которое потребуется Валере, не превосходит 1. Предположим Валера поставил препятствия в какие-то клетки. Будем говорить, что номер препятствия — это номер клетки в которой оно стоит. Рассмотрим среди всех препятствий с отрицательными номерами самое правое (обозначим его obs1), а среди препятствий с положительными — самое левое (обозначим его obs2). Очевидно, что робот не сможет оказаться левее препятствия obs1 и правее obs2. Поэтому требуемое количество препятствий не превосходит двух. Покажем, что Валере не нужно ставить препятствия в клетки с номерами больше нуля. Предположим он поставит препятствие в клетку с номером a > 0. Если робот ни разу не попытается сходить в эту клетку, то, очевидно, препятствие лишнее. Если в какой-то момент робот пытается пойти в клетку a, то в последующем он посетит финишную клетку более одного раза. Это так, потому что на последнем ходу роботу нужно пойти направо, но из клетки a - 1 направо пойти нельзя, а все клетки, которые левее уже были посещены. Таким образом мы получаем, что Валере потребуется не более одного препятствия, которое должно иметь номер меньше нуля.

Давайте теперь проверим, может ли Валера обойтись вообще без препятствий. Если может, то робот не пропустит ни одного хода и успешно закончит выполнение инструкции в какой-то клетке. Тогда Валера может выбрать только эту клетку в качестве финишной и ответ на задачу в этом случае равен единице. Остается случай, когда Валера должен поставить одно препятствие.

Заметим, во-первых, что по тому, где Валера поставил препятствие, однозначно восстанавливается финишная клетка. Это значит, что количество способов выбрать препятствия и финишную клетку, равно количеству клеток, в которые нужно поставить одно препятствие. Предположим Валера поставил препятствие в клетку с номером b < 0 и робот успешно закончил инструкцию. Заметим, что в этом случае робот пропустит какие-то ходы типа "L", выполнит все ходы типа "R" и последним своим ходом пойдет направо в какую-то не посещенную клетку. Если теперь мы подвинем наше препятствие на одну клетку вправо, то от этого робот может лишь пропустить больше ходов типа "L". Это значит, что финишная клетка может лишь подвинуться вправо. Но так как в прошлый раз мы ее посетили последней, то и новую финишную клетку мы посетим последней. Это в свою очередь значит, что существует какая-то клетка p < 0 такая, что если мы поместим препятствие во все клетки c ≥ p, то робот сможет успешно выполнить инструкцию, а если поместим препятствие в клетку d < p, то не сможет. Эту клетку p можно найти при помощи бинарного поиска и простого моделирования за O(n) на каждой его итерации. Таким образом получаем решение за O(n log n).

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

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +27 Проголосовать: не нравится

probably for the first time in my life, i have used the function fmod of C++ (to solve problem B).
i always used to think this was a useless function! :D

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

Hi,

I've got a question about Problem E. I think the solution doesn't always exist, but the problem description doesn't mention this and neither does the editorial.

Let RLR be an example. If we don't place any obstacles, we end at position 1, which has been visited before. We can't place an obstacle on position 0, so the only other option is to place the obstacle at position 1. In that case, we end at position 0, which is also an invalid result. What's the correct answer for these cases?

»
11 лет назад, # |
Rev. 4   Проголосовать: нравится +6 Проголосовать: не нравится

Кто-нибудь может объяснить, почему

D:=D — 4*a*trunc(D / (4*a) ); — это правильно, а

While D >= a*4 do D := D — a*4; — это неправильно ?

WA17
AC

UPD. problem B

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Странные проблемы с точностью. Если заменить real на extended, то все работает

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

For problem E I have an O(n) algorithm: http://codeforces.me/contest/404/submission/6085167. We should set 0 or 1 obstacle only. If we don't set any obstacle, and the robot make a valid way, just print 1. Else, all I need to find is the last position of the robot and the minimum position of the robot if I set an obstacle on position x(x>0).

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

For the problem E I have an O(n) algorithm: http://codeforces.me/contest/404/submission/6085167. I only set 0 or 1 obstacle on the line. If I don't set any obstacle, and the robot makes a valid way, just print 1. Else, all I need are the minimum position of the robot for all process and the last position if I set an obstacle on position "pos" (pos>0).

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

I don't have time to solve problem D

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

I'm getting a wrong answer bcz of 0.00014 relative error in prob B Marathon of DIV -2.I'm unable to think of what exactly needs to be done to get an AC.Here is my code:-

import java.util.*;

public class Main {

public static void main (String [] args){

     Scanner in = new Scanner(System.in);

         double a = in.nextDouble();
         double x = in.nextDouble();
         double n = in.nextDouble();

            double d=x;
         for(int i=0;i<n;i++){



            if(d%(4*a)>0 && d%(4*a)<=a)
                System.out.println((d%(4*a)) + " " + "0");

                else if(d%(4*a)>a && d%(4*a)<=2*a)
                   System.out.println(a + " " + (d%(4*a)-a));

                else if(d%(4*a)>2*a && d%(4*a)<=3*a)
                   System.out.println((3*a-(d%(4*a))) + " " + a);

                else if(d%(4*a)>3*a && d%(4*a)<=4*a)
                   System.out.println("0" + " " + (4*a-d%(4*a)));

                   d+=x;


         }
         }

}
»
11 лет назад, # |
Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

In problem C, Why last test case i.e.
5 4
0 1 1 1 4
returns '-1' ?

can this be the answer :
4
1 2
1 3
1 4
2 5

  • »
    »
    11 лет назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    your answer is valid if input 5 4 0 1 1 1 2

    well, there is no vertex can be in distance 4 if there is no vertex in distance 2 and 3. so there are no answer

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

      That means all the edges are of 1 unit length. Am i right? if yes, then it is not mentioned in question.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

        exactly. its been clarified during the contest

        Problem C. Restore Graph ***** The distance between two vertices is the minimal number of edges in the path between themc

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

Can anyone explain me Minesweeper 1D in detail. I'm unable to find out the recurrence ? If you have code for this question then please add comments in Code so that I'm able understand the logic as well as Code . Thank You !!!

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

It is really easy!!!

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

For Problem C — Restore Graphs. What is test case number 35 ?

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

    My submission was also getting Wrong answer on that test case... The problem with my code was "int overflow" when I was multiplying v[i-1].size() * (k-1) for checking for the -1 case.

»
4 года назад, # |
Rev. 6   Проголосовать: нравится 0 Проголосовать: не нравится

If you have a doubt regarding the test case of Problem C, then check this link.