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

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

Всем привет!

Через несколько часов начнется Codeforces Round #159 для участников Div.2, но традиционно остальные могут поучаствовать вне конкурса. Он был подготовлен небольшой командой авторов: я (NALP), Иван Фефер (Fefer_Ivan), Павел Холкин (HolkinPV), Виталий Аксенов (Aksenov239) и Геральд Агапов (Gerald). Кроме того мы выражаем благодарность Марии Беловой (Delinur) и Михаилу Мирзаянову (MikeMirzayanov).

Традиционно всем удачи, полных решений и удачных взломов!

UPD: В раунде будет использована динамическая система оценки задач. Задачи отсортированы, по мнению авторов, по предполагаемому порядку увеличения сложности.

UPD: разбор на русском языке доступен тут.

UPD: контест закончен, поздравляем победителей!

1.GreatEagle

2.CarlyPlus

3.Dakurels

4.ytqiaqia

5.SuccessfulHackingAttempt

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

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

Thank You ! We Were Waiting for The First Contest in This Year ! :)

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

Correction Required :It is obvious, but traditionally it is Round #159.

In Indian culture, it is considered good to make minor mistakes when you do something good (like a small typo in the wedding card). So hope this NEW YEAR CONTEST is good for all.

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

I can't wait to do it >_< thank u very much

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

Nice, waiting for tutorial :)

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

wow it seems all the comments here get negative votes. so here i am! :d

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

happy new year and good luck :) :*

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

Динамика... Хорошо год начинается :) Мне лично понравилось! Желаю всем УДАЧИ и повышения рейтинга!

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

C-C-C-COMBO BREAKER!

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

Не успел! Жалко!

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

Вот вам и динамическая система оценка задач: Б-шка падает на один балл с А-шкой, хотя она на порядок сложнее.

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

    А по мне, так они обе одинаковой сложности. Разве что Б пишется в одну-две строчки, а А — в семь-восемь.

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

У меня одного в начале контеста упал КФ на пару минут?

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

У меня люди застряли в лифте, я не успел их вытащить...

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

    Не подскажете метод решения? На ум пришло только декартово дерево по неявному ключу.

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

      разбор уже опубликован, ссылка в посте :)

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

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

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

Problem A description was so hard to interpret. It took me more than 15 minutes to get what the problem was asking.

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

Как Д решать?)

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

    За 40 минут не застрессилось такое:
    Идём с конца и ставим + или ‒ так, чтобы сумма была как можно ближе к 0. В конце, если получили отрицательное — инвертируем знаки.
    UPD это заходит.

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

In problem A , I was really getting confused through a lot of words like supply line filters , devices , sockets , electric sockets. I was really changing the symbols through and forth.

I could not even understand the meaning of the problem :(. I need to improve my English.

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

Отличный контест, но сложность видимо вещь ооочень субъективная.

p.s. Как решалась C и что там может быть в 6 тесте ?

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

    Вы можете смотреть тесты. Для этого зайдите в раздел "Попытки" в вашем профиле и кликните на номер сабмита.

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

Секунд 15 до конца контеста -> Нашел потенциальную ошибку, исправляю пару символов, Ctrl+A, Ctrl+C -> Открываю окно "Отослать" -> Ctrl+V -> Выбирал задачу -> Бросив взгляд на таймер(оставалось приблизительно 8-10 секунд) понимаю, что успел... -> Нажимаю "Отправить" -- кнопка не кликабельна -> Завершается контест -- кнопка становится кликабельной. Конечно не факт, что исправленный код был правильным, но все равно такая вот беда...

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

how amazing testing system

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

About Problem C

Why atan2() have error, but acos() is ok?

PS: Oh,atan2() is ok. The error occur because cout and printf have some diff.

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

This is Contest or english lessons?,problem A is so hard who does not know english,Fuck english

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

    Let me rephrase your question: are the problem setters foreign language experts? English is the main scientific language, too bad.

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

    It's okay. On ICPC we were calling such problems English problems. Sometimes they were two A4 papers long. But we were able to dedicate time for that, concentrate, read and sometimes solve.

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

Hi,

I believe there is a problem with the solution judging system for Problem D: Sum.

My corrected submission after the round (now registered for practice) can be found at the following link: @ http://mirror.codeforces.com/contest/257/submission/2893122

For test 1, which is: 4 1 2 3 5

My solution output: +--+, which works, because this translates into 1-2-3+5 = 1, whereas my solution was judged WA, because the system was expecting "+++-" instead.

The problem statement clearly states "If there are multiple solutions, you are allowed to print any of them."

Could someone please verify this/provide me some clarification please?

Thanks, Lee Wei

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

    Hi, your solution outputs extra symbols (it seems with code 0) after the answer. So, problem's checker reads token <<+--+__>> (symbol _ for clarity only) and considers this token not a valid answer.

    I think everything is ok.

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

      Hi,

      I've done further tests to narrow down the issue. It seems that if i only print a single character up to n times, instead of traversing the whole vector (which I've initialised to be max size n), i break when a counter i inserted hits n, then the solution is ACC — see 2903009.

      is my STL container traversal macro correct? #define TR(c,itr) for (typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)

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

        Yes, it seems correct. Could you show a working and a failing solution that differ not so much, or elaborate on what is wrong?

        By the way, vector<char> b(n); creates a vector of actual size n, not of "max size n".

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

