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

Автор tourist, история, 9 месяцев назад, По-русски,

Hello 2018!

Если вы думаете, чем бы заняться в восьмой день 2018 года, обратите внимание! Первый раунд для обоих дивизионов в новом году начнётся уже 8 января в 17:35 по московскому времени (время в вашем часовом поясе).

Как новый год встретишь, так его и проведёшь, поэтому четыре важные составляющие Hello 2018 будут такими же, как у Good Bye 2017:

  • Два дивизиона вместе
  • 8 задач
  • 2 часа 30 минут
  • Рейтинговый

Однако будет и существенное отличие:

  • Другие задачи

Задачи этого раунда предложили и подготовили YakutovDmitriy, BudAlNik и я.

Спасибо также и всем, без кого этот раунд бы не состоялся здесь и сейчас: AlexFetisov, Golovanov399, KAN, MikeMirzayanov, PavelKunyavskiy, qwerty787788, VArtem, winger.

Удачи!

Стоимости задач: 500 — 750 — 1000 — 1250 — 1750 — 2250 — 3000 — 3500.

Разбор задач доступен по ссылке.

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

  1. Um_nik
  2. desert97
  3. yosupo
  4. dotorya
  5. zeliboba
  6. FizzyDavid
  7. Endagorion
  8. .0.
  9. SpyCheese
  10. Kostroma
Анонс Hello 2018
 
 
 
 
  • Проголосовать: нравится  
  • +2848
  • Проголосовать: не нравится  

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

The difference is pretty substantial and unique.

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

How sweet we have tourist as a contest writer. Looking forward to the contest.

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

Now I have a legitimate reason to skip school.

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

Wow, wasn't expecting a round with different problems, you guys are full of surprises!

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

i can see contestRegistrants in Hello 2018 > Goodbye 2017

UPD: and most of them will be Legendary grandmaster

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

i hope that there will be no math problem ...

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

And Thanked Mike :D

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

Турист вернулся :)

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

WoW , Contest writer tourist , eagerly waiting for the contest.

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

Registration goal-10k :-)

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

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

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

Как новый год встретишь, так его и проведёшь Значит сливать будем

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

But there will also be a substantial difference:

Different problems

Best announcement <3

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

    I'm not sure I understand this statement.

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

      He said "Four important components of Hello 2018 will be the same as in Good Bye 2017: ..." before this.

      • »
        »
        »
        »
        9 месяцев назад, # ^ |
        Rev. 2   Проголосовать: нравится -8 Проголосовать: не нравится

        In my case, I was seeing "Other problems" instead of "Different problems", and I thought he meant 8 problems + other problems. But then it's no longer 8 problems :p But then they fixed it. Not sure why I saw "other problems"

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

      But there will also be a substantial difference:

      Different problems

      Different writers!

  • »
    »
    9 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Also usefull
»
9 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Is this the first Hello contest ever made?

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

tourist не умеет состовлять задачи

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

Best announcement ever!!

Don't miss the chance to hack legendary grandmasters (reals and fakes) :D

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

.

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

Nice, one of my biggest competitors setting the problems this time, gonna be fun mate!

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

Highest ranked person on CF will not be able to participate

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

So, round by tourist for both divisions and without any purple guys as problemsetters... Seems to be my very chance to stop performing THAT shitty on contests.

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

