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

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

Доброго времени суток, сообщество Codeforces!

Рад Вам сообщить, что мы в очередной раз делаем раунд из задач одной из олимпиад для саратовских школьников. На этот раз — раунд для второго дивизиона. Раунд начнется в необычное для Codeforces время: 11 ноября в 12:00 MSK

Задачи были подготовлены MikeMirzayanov и мной, в написании альтернативных решений нам помогали Fefer_Ivan и Gerald.

Участники из первого дивизиона, как обычно, могут поучаствовать вне конкурса.

Разбалловка стандартная: 500-1000-1500-2000-2500.

UPD: Опубликован разбор на английском.

UPD 2: В задаче E изначальное авторское решение (оно, к сожалению, было одно) было неправильным. Однако, ответы ко всем претестам были корректные. После контеста авторское решение было исправлено, все решения по задаче E были перетестированы.

UPD 3: Появились окончательные результаты, рейтинг обновлен.

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

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

Why the contest is only for div 2?

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

It is a contest for singles~~~~november 11th~round 211...Monday...So many "one"!

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

What's the meaning of schoolchildren? Which ages does it contain?

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

Задача "B" оказалась намного легче "A"

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

    "А" тоже элементарная. Простой способ: расписать if-ы для каждой цифры.

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

Ребят, может кто подскажет насчет задачи "C", там в условии стоит ограничение на длину строки в 2 * 10^5

А у меня мысль для решении такая: пробежаться по строке и проверять на наличие ошибок.

Но если длина строки окажется даже 10^5, то вряд ли я смогу уложиться в 1сек.

Как вы ее решили?

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

    Разве это корректно — обсуждать еще не закончившийся контест?

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

E was a nice problem.

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

Как D решать?

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

    Решение за O(NlogN). Делаем бинпоиск по количеству взятых велосипедов. Пусть сейчас мы хотим проверить, можно ли взять X велосипедов.

    Считаем Cost — количество денег, необходимое для покупки X самых дешёвых велосипедов. Потом берём X самых богатых детей, считаем, сколько их наличных денег мы можем максимально истратить, пусть это количество равно Cash. Проверяем, что Cash + Budget ≥ Cost, тогда для того, чтобы набрать X велосипедов нам нужно max(0, Cost - Budget) личных денег.

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

Happiness is

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

Может я что-то не понимаю, но как линейное решение могло заТЛится на 8-ом тесте, который (ИМХО = 8 претест, или я не прав?) прошел во-время соревнования?

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится
    t = t + s[i - 1] + s[i - 1];
    

    Вот эта строчка работает за длину строки.

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

      Ну афигеть, а как тогда эффективно дописать к строчке символ?
      И все же разве 8 тест != 8 претест?

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

      И у тебя решение громоздкое. Взгляни на мое. Если строка-результат пустая, то кладу в нее символ, если в строке больше одного символа и текущий символ равен последним двум символам в строке, то я текущий символ не добавляю в строку-результат. Так же, если в строке больше двух символов и два предпоследних равны, и последний с текущим равны, то тоже не кладу символ в строку результат. Как-то так.

      http://codeforces.net/contest/363/submission/5066025

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

    Но 8 претест == 8 тест, как так?

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

Can someone give the approach to solve problem D : Rent Bike ? Thanks in advance...

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится
    • first make n equals to m : if (n>m) take only the richest m boys, if (n<m) take only the cheapest n prices.
    • use binary search to search r , store the total amount spent by boys s everytime you check the condition in binary search. The answer for s is the last true condition in binary search check (that is, the largest possible r we found).
    • To check the condition in binary search, check it greedily : let's say you want to check for the answer X, then choose X richest boys and X cheapest bikes. Pair them respectively and see if it's possible for those X boys to buy those X bikes.

    Sorry for my English :)

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

Ohh , why did I sleep through this contest :( . It looks like I missed a cool codeforces round :) .

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

can someone explain me the reason why this solution did not passed?

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

Problems were very interesting. Thanks to Authors...!!!

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

Во время контеста пытался взломать по задаче B тестом :

100000 100000

100 100 100 100...

