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

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

Всем привет!

Скоро (1 октября, 19:30 MSK) состоится очередной Codeforces Round #203 для участников Div. 2. Как обычно, Div. 1 участники смогут поучаствовать в этом раунде вне конкурса.

Автором раунда являюсь я. Хочется сказать большое спасибо Гере Агапову (Gerald) за помощь в подготовке и за хорошие предложения по задачам. Спасибо Лось Илье (IlyaLos) за тестирование задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon. Также спасибо Игнатьеву Александру (aiMR) за тестирование задач и идею одной из них.

Удачи!

UPD: Будет использоваться динамическое распределение баллов. Задачи расположены в порядке увеличения сложности (по мнению авторов).

UPD: Поздравляем победителей!

  1. fanhqme
  2. FAU.COACH
  3. Witalia
  4. sokian

UPD: Разбор

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

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

Ставлю, что либо D, либо Е будет на ДП.

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

    Ладно) Как оппозиция, поставлю на геометрию в 3-4 задаче и на то что 100 место наберет 2000 баллов, имею ввиду див2 учасников.

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

      Основываясь на предыдущих контестах автора, можно предположить, что B будет математикой, которая даже немного сложнее, чем C.

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

      Не думаю, что задачи будут простые для div2 (ведь автор из Саратовского ГУ), и, хотелось бы, чтобы была динамическая система оценивания, но, скорее всего, опять стандартная разбалловка...

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

        "ведь автор из Саратовского ГУ". Это новый своеобразный показатель сложности ?

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

          Авторы из СГУ действительно очень часто переоценивают возможности Div-2 участников

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

            Не, ну этот контест был очень даже неплох)

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

        Давно заметил, что вы большой поклонник динамической системы =)

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

      У меня 103 место и 2090 баллов :D Скажешь как рейтинг изменится? :D

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

    С 200-го места до последнего будут участники решившие не более 2-ух задач. Не учитывая Div1 участников, разумеется.

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

    Это плохо или хорошо?

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

    Ставлю, что я на этом контесте не упаду в рейтинге.

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

      странно было бы если б ты упал в этом контесте...

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

    Твои комментарии в каждом посте.

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

Happy National Day for all Chinese participants!

Wish everyone a high score!

PS: It would be better for us Chinese participants if only start time of each round could be made a little bit earlier...

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

Сколько желающих поиграть интуицией !..

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

GL&HF!

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

I hope this contest don't like last.

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

    whats wrong with the last one? (:

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

      You can surely see my username written in green colour ,can't you !! This is what happened in the last contest :(

      So, fingers crossed this time :) (y)

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

Why is it that registration closes before contest ?? and we can't enter after the contest hast started?

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

    Valid point. But I assume one reason may be challenge phase. If there is no registration there might not be fair and optimal way of room assignment as every body will simply log on at the time of the competition.

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

R.I.P clarity..

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

I submitted problem C in Java to get TLE on test case 5. Rewrote the same algorithm in C# and it passed test case 5. That's really not fair. >.<

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

The problems translations to English needed more work. Also problems A, B & C didn't have any explanation for their sample tests.

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

    Couldn't agree more. I took much time reading description of Problem B and hardly got how sample tests works because of no explanation, but easily understand Problem C by a quick glance.

    I think Problem C should be set before Problem B.

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

i can't understand problem B :(

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

    i have same problem. but i sent a clarify question and understood it. when you cant understand a problem you should send a clarify question. they often send you a compelete answer! sorry for my poor english.

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

    Same here. It was very difficult understanding the problem B. But looking into the submissions in the room, I was skeptical of making my comment. I think we as a community will benefit if the problems are better written.

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

    The same to you!!!

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

    it's the only problems that I solved :lol:

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

The title of the competition is too difficult to read!!!

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