Как новый год встретишь, так его и проведёшь Ну, наверно именно поэтому в начале года даётся возможность сменить ранг. (Единственное время, когда он растёт((()

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

Неплохое начало нового года!)

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

Let's not forget the idea of the first Hello contest was from the Sith

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

I'm really waiting about this contest. I hope that will be a good contest for us.

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

3.14-rated

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

It's going to be a perfect Hello 2018 :)

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

Tourist is going to be first contributor by the end of the contest!

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

Hello 2018.

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

This time I don't even have to bet for 10K+ registrants, so I bet for tourist becoming Top contributor! :v

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

*short sad story ...

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

Tourist is so overrated. He says anything and people will upvote him

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

Short statements please!!!

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

I hope know who of the setters did every problem, at least at the end of the competition, but I really want to know during the real competition. Is like knowing who you are facing when you solve the problem.

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

I can't wait to see these problems.

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

Logic Codeforces: participated in previous contest on 5/1/2018 and then the 8/1 is Hello 2018 ?? :D ??

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

If this contest was made by tourist I am afraid of queue of testing submissions

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

well it seems , the contest has legitimate reasons to cross 10k registrants.#Tourist.

»
9 месяцев назад, # |
Rev. 7   Проголосовать: нравится +27 Проголосовать: не нравится
»
9 месяцев назад, # |
  Проголосовать: нравится -22 Проголосовать: не нравится

Finally a round that tourist can't take the first place :D

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

Can any body tell me if i should sleep to prepair for the next day's exam or ... well forget it!

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

Now I wish I hadn't registered for a word games contest in my college. This will be sadly missed :(

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

Not sure if I should rejoice that tourist is the round writer .. or wish my rating good bye

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

With 1100+ uvotes on this announcement , tourist gonna top 2nd leaderboard too.:)

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

Как новый год встретишь, так его и проведёшь, поэтому четыре важные составляющие Hello 2018 будут такими же, как у Good Bye 2017:

  • Два дивизиона вместе
  • 8 задач
  • 2 часа 30 минут
  • Рейтинговый

По задачам неправильно, в Good Bye 2017 было всего лишь 5 задач.

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

chinese boy again changed his handle OO0OOO00O0OOO0O00OOO0OO

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

I dont knoy inglish( I cant anderstend yu(((

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

up to 10K

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

can you please tell me , what does it mean by "different problems" ?? i think every problem is different , from different tags like number theory , graph , dp , dfs/bfs , dsu , data structures ,ad hoc etc .

but i can't understand why "Different problems" is specialized in the blog , can anyone explain ???

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

Yea, eighth day of 2018 is great time to finish new year's eve parties and write some contest :3 But please, could somebody remind me, why is tourist organizing another contest and I still haven't do anything to have my own one?

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

    Oh, yea, I remember now, I'm so lazy, that's te reason... So hoping to see great tasks from you :D

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

      Let's see if you can get upvotes by changing your color to nutella.

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

        Yea, I've just noticed it... Really, all the time I'm getting upvotes only because of nutella? ;_; I now feel upset, so much racism on codeforces :/ And on the other hand, seriously, no one recognizes me? So much effort, so much tiring and no one recognizes Radewoosh...?

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

        Holy crap it worked

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

    Because you are still expert :V

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

username should have a valid length. This is totally embarrassing

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

Турист е**шит вообще адовые контесты.

Ну такой вот примерно проблемсет усредненный, потому что вариаций масса. Берется Good Bye 2017, но не копируется полностью, копировать — это не про туриста. Он берет этот контест, заходит на полигон и начинает задачи изменять. Добавляет в него огромное количество многомерных дп, персистентных структур, теории игр FFT! для длинки, слабые претесты делает. На все это ставятся минимальные ограничения, чтобы с запасом в миллисекунды заходило. Потом контест заливается на кф и тестится красными. Потом турист заходит на кф и начинает сам прорешивать. При этом пишет в виме на паскале. Пишет и приговаривает полушепотом ух б*я. При этом у него на лбу аж пот выступает. Любезно мне порешать иногда предлагает, но я отказываюсь.

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

    Тебя в детстве роняли?(((

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

    Это же паста топкодера

    "Tourist ebashit do a hell of contests.

    Well, that's about problemset averaged because variations weight. Taken Good Bye 2017, but not copied completely to copy — it's not about tourist. He takes this contest comes on the ground and begins the task change. Adds a huge amount of multidimensional DP, persistent structures, game theory, FFT! for Glinki, weak pretests makes. All of this put a minimum of restrictions, to the stock in the milliseconds went. The contest then is poured on KF and red tests. Then the tourist comes on KF, and he begins to progressivity. When it writes to the Vim in Pascal. Writes and says in a half whisper ugh fuck. With this on his forehead already sweat appears. Kindly I can fix sometimes offers, but I refuse."

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

WTF +1629 только из за того что он tourust ? С меня диз

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

is it rated?? please don't downvote today is my birthday.

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

Good Time! I don't have to skip class that day. Excited.

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

Before the contest ... tourist will be the first on the Top contributors list :)

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

Codeforces...you are supposed to remove Christmas decorations before January 5th...it is bad luck to keep them up longer than that. I suggest you alter the logo back although I don't know if it's binary or gets worse the longer you leave it, damage may already have been done

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

Dang!

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

Love that Codeforces does new things.

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

The comment is hidden because of too negative feedback, click here to view it

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

I hope that OO0OOO00O0OOO0O00OOO0OO will be the winner of the contest.

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

I am so shocked that no one has asked it, Is it rated though?

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

Mike did it :D

The Art of Errors Handling...

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

    And the first character isn't black!

    UPD: eh, sorry for the comment, it's him trying Grandmaster.

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

      He plays with the handle and colors like a kid !

      it was bad behavior to change the handle in such way just to ruin the CF page design !

      such a RED Coder must be more wise and contribute to make this place better.

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

That moment when I see Div-1 Coder's code failed on system test and my code get AC on same problem :D

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

So,say "Hello" to Codeforces with "Hello2018" contest :)

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

Эх, было время, когда большинство раундов было в 19.35, а не в 17.35...

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

Look at the Top Contributors list. Only Two more then Top Rating and Top Contributor tourist Love You :). You Are my first crush <3

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

Looking at the large number of upvotes for this blog post, I can't wait to see number of registrants exceed 10000

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

Вангую, когда tourist опубликует разбор, он станет вечным лидером по вкладу.

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

Can you consider:

  1. Making drain lower?

  2. Turning "handle magic" off for the contest?

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

please dont hurt me with hardy problems daddy:(

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

tourist Hey Bro :) If you reply me I will show this to my school mates

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

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

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

World War 4 in next few minutes

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

tourist finelly get the first place of the Top contributors :D

well done

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

Lovely scoring distribution

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

Hello Div2

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

Hope, codeforces server work fine during the contest.

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

10 min delay

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

10 min delay

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

We have less than one minute so good luck to everyone!

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

Yeah Sure , Let's wait for 10k participants!!

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

It seems that we have more 10 mins to prepare the contest :)

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

Anyone facing this? HAHA

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

10 minutes delay before the actual start time?

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

9K participants, yeeeeee

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

They are waiting for the total number of registrations to get 10000. Very greedy

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

Tourist can never create a complete problemset on his own, because he can't tell the difference between div2A-D

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

Wow. More than 9K registrants.

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

Extra 10 minutes for 10k registrants :)

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

my first contest of 2k18 ..very excited !!

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

codeforces hacking system is such a disaster now!

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

Dear Admin , Please make sure that system testing is fast today unlike GoodBye Contest. :)

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

for A, is it possible to hack solutions of this form: cout << m % (1 << n); ??

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

Is D ternary search on k?

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

    binary search on k

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

      When k is small, we have many options to choose from. So just greedily choose the least time consuming problems from sorted vector(acc. to 'a'). This gives a situation where every problem we pick contributes to score. But as k is small, this score is low.

      When k is large, we don't have many options to choose from. So, we have many questions we can attempt, but not all of them might contribute to score, either due to not enough options with a value greater than k, or due to time.

      So, on both sides of optimal k, we get lower scores.

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

      I somehow got WA with that.

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

When you try to be newbie and fool the predictor:

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

Very clear problem, but so hard to me. Thank you

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

Was the hack 30 100000000 invalid for problem A?

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

    I don't know how A was passing this test case.. I too tried to hack with similar test but failed which resulted in demotivation and regret of why the fuck I tried to hack and now I am going to be ripped off dark blue.

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

    Maybe you are missing the endline between 30 and 100000000

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

      I tried again with 30 (and in the next line)100000000 but it showed "ignored".

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

I couldn't get my code to compile, since apparently __int128's don't exist on CF?

http://codeforces.com/contest/913/submission/34030034

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

What is the 6th test in C?

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

Please can anyone tell approach for 'C'?

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

    If cost[i] < cost[i-1], we can just take 2^i objects instead of 2^(i-1). Just find the answer from binary representation of L.

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

Problem D seemed really fascinating but couldn't really think how to approach it !! Anyone who solved, can explain the idea behind it?

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

    binary search on k

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

      That's Nlog^2 right? I thought that it is possible to have a gap in ks, but it wasn't true so I missed this solution. But I wanted to make sure that I haven't missed a more efficient solution (mine is NlogN, but the difference shouldn't matter)

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

        No, its NlogN. You can sort array t before binary search, and then you simply need one traversal inside binary search. But, you need to keep arrays a and t together, i mean, sorting array t will mix indexes, but you can keep vector of pairs or something to keep a_i and t_i together always.

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

    I think binary search, actually im pretty sure. First, sort t_i but keep a_i with them ( you can make vector of pairs). You binary search for res, and you go through array a and ask if a_i is bigger than res, if yes add t_i to sum. If you can add exactly res elements so that sum is less or equal to T, then just lo = mid + 1, othervise hi = mid- 1.

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

    We want to maintain multiset of times for value K when we do a cycle for k from n to 0. Just add all problems with a=k and check if first k elements sum of the set is <=T.

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

    I've done ternary search by the a[i] ( the min value of a[i] that will appear in the answer ). I was late to submit. So, maybe someone did it with the same approach?

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

    I did not use binary search or ternary search. I tried all possible answers in decreasing order maintaining the best set of problems so far, in such a way that each problem is added and removed from the set at most once. So it works in : solution.

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

Problem D is binary search, I didnt have time to submit solution, I was late for few seconds literally..

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

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

I hope there is an elegant solution for problem E. It would be an implementation hell otherwise.

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

    you need to think in terms of graphs and do some sort of shortest path algorithm which obeys given grammar

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

      What about the lexicographical thing?

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

        Will the simplest brute force work? Just iterate through all the possibilities of the combination of logic...It is not that slow I think.

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

          I thought it work at first, but turned out that some of the answer is really long (more than 12 character), so brute force didn't work.

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

            So I mean the brute force with minimal branch-cutting. The point is that the brute force must be implemented correctly.

            And yes I think it is hard to debug because some of the expressions are really weird.

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

          I did that and since possiblities are just 256.I hardcoded them

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

            I saw your solution. How did you come up with the wierd formulas?

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

        here is distance is the string and we can write comparator for that as required.

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

    The implementation is not that bad. Just follow the grammar. The problem, though, it's one of the biggest piles of shit I have ever seen

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

 How can someone take n-1 integers as input using this loop and get pretest passed in problem B ?? Or am I missing something ??!!

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

    It is given that vertex 1 is the root!

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

      Looks like you didn't get my point. After n, there are n-1 inputs in the problem. But, this man loops from o to n-1, that means he takes n integers. How did he even get output ??!!

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

        There is input stream closing. When stdin closes scanf doesn't wait for input, it just returns 0. Question is what is u. I don't know, but i presume, that u is dublicate from previous iteration.

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

Really elegant contest with clear statements. Thank you.

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

In problem A how on earth this --> 34020785 get passed. can anybody explain??

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

Shitty Bug ! Spent 1 and half hour on a stupid bug!

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

Really elegant contest with clear statements. Thank you.

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

I'm sure that this:

cin >> n >> m;
cout << m % (pow(2, n)) << endl;

Passes system tests, in div2 A.

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

You know that sweet feeling when you've been debugging a source that is correct because it fails the example because the modulo is not the standard 1e9 + 7? Well now I do and it hurts like shit especially when I solved the problem 20 minutes before the end of the competition and I just found the bug...Anyway, apart from my mistakes, E was a total shit and I regret that I upvoted the contest

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

matthew99 finally makes a comeback. Congratulations !

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

CF's hack system is a total disaster. It should be disabled IMMEDIATELY until admin replaces it's flash-based hack interface

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

Similar problem E link only output length.

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

When you realize after contest that in D it's a[i]<=m to count instead of a[i]>=m. -_- fml fmr(rating)

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

what was the hacks for A and B ?

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

It's true that Problem D is the final "Too Easy Problems" ? :) But anyway, nice contest and nice problems.

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

On problem A --> How on earth this --> 34020785 submission passed the inputs test 1:

1000000

1000000

test 2:

12123

12123

test 3:

123213

123213

Can anybody explain??

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

    Even I got an unsuccessful hack attempt on a similar solution. What I observed was that the value of s becomes some large negative (something like -9.XXXX * 10^9) and the modulo returns the correct, positive remainder.

    Although unsuccessful hack, I am impressed by the cleverness of those guys. I mean, cmon! The hackbait was TOO DAMN TEMPTING XD

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

      The problem setter is tourist. Can you imagine he haven't noticed that some Contestant will submit this type of solution and those who will try to hack this type of solution will get unsuccessful hacking attempt.Of course he did and that is why he is tourist. And thats how he can fool hackers

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

    In C++ standard reference casting from double/float to int has undefined behavior if the result lies outside the range of representable values. In VC and G++ compilers it returns MAX_INT for overflowing and the modular works well.

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

I failed to hack lots of problem A solutions because of casting from double(in pow method) to int returned MAX_INT and the modular operator returns correct answer. (However in C++ reference, it talks about undefined behavior for overflowing). Anyway I learnt something new :-)

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