но каждый раз выходило FAIL Unexpected character #13, but ' ' expected (stdin) [validator v.exe returns exit code 3] или FAIL Expected EOLN (stdin) [validator v.exe returns exit code 3], почему?

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

    Same thing happened to me! My Submission fails on test 15:

    Input
    zz
    Output
    zz
    Answer
    zz
    Checker comment
    wrong answer Result is not a subsequence: 'zz' not in 'zz'

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

    it maybe due to this piece of code

    ans += s[0];
    ans += s[1];
    

    u are adding 2 characters to ans, when there is only one character in input.

    EDIT: but what i dont know is why this resulted in Wrong Answer rather than Runtime Error. also, i agree with you that the Checker Log is contradicting itself!

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

      Yes. Thanks. It should add an extra '\0' to the output string. Removing it, it gets AC. But, I wonder why would an extra null cause checker program to fail.

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

        printf("%c",'\0') or cout<<'\0' will print a space.

        string str(10,'\0');

        cout<<str; will print 10 spaces while printf will stop at the first '\0'.

        -- MS C++!

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

Кто как решал задачу D? У меня бинпоиск по количеству взятых велосипедов. Может ли там зайти какая-нибудь жадность?

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

    Тоже интересно. Я пытался двумя указателями, но ошибку в коде не нашел.

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

.

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

In problem B , I solved in notebook using val += h[i] — h[g]; and unknowingly missed the + sign during coding 5061002 ,as the pretest passed i did not go through the code once :(

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

I got WA in Problem C (test 15) while my program gives the correct answer!

Here's my Submission

Can anyone tell me why this happened?

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

    This part is causing the problem : ~~~~~ if(s[0] == s[1] && s[1] == s[2]){ index = 2; }else{ s1[2] = s[2]; index = 3; }

    ~~~~~

    For the given case "zz", s[2] does not exist, thereby the control goes to the else condition and index is set to 3. So you are actually printing extra space along with your answer, which is invalid.

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

      in this case...s[2]='\0',it can't be printed...and the '\0'(0) is not the ' '(32)....in ascii...

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

    yes, my bad ... :( it is '\0' and shouldn't be printed. So the reason which I gave you, regarding your control going to the else condition is correct, whereas you are printing '\0'. Thanks for correcting me mathlover :)

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

Только я мог за "С" получить баллов меньше, чем за "А" :)

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

Problem E is very nice, but nobody got E accepted during the contest... When will the solution be published?

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

Как решать E?

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

How is the standings is computed? Through the submission is accepted, but the standings is so low:(. Can someone explain for me, 3kq.

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

Can anyone tell.why my this solution failed? 5062164

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

    Ok.Null charachter was the issue. But i want to know.Why did WA came on 52nd test case when i did not put null charachter in the Output string and printed using %s.

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

Test: #6, time: 0 ms., memory: 792 KB, exit code: 0, checker exit code: 1, verdict: WRONG_ANSWER Input aaa Output aa Answer aa Checker Log wrong answer Result is not a subsequence: 'aa' not in 'aaa'

why aa is not in aaa?? http://codeforces.net/contest/363/submission/5062051

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

This contest was much easier with comparison to the previous ones...

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

Please !!! Update the rating !!! :( Eagerly waiting for that .....

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

How to get the test datas?

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

while trying to submit solutions in practice for today's contest, i got a message saying "Practice is allowed only for finished and unfrozen contests".

can anybody help me with this? thanks.

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

Interesting. Why am I the Candidate Master with rating 1699?

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

    I'm Master with rating 1408 :) I think they rollback rating because of some problems related to problem "E"

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

    It seems the rating change for this match has been reverted due to an issue of problem E,but they forgot to update the handle colour.....

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

Рейтинг пересчитывать что ли будут?

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

Can you provide an official information of whether the contest will be rated or less?

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

When will we have the Final standings?

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

The editorial for problem E seems like brute force...What a strong test server...

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

This was my 100th rated contest on codeforces. After the contest, I have my highest score in an individual contest(4076) , my best rank in a contest (31), my highest rating so far (1742).

PS — How many people have 100+ contest on codeforces. Who has the highest number of matches? I know Egor with 111 rated contest. Anyone higher ?