Could not submit E on last minute as server was down :-( 5 additional minutes should be granted IMHO

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

Сдал за 6 сек до конца, не повторяйте моих ошибок !!! Если бы не этот чек в if-e (k == n) которым я дебагал и забыл удалить, кто знает как бы для меня закончился контест... http://codeforces.com/contest/350/submission/4631678

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

From where I can get tutorials for the contest??

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

I think some phrase and grammer is difficult to realize for people have poor english like me.

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

8 successful hacks for problem A with this test case 2 1 3 5 10

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

From where I can get the tutorials for the contest?

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

I failed to submit my solution for problem C the last second before the end because I can't enter the site.what a pity!

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

    I was in exactly same situation...

    15 sec remaining, I submitted problem D but.. the submission was denied..and the contest ends.. :(

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

problems did not interesting,did not short,did not have sample test explanation,statement was not perfect.

I don't like this contest :) may be becose I wrote badly ;)

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

duh! And C went to 1000..

Scoring should be gradual not sudden like 500-1000-1500 ...

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

When will ratings be updated???

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

Хороший тур. Хотя немножко тупанул). Авторам спасибо.

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

QuickSort с взятием для сравнения средним элементом переписываем под quicksort со взятием для сравнения рандомным элементом и задача C не падает с TL и заходит... в дорешке... обидно...

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

Поучаствовал первый раз, здорово! Понравилось :)

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

For Problem C :

My java code gets TLE at test 5 .

This is the Code : http://codeforces.com/contest/350/submission/4630115

After The contest I changed it to C++ And the same code passes :

This is my C++ code : http://codeforces.com/contest/350/submission/4632017

Kinda disappointing :/

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

    I think it's because of big amount of System.out.println()

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

      Maybe I shall use String Builder and append stuff together , but I couldn't get that this is the reason of my TLE. :/

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

        You could try using PrintWriter

        PrintWriter out = new PrintWriter( System.out ); // all your prints out.flush() // send your prints to the output

        It is faster.

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

    Sorry, there is.

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

      How do you solve it without sorting?

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

        I'm getting the closest points to my starting point to avoid facing a bomb in my way to a far bomb and it goes like that till the end so the condition is satisfied.

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

          Ok, and how do you take the closest point to the origin?

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

            By getting the minimum sum of (x + y) for the bombs points

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

              And isn't it faster to sort the bombs by x+y and then iterate through them? Since it is still not enough to get AC using Java, I don't think that choosing the min(x+y) with O(n) for every bomb works in 2 sec in any language.

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

                Sry I misunderstood you , I was explaining how im sorting them but without sorting Idk how to do it

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

From problem E:"non-directed connected graph from n vertexes and m edges, containing no loops and multiple edges"

Doesn't this mean that the graph is a tree?

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

    No, loops != circles. No loops simply means that there is no edge from one node to itself.

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

    loop != cycle. loop is an edge from a node to itself

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

translate of B , got half of my time :(

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

Поделюсь своим решением по Е, оно довольно простое, и я сам во время контеста думал, ну когда ж уже witua его взломает :) Тем не менее, зашло. В общем, идея такая: в алгоритме Флойда внешний из трех циклов отвечает за вершину, которая стоит внутри пути, то есть не начальная и не конечная. Так как Валера из условия осознанно не стал использовать некоторые вершины в качестве этих внутренних (они у него не помечены), то на этом его и словим.

  1. Нам дано, как минимум, две помеченные вершины и одна непомеченная (случай, когда все помечены, вынесем отдельно, ведь тогда понятно, алгоритм Флойда реализован правильно и граф-контрпример не построить). Обозначим эти помеченные через p1 и p2, а непомеченную — через np. Проведем ребра (p1;np) и (p2;np). Вот, собственно, заготовку построили, ведь прога Валеры не найдет кратчайшего пути из p1 в p2 через np. Осталось только добавить недостающие ребра так, чтобы эту заготовку не сломать.

  2. Обеспечим связность нашего контрпримера. Все вершины, кроме p1, p2 и np, соединим с p1. Итого пока что у нас получается 2 + (n-3) = n-1 ребер. Это тот минимум, который могут от нас требовать.

  3. Дальше выберем из наших вершин все, кроме p1 и p2 (np тоже можно). Все эти вершины можно посоединять попарно, не сбив заготовку 1 пункта, ведь из p1 в p2 все равно можно будет попасть только пройдя через np, которую Валера наотрез отказался пометить.

  4. Если ребер все еще недостает, можно соединить все непомеченные вершины с p2, ведь пути из p1 в p2 через них, длина которых будет равна двум, как и в 1 пункте, Валера тоже не рассмотрит.

  5. Если все равно ребер недостает, граф построить нельзя. В противном случае мы получили пару вершин p1 и p2, кратчайший путь через которые программа Валеры определит неправильно.

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

    Писал так же. Насколько я понимаю, это правильное решение :)

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

      Просто немного удивлен, почему меньше сотни человек решили ее во время контеста.

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

        Потому что это Е. Психологически люди думают, что она должна быть сложной.

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

