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

Автор RAD, 14 лет назад, По-русски
В России сегодня не просто 20-е сентября, а День Рекрутера. В Азербайджане – нефтяника, а в Беларуси – таможенника. Для нас же это плюс ко всему еще один хороший день, чтобы провести раунд. Добро пожаловать на Codeforces Beta Round #29 (Див. 2, Codeforces format)!

Готовить раунд помогали: Михаил МирзаяновДмитрий МатовГеральд Агапов и Николай Кузнецов, за что им спасибо.

Счастливого Дня рекрутера,
Артем Рахов

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

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Удачи всем!!!
Высокого рейтинга вам!!
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Желаю всем "зелёным" и "серым" стать "жёлтыми" или хотябы "синими" ("красными" не желаю - это практически не возможно). Ладно короче всем удачи
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
"В России сегодня не просто 20-е сентября, а День Рекрутера. В Азербайджане – нефтяника, а в Беларуси – таможенника."... а в Японии сегодня - День воздуха)) Прикольный праздник! 8)
Всем успехов на контесте!
  • 14 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится
    Российская Федерация, День работника кадровых служб.
    Республика Корея, День благодарения.
    Южная Осетия, День Независимости
    Япония, День воздуха.
    Азербайджан, День нефтяников.
    Белоруссия, День таможенника.
14 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится
Классный контест! Интересные задачи. Спасибо!
Тока не понятно как последняя таска решается((
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
what is test case 11 for problem B??
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Is the following a valid test for problem A?
3
2 6
5 3
8 -6
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
можно второй тест на E?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is test case 6 for problem D?? thx
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What's the 14th test of problem E........
I got wa on it
Guys who failed system on E were TLE in majority。。。

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Ребята, объясните, что за ошибки представления данных. Уже не в первый раз, напрягает. До сих пор не понимаю из-за чего. На второй задаче тест 1.

using System;

namespace CodeForcesApp
{
    class B
    {
        static void Main(string[] args)
        {
            string[] s = Console.ReadLine().Split(' ');
            int l = int.Parse(s[0]);
            int d = int.Parse(s[1]);
            int v = int.Parse(s[2]);
            int g = int.Parse(s[3]);
            int r = int.Parse(s[4]);

            double time = 1.0 * l / v;
            double t = 1.0 * d / v;

            int c = g + r;

            while (t > c)
                t -= c;
            if (t >= g)
                time += c - t;

            Console.WriteLine(time);
        }

    }
}

Форматирование  Console.WriteLine("{0:f8}", time);  не помогает.

  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Аналогично было у меня. В итоге сдал, переписав на С++.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is a test case #14 for problem C? Judge reported "Runtime error", but I don't see why.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Oh, don't worry.
    Now I see, that I just used too little constant in array declaration. What a silly fail. :-)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is B-pretest1 and answer?
PE when I use C#
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
по задаче E:
- на мой взгляд TL оказался жестковат. я только что написал еще одно решение на Яве и оно прошло за 950ms (116688). на C++ похожие решения отрабатывают за 150ms (115992, 116490, 115816)

по задаче D:
- я конечно сам балбес, не добавил в решение if (!good) return;

порешал блин второй дивизион ))) хотя у меня есть определенная отговорка :P
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    У меня решение с неправильной асимптотикой, которое двигало обоих людей сразу, но читерски прекращало работу, когда находило ответ, работало 1300 мс, а решение за O(nm) на C++ - 100 мс. И я решил что запас в 10 раз по сравнению с ТЛ - нормально. На больших ограничениях разделить эти решения еще сложнее.
    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      не знаю какое сейчас распределение по языкам, но референс решения на Яве и C++ всегда полезно иметь. это в идеале конечно.

      я тоже на контесте написал решение которое двигало двоих сразу, у меня укладывалось в 1200ms (macbook pro, 2.4 ghz, 64-bit jvm). но я не заметил что TL всего лишь секунда. имхо можно было не разделять , а просто дать людям сдать задачу ) тем более самбитов по ней и так было очень и очень мало
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
what's test case 3 for problem c?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What is pretest 4 for problem C? I don't know why I get a representation error.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    4
    90104473 221011623
    18773664 221011623
    90104473 74427905
    74427905 186329050

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
кто нить знает конр пример для задачи В а то ВА на 11 тесте
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
пожалуйста, дайте 5 претест на C
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    5
    695442143 421284135
    641835294 542627184
    852367357 120042890
    641835294 852367357
    542627184 421284135

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
what's the solution for the last problem?