Ah...give me 10 more mins I can submit E...so sad.

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

In Problem A, will the code using power function for all n can get Accepted and if not can anyone help me with the hacks that can be used or if the answer is yes then why is it so because there will be overflow. (sorry about bad English.) Thanks.

// C++ ll is long long

ll solve(ll n,ll m){ ll x = pow(2,n); return m%x; }

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

    Seems like casting double to int with overflowing surprisingly gives -2^31 as an answer. int(pow(2, 1000)) = -2147483648. And yes, because m <= 10^8, m % (-2147483648) = m (which won't not be true for m > 2^30 or something).

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

      m%INT_MIN=m is true for all 32 bit signed integers except m=INT_MIN. The reason is the way % operator is defined. a%b+(a/b)*b=a always holds true, and for b=INT_MIN, a≠INT_MIN, a/b when casted to int (rounded towards 0) returns 0. Thus, a%b=a follows.

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

Problem E of this contest is almost the same as today's Problem E.It makes me feel not so good that I struggled on E for about 1 hour only to give up and was told there was a similar problem on Codeforces just after the contest. Link

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

Does the following work on H? I didn't have time to write it due to having too many bugs on G.

Say the x1, x2, ..., xn split [0, 1] into n + 1 intervals: I1, I2, ..., In + 1. Now we do dp, with the observation that the answer on each interval is going to be a polynomial. The dp formula directly shows this. The rest is then just implementing some integrals to compute the density on a real number x after k steps.

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

E is totally same with http://codeforces.com/gym/100867 problem E I don't think it's good.

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

can anyone please explain the approach for C?

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

Anyone have a list of their solutions for all 256 functions in problem E? I can't figure out why I got WA, here's my list: https://pastebin.com/r6Curstb

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

Why does my ternary search logic fail?

When k is small, we have many options to choose from. So just greedily choose the least time consuming problems from sorted vector(acc. to 'a'). This gives a situation where every problem we pick contributes to score. But as k is small, this score is low.

When k is large, we don't have many options to choose from. So, we have many questions we can attempt, but not all of them might contribute to score, either due to not enough options with a value greater than k, or due to time.

So, on both sides of optimal k, we get lower scores.

Edit : The test case I failed was due to > instead >=

But, as others did it with binary search, I wonder where my ternary search logic has flaws.

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

I created (and solved?) a harder version of problem D as I misread the problem statement as:
A task will be taken into account to the final score if a[i] <= total_solved_task. (Indeed, I pass all the samples with this interpretation)

And I wasted more than 100 minutes on it while 1k more contestants solved it :)

It's time to become a Candidate Master :)

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

Problem E:

test

1

00000000

Is the answer !x&x or nothing?

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

    Правильный ответ !x&x. Во-первых, потому что пустое выражение не удовлетворяет грамматике. Во-вторых, потому что непонятно, что должно возвращать пустое выражение.