In problem C, can anybody explain to me why this get AC,

// std::sort(..., ..., cmp) ;
bool cmp(dot d1, dot d2){
	return abs(d1.x)+abs(d1.y) < abs(d2.x)+abs(d2.y) ;
}

while this was not?

bool cmp(dot d1, dot d2){
	if(d1.x == d2.x)	return abs(d1.y) < abs(d2.y) ;
	return abs(d1.x) < abs(d2.x) ; // move x first, y second.
}

Thank you for your reading.

edit: Thanks for reply. I found a test case that make sort() result not correct.

a = (1, 3), b = (-1. -2), c = (1, 2) in my code (1, 3)==(-1,-2), (1, 3) > (1, 2), (-1, -2)==(1, 2) b = a, a > c, b = c → b=a>c=b, so a&c may not sort correctly.

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

topped my room for the first time and advanced to Div-1 even though i failed A! :)

P.S. very weak pretests for A!!

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

    Why does my code for Problem B give MLE? I have no idea.

    http://codeforces.com/contest/350/submission/4633434

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

      Looks like recursion depth. May be could not allocate enough stack.

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

        I don't think that is the reason because I do not see any unnecessary recursive calls. It's similar to how others have done it.

        Edit : On taking a closer look, I realized that my code is not using a vis[] array hence, there is a possibility of it getting trapped in a cycle which causes stack overflow. You are right. Thanks :)

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

Failed to get Problem C because I used formula to find gradient instead of the distance formula. All this because I had little time left and rushed everything. Just saw that and corrected the formula to get AC. Absolutely deflated :(

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

Hi, I tried debugging my codes but could not find anything wrong. Please help me to find what is wrong with my solutions.

350C - Bombs — solution id 4631490
350B - Resort — solution id 4628087

The test cases are only partially shown so they were of little use.

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

I think the second test case for problem B is wrong as i got 1-2-4-5 and k=4; while the testcase says 4-5 k=2.Please can someone clarify please.

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

    Got it condition 2 of problem each object must have at most one connection to another object. I'm thinking in line of LIS is my intuition correct?

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

      notice that path 2-4 is invalid as 2-3 also exists. a path is valid if the starting vertex leads to one other vertex only.

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

thx this contest..I get 246 points.

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

Problem A, my program got WA on test #24 (expected 4, but got -1). I ran my code on my machine, however, the output was actually 4. I don't know why it got -1 on codeforces (even after I resubmit the code, it was still WA). Here is my contset submission 4621813

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

Enjoyed the contest very much.Hacked 8 solutions successfully with the test case 3 1 3 4 5 8

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

In my opinion, I prefer concice problem description, long description always take nonnative more time to understand, I think the algorithm matches should reduce the differences between native & nonnative.

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

Problem C's TL should be increased. this tight TL is not fair

Here is my code which at first stocked at test 5 after adding "ios::sync_with_stdio(false)" it passed and again stocked at test 6

here is my submission http://codeforces.com/contest/350/submission/7048251

just look at the times in AC codes here : http://codeforces.com/contest/350/status/C