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

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

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
  • Проголосовать: не нравится  

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

The difference is pretty substantial and unique.

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

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

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

Now I have a legitimate reason to skip school.

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

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

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

i can see contestRegistrants in Hello 2018 > Goodbye 2017

UPD: and most of them will be Legendary grandmaster

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

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

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

And Thanked Mike :D

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

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

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

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

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

Registration goal-10k :-)

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

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

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

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

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

But there will also be a substantial difference:

Different problems

Best announcement <3

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

    I'm not sure I understand this statement.

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

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        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"

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

      But there will also be a substantial difference:

      Different problems

      Different writers!

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

Is this the first Hello contest ever made?

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

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

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

Best announcement ever!!

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

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

.

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

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

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

Highest ranked person on CF will not be able to participate

»
4 месяца назад, # |
  Проголосовать: нравится -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.

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

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

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

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

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

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

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

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

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

3.14-rated

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

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

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

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

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

Hello 2018.

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

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

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

*short sad story ...

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

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

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

Short statements please!!!

»
4 месяца назад, # |
  Проголосовать: нравится 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.

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

I can't wait to see these problems.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

chinese boy again changed his handle OO0OOO00O0OOO0O00OOO0OO

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

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

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

up to 10K

»
4 месяца назад, # |
  Проголосовать: нравится 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 ???

»
4 месяца назад, # |
  Проголосовать: нравится +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?

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

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

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

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

      • »
        »
        »
        »
        4 месяца назад, # ^ |
        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...?

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

        Holy crap it worked

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

    Because you are still expert :V

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

username should have a valid length. This is totally embarrassing

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

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

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

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

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

  • »
    »
    4 месяца назад, # ^ |
      Проголосовать: нравится -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."

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

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

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

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

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

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

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

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

»
4 месяца назад, # |
  Проголосовать: нравится -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

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

Dang!

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

Love that Codeforces does new things.

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

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

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

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

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

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

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

Mike did it :D

The Art of Errors Handling...

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

    And the first character isn't black!

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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится -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.

»
3 месяца назад, # |
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

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

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

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

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

»
3 месяца назад, # |
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

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

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

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

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

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

Can you consider:

  1. Making drain lower?

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

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

please dont hurt me with hardy problems daddy:(

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

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

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

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

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

World War 4 in next few minutes

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

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

well done

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

Lovely scoring distribution

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

Hello Div2

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

Hope, codeforces server work fine during the contest.

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

10 min delay

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

10 min delay

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

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

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

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

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

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

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

Anyone facing this? HAHA

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

10 minutes delay before the actual start time?

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

9K participants, yeeeeee

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

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

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

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

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

Wow. More than 9K registrants.

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

Extra 10 minutes for 10k registrants :)

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

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

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

codeforces hacking system is such a disaster now!

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

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

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

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

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

Is D ternary search on k?

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

    binary search on k

    • »
      »
      »
      3 месяца назад, # ^ |
      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.

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

      I somehow got WA with that.

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

When you try to be newbie and fool the predictor:

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

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

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

Was the hack 30 100000000 invalid for problem A?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

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

    Maybe you are missing the endline between 30 and 100000000

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

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

»
3 месяца назад, # |
  Проголосовать: нравится 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

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

What is the 6th test in C?

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

Please can anyone tell approach for 'C'?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится -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.

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

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

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

    binary search on k

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится 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)

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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?

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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.

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

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

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

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

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

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

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

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

      What about the lexicographical thing?

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится 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.

        • »
          »
          »
          »
          »
          3 месяца назад, # ^ |
            Проголосовать: нравится 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.

          • »
            »
            »
            »
            »
            »
            3 месяца назад, # ^ |
              Проголосовать: нравится 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.

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

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

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

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

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

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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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

  • »
    »
    3 месяца назад, # ^ |
    Rev. 3   Проголосовать: нравится +23 Проголосовать: не нравится
»
3 месяца назад, # |
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 ??!!

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

    It is given that vertex 1 is the root!

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится +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 ??!!

      • »
        »
        »
        »
        3 месяца назад, # ^ |
          Проголосовать: нравится +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.

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

Really elegant contest with clear statements. Thank you.

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

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

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

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

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

Really elegant contest with clear statements. Thank you.

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

I'm sure that this:

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

Passes system tests, in div2 A.

»
3 месяца назад, # |
  Проголосовать: нравится +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

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

matthew99 finally makes a comeback. Congratulations !

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

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

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

Similar problem E link only output length.

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

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

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

what was the hacks for A and B ?

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

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

»
3 месяца назад, # |
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??

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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

    • »
      »
      »
      3 месяца назад, # ^ |
        Проголосовать: нравится -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

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится +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.

»
3 месяца назад, # |
  Проголосовать: нравится 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 :-)

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

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

»
3 месяца назад, # |
  Проголосовать: нравится 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; }

  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 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).

    • »
      »
      »
      3 месяца назад, # ^ |
      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.

»
3 месяца назад, # |
  Проголосовать: нравится 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

»
3 месяца назад, # |
  Проголосовать: нравится +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.

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

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

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

can anyone please explain the approach for C?

»
3 месяца назад, # |
  Проголосовать: нравится 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

»
3 месяца назад, # |
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.

»
3 месяца назад, # |
  Проголосовать: нравится +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 :)

»
3 месяца назад,