it's obvious that if the shortest path in the graph has even numbers of nodes, than that's a solution.. but what to  do if that is not the case?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I managed to get AC in practice using Dijkstra's algorithm.

    You can represent each state as (x1, y1), where x1 and y1 are the location of the two guys. Then you can transition from (x1, y1) to (x2, y2) at a cost of 1 if there exists edges (x1, x2) and (y1, y2). Ensure that x2 != y2. Thus, you begin with (1, n), and terminate at (n, 1). Since each transition is equally weighted, a normal queue is sufficient.

    My solution was fairly sketchy since I got TLE using some C++ STL, but it passed with time 800ms when I manually implemented them. I'm wondering if there are more efficient solutions.
    • 14 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится
      Yes, there are. Since the edges have weight 1 (actually, equal weight in general) you don't need to use Dijkstra (and use BFS instead). The state in the bfs is the current nodes of the two persons and who moved last (in order to make the solution linear in the number of edges we need to realize there is no need to move them both at the same time). So we end up with a state[500][500][2], i.e. [node1][node2][who], where node1 is the current node of person 1, node2 is the current node of person 2, and who is 0 or 1 depending on who moved last. We run a standard BFS which should not allow the node1 == node2 when who == 0 (i.e. after the move of the second one). Ending state is when node1 == n, node2 == 1, who == 0. You can figure out details further yourselves :)
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        nice and easy solution. Thank you.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        That's a much better representation of states. I've updated my solution and now it passes with time 110ms.

        Sorry about the confusion; I meant BFS instead of Dijkstra. Basically a Dijkstra without checking to see if the new distance is lower.
        • 14 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится
          As we all know,BFS travel every state in ONE step, so when reach the goal state, the step is  minimum.
      • 14 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится
        nice and easy solution. Thank you.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
У кого проблемы с PE на C#:

Вся засада в культуре, ну или как сказал RAD, вместо точки выводится запятая. Походу все же такие вещи надо на сервере правильно настроить. Написал по этому поводу Майку.

Выводить можно так: Console.WriteLine(dbl.ToString(CultureInfo.InvariantCulture)). После изменений все прошло. Но обидно, уже 3 контеста с такой фигней сталкивался, и только сейчас дошли руки поэкспериментировать, в чем дело.

Понятно, что теперь не стоит забывать о всем, что связано с культурой: парсинг чисел, дат, вывод оных и т.п.
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Давно тоже сталкивался с этой проблемой на контесте, решилось добавлением строки:
     System.Threading.Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
    в Main()

    вот мой шаблон: http://paste.ubuntu.com/497437/

    По этому поводу кстати можно и Тимус почитать:

    Не забывайте, что культура по умолчанию может любой. Это важно, если вам требуется считать или вывести число с плавающей точкой: разделитель целой и дробной части может быть задан в системе как «.» или как «,». В настоящий момент на сервере настроен разделитель «.», однако это может измениться в будущем. Чтобы не сталкиваться с подобными проблемами, указывайте культуру явно при каждой операции ввода/вывода или установите культуру по умолчанию для всей своей программы:

    Thread.CurrentThread.CurrentCulture = CultureInfo.InvariantCulture;
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What's the 12th test of problem B ?
I got WA on it .
Thanks !
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    2 1 1 1 1000

    • 14 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится
      а какойо ответ должен быть? У меня выводит 2.00000
      • 14 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится
        On the 12th test case I got 1002.
        ( I cannot understand russian but I assumed you might have asked what's the correct answer for the 12th test case . If I was wrong, I'm sorry .

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

What's test 19 in problem B?

14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Будет ли разбор задач?)если нет, сделайте кто нибудь пожалуйста)
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
What's test 5 in problem C?
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
да в задаче В вообще прикольно получилось из-за одного лишнего знака = прога непрошла все тесты
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
In Problem B :

In this case 5 4 3 1 1. Why the answer is 2.33333333
I think it should be 2.66666667.


  • 14 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    He first moves 3 units ( with t1 = d1 / v = 1 second ). The traffic light changes color.
    He now waits t2 = 0.66667 seconds from the semaphor's red light.
    After t2, he instantly accelerates to v = 3 m/s speed, catches the changing color right when passing through the traffic light and makes t3 = d2 / v = 2/3 = 0.66667 seconds until reaching the destination.

    Total time spent: T = t1 + t2 + t3 = 1 + 0.6667 + 0.667 = 2.333
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
I keep getting WA on Test 2 in Problem D  on the judge. Is not test case 2 the second sample test case specified in the problem ?  I get correct answers on the samples.  Can anyone tell me what Test case 2 is ?
  • 14 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    I got AC. Had not written a return statement and the behavior of function was undefined.
14 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
There's some place where I can get the inputs and outputs of the problems?

I'm getting WA at Test 13 in problem D, and couldn't figure out where my solution fail.