Can someone tell me why long double doesn't work, but same code with double gives AC? here are submits :

WA : http://mirror.codeforces.com/contest/257/submission/2893123

AC : http://mirror.codeforces.com/contest/257/submission/2893207 (in this code shorten "ld" is for double, not for long double...). When I execute same TP with long double on my computer, it outputs correct result for me. And if I use cout, it truncate the last 6 digits, so I get WA again.

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

    You must not print long double with printf("%lf", d); because %lf reads double but not long double.

    To print long double you should write like this: printf("%.10lf", (double)d);. Or you can use cout like this:

    cout.precision(10);
    cout << fixed;
    
    cout << d << endl;
    
    

    After cout.precision(10) and cout << fixed program will always output real numbers with exactly 10 digits after the .

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

      I know %lf is for double, but I have used in code %llf, and it worked fine on my computer. I have tried Custom test and I have found few things. $llf and %Lf doesn't work with gnu C++ 4.7 compiler, but If I switch compiler to Microsoft Visual C++ 2010, I get correct answer no matter do I use %llf or %Lf for long double. I have submitted WA code from previous post, with different compiler, and I got AC. :( so sad I didn't realized this before. Thanks anyway on answers. I hope this mistake will not recur.

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

        in Microsoft Visual C++ long double == double.
        sizeof(double) == sizeof(long double) == 8
        in GNU C++ long double != double.
        sizeof(double) == 8
        sizeof(long double) == 12
        That's why Visual C++'s printf works with "long double"

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

      http://mirror.codeforces.com/contest/257/submission/2890819

      check out this solution. I know the solution is incorrect, but the reason why I got WA is really surprising.

      I did exactly what all u told, I set the precision as 12 digits after the '.' Still answers didn't match.

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

Does anyone have any idea that how I can get TLE with GNU C++ 4.7 and AC with Microsoft Visual 2010 with the same code on both??!!!! I stuck on this problem for 90 mins in contest and I almost felt this contest. :(((

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

Does anyone have any idea that how I can get TLE with GNU C++ 4.7 and AC with Microsoft Visual 2010 with the same code on both??!!!! I'm stuck on this problem for 90 mins in contest and almost missed other problems. :(((

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

Div 2 — Problem A:

My solution is giving correct output for the testcase: 5 50 6 2 1 3 1 3

with output -1 on my computer and ideone:http://ideone.com/hM20Vq but giving a different answer on custom test here and hence judged wrong. Please do something about it.

  • »
    »
    12 лет назад, # ^ |
    Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится
    REP(i,0,k)
    

    If k > n, then this loop goes outside the array, so the variable sum is added an undefined value of a[n]. You can use customtest to debug directly on CF.

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

my solution is producing correct output for all the test cases,but my code is failed during the system testing on case 17,although it gives correct output -1. can anyone answer why this happened ? my solution can be viewed here

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

I wrote a solution about problem B long 3 lines in O(1) time. Looking among the submitted solution almost everyone has solved the problem in O(n) in more complicated way. I wanted to ask why, is there any case where my idea fails?

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

    Some of my friends solved it with 1 liner solution O(1) and their solutions passed the system test!

    I don't know how or why till now!

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

      The optimal strategy is the simplest one: as long as you have a choice, use the cube that gives you a point. I don't have a solid proof for this, but it's sort of the obvious way (especially given it's just problem B and those rarely involve more than brute force/greedy).

      How will the situation look, then? Suppose there are A cubes of the color which the first player chooses as the first cube, and B of the other, on the input. Then the adding of the cubes only gives 1 point to the player making the move, until there are no more cubes of the desired color; then, each turn only gives a point to pl. 1.

      From this, it's easy to see that the sooner there's only 1 color left, the more points pl. 1 gets, so A <= B. And it's just simple math from here on out.

      (This is just my opinion on the solution. I used the greedy approach, though, since I code faster than think so logically :D)

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

Okay, here is my comment on this contest.

This was the worst contest I ever played on codeforces! The problem statement of the first problem was the worst ever! More than 15 minutes of reading and I couldn't figure out what the problem is talking about!!

For the second problem, it was not clear as well! Many people submitted O(1) solutions which passed the system test for non obvious reasons (at least for me!)

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

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

    Contests aren't just about thinking/coding, but also about being able to efficiently understand the prob. description (and other stuff).

    For my opinion on the solution of prob. B, read above.

    I actually liked this contest, because there weren't crazy jumps in difficulty.

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

      But still the statement of task A was unecessarly overloaded of test.

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

edited ..

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

editorial in Russian published here @ http://mirror.codeforces.com/blog/entry/6357, use google translate pls, at least until a translation (will it come?) arrives.

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

What about the English editorial?

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

Is there a tutorial?

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

Still no tutorial?

BTW can you update the tag for problem 1 it can also be solved using binary search approach.

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

Can't find the editorial..