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

Автор tourist, история, 7 лет назад, По-русски

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. .o.
  9. SpyCheese
  10. Kostroma
Анонс Hello 2018
  • Проголосовать: нравится
  • +2848
  • Проголосовать: не нравится

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

The difference is pretty substantial and unique.

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

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

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

Now I have a legitimate reason to skip school.

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

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

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

i can see contestRegistrants in Hello 2018 > Goodbye 2017

UPD: and most of them will be Legendary grandmaster

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

And Thanked Mike :D

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

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

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

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

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

Registration goal-10k :-)

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

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

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

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

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

But there will also be a substantial difference:

Different problems

Best announcement <3

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

Is this the first Hello contest ever made?

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

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

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

Best announcement ever!!

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

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

.

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

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

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

Highest ranked person on CF will not be able to participate

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

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

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

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

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

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

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

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

3.14-rated

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

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

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

Hello 2018.

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

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

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

*short sad story ...

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

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

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

Short statements please!!!

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

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

I can't wait to see these problems.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

chinese boy again changed his handle jqdai0815

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

up to 10K

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

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

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

username should have a valid length. This is totally embarrassing

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Dang!

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

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

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

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

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

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

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

Mike did it :D

The Art of Errors Handling...

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

    And the first character isn't black!

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

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

»
7 лет назад, # |
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

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

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

»
7 лет назад, # |
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

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

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

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

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

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

Can you consider:

  1. Making drain lower?

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

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

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

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

World War 4 in next few minutes

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

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

well done

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

Lovely scoring distribution

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

Hello Div2

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

Hope, codeforces server work fine during the contest.

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

10 min delay

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

10 min delay

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

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

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

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

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

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

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

Anyone facing this? HAHA

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

9K participants, yeeeeee

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

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

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

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

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

Wow. More than 9K registrants.

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

Extra 10 minutes for 10k registrants :)

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

codeforces hacking system is such a disaster now!

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

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

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

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

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

Is D ternary search on k?

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

    binary search on k

    • »
      »
      »
      7 лет назад, # ^ |
      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.

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

      I somehow got WA with that.

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

When you try to be newbie and fool the predictor:

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

Was the hack 30 100000000 invalid for problem A?

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

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

    Maybe you are missing the endline between 30 and 100000000

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

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

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

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

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

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

Please can anyone tell approach for 'C'?

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

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

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

    binary search on k

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

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

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

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

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

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

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

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

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

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

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

»
7 лет назад, # |
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 ??!!

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

    It is given that vertex 1 is the root!

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

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

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

Really elegant contest with clear statements. Thank you.

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

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

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

I'm sure that this:

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

Passes system tests, in div2 A.

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

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

matthew99 finally makes a comeback. Congratulations !

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

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

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

Similar problem E link only output length.

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

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

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

what was the hacks for A and B ?

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

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

»
7 лет назад, # |
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??

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

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

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

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

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

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

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

    • »
      »
      »
      7 лет назад, # ^ |
      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.

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

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

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

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

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

can anyone please explain the approach for C?

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

»
7 лет назад, # |
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.

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

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

Problem E:

test

1

00000000

Is the answer !x&x or nothing?

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

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

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

      Кстати, а почему в грамматике, то есть кавычки, то нет?

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

        Везде, где в грамматике встречаются символы из выражения, они идут в кавычках. Символ | без кавычек означает что нетерминал слева может раскрыться в один из нескольких вариантов, перечисленных через |.

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

In problem G, I add some last digits such that the result number N satisfies N % 2|N| = 0 and N doesn't end with 0 or 5. The rest is to find k such that N ≡ 2k modulo 5|N|. It seems to be done by induction.

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

    I thought the same thing but forgot that N % 2^|N| needs to be 0. If you can prove the minimum |N| needed, there's a way to find k in O(5^(|N|/2) * log(|N|)). Also, it looks like 2^i passes through all numbers not divisible by 5 on modulo 5^|N|. The way to find k is finding the numbers 5^(i * floor(sqrt(n))) and starting from the number you want going back (multiplying by floor(5^|N| / 2) + 1 that's the modular inverse of 2) until finding a number that's from 5^(i * floor(sqrt(n))).

    Edit: but probably there's a smarter way to solve it, something like getting the answer for 5^x using the answer from 5^(x — 1), since 2^i is a cycle through 5^(x — 1) and probably through 5^x so the answer for 5^x is i * size of cycle + answer for 5^(x — 1).

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

Can someone please explain to me why this submission on problem D passes the pretests?

On the first example test (which is usually the same as the first pretest), it outputs:

2 2 3 4

... implying that you get a score of 2 if you solve problems 3 and 4. But you don't, you get a score of 1 (since problem 3 requires 4 solved problems). Am I missing something or is the judge for this problem broken?

EDIT: nevermind, it seems like I interpreted the statement wrong. I thought a[i] has to be smaller than the total number of problems, but in reality a[i] has to be greater than the total number of problems... and reading through the comments here, it seems like I'm not the only one :P

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

D is straightforward binary search . Lost a good amount of time while debugging C ! :( . bad contest.

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

    Just because you can't handle overflow doesn't mean contest is bad >:(

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

Hello 2018 but with the old name... So sad

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

I find this contest so much better than the good bye 2017. I'm very grateful to the authors.

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

Correct way to solve C?

Also, hello 2018 and rating drop my old friend...

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

    Let's update ci: ci + 1 = min(ci * 2, ci + 1). After this we may see that taking away 2N - 1 until L ≥ 2N - 1 is optimal since it's the smallest price we can get 2N - 1 litres for. Then there're two possibilities if there are remaining coins: you either take one more 2N - 1 or go and do the same thing for 2N - 2 till L ≥ 2N - 2 and so on.

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

    Look at my code

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

check this out that's why you are not red yet :v http://mirror.codeforces.com/contest/913/submission/34025378

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

What is TC 8 on problem C all about?

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

include<bits/stdc++.h>

using namespace std;

int main(void) { long long m,n; cin >> m >> n; long long result; result=pow(2,m); cout << n%result << endl;

}

How this code got AC for problem A? I used repl.it compiler and it gave RE.

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

Failed... and Failed... and Failed...; HELLO 2018!!!

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

failed :/

and failed :'/

and failed ×_×

...HELLO, 2018!!!

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

Is it just me or you also had these failed problem phases? in all last couple of contests, I had systest failed problems for stupid reasons, in all of them. I'm really stuck in this sh*tty rating because of the HUGE effect that a 1000 or a 500 point problem can have.

You know what's my problem with codeforces? I can solve all of the "easy" problems in a relatively small time, for example, I solved the first four in 49 minutes, not bad, but I'm not using the extra one hour and half for anything (Sometimes hacking, but you always have this belief that you can solve another one). And I'm not alone, usually, the easy problems are solved by more than 1000 people at the end of the contest. the next problem is solved by like 100 people, of course, I can't easily solve it, there are 100+ GMs competing too and they couldn't.

So what's the way for me to get a good rating? submit questions fast, if I don't I will get more penalty and since 1000 people already solved all of the easy problems, I will have a rank like 700+ which is not good. So I have to be fast. Alright, but getting pretest passed is also not a 100% guarantee to get a score of a problem. and when you fail to solve a problem what happens? you go miserably down on ranking.

Even if I have many good contests one after another and I bring up my rating, again there will be another contest, super hard to solve more than 3, and you just need a silly mistake on A to fail and with only B & C for example go down terribly.

I don't care about my ranking, I just don't like the feeling of being stuck in Div.2 for this long. Every time I have to solve things that are not really adding to my knowledge like Div2.A and Div2.B and a lot of times Div2.C.

Tl;dr, I just want sort of contests on codeforces, that have a mellow decreasing number of people who could solve the problems. something like 3000, 1500, 700, 300, 50.

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

    I believe that virtual participating in previous contests, with practicing on being careful and quiet during reading and solving problems, will decrease the possibility of failing in post-test in real contests.

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

what's the easiest and fastest solution for C?

please explain completely(not just like most of editorials :))

UPD1:I read tutorial and it was easy and fast and complete enough :D

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

Is rating predictor alright? Doesn't seem so by looking at the rating predictions.

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

    Things got pretty complicated in the predictor due to handle changes (newly-used handles will be identified as new users by the predictor, therefore, the prediction is way too different).

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

one of my friend solve A with cryptography

34024600

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

hi there

i've a question about my problem B

why this 34032197 sulotion should get acc while the MAXN = 1000 & somewhere i've used adj[1000] ????

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

My submission for problem D, fails on the 23rd test case, but the checker log is weird, I don't have access to the full test case, but my answer seems correct based on the little summary that I can see.

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

    I think this error means that "You said max score possible was 89771 but the score calculated from the indices you printed is 89770"?

    Not 100% sure but it seems this way.

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

    it says that the 89772 items you chose gave you actual score of 89770 not 89771 as written in the first line of your output, so I think the mistake is not obvious by just looking to the summary

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

      Yes, I got accepted now. Also thanks to tourist for taking the time to read and debug my code.

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

        what?

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

        Could you explain?

        Why your code gets wa?

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

          I explained you already in private message, anyway again:

          If you answer more questions than the actual number, it might make other questions useless. (does this sentence make sense?!)

          For example imagine we have infinite time to answer the questions and our "a" sequence is {2, 2, 2}. The answer is of course 2, but if we solve all three problems, we get 0 points.

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

            Thank you :D

            I forgot some statement

            Unfortunately, your teacher considers some of the problems too easy for you. Thus, he assigned an integer ai to every problem i meaning that the problem i can bring you a point to the final score only in case you have solved no more than ai problems overall (including problem i).

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

Can anyone help me, Im getting TLE on D even though my solution is NlogN. http://mirror.codeforces.com/contest/913/submission/34032577

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

    maybe there is problem with binary search? infinite loop?

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

    Well... first, I see you do int a[100010], t[100010] but n is up to 2 * 10 ^ 5. Secondly, at some point in your code you have res.clear();, but a few lines later you access res[i] (vector res is now empty).

    Quick edit: it seems like by doing the above modifications (setting the array size to 200010 and commenting the res.clear(); line) gets you accepted.

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

      Thanks so much! But its weird how I got TLE for mistakes that dont affect time but only corectness and memory (am I right? ).

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

        In C (and C++), accessing out-of-bounds memory causes "undefined behavior", which is a term for "anything can happen and you (generally) don't know what to expect". Results of undefined behavior are implementation-specific (depends on the compiler). For example, it is not impossible that your out-of-bounds array access might have overwritten some data important in memory which caused you to TLE (maybe the variable which dictates the loop limit or the loop index, the return address of some function on the stack etc).

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

There is a substantial difference: https://www.diffchecker.com/zgfaXp6C :)

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

Здраствуйте в этом контесте у меня совпали решения с аккаунтом nis2016, оба аккаунта являются моими. Произошел случай что я не смогу войти со своего основного аккаунта adlet.balzhanov. После этого я решил написать контест через свой старый аккаунт. Но в середине контеста я смог зайти в свой основной аккаунт с сдать эти задачи через него, используя свой предыдущие коды. Я в полной уверенности могу доказать, что оба аккаунта мои, предоставляя к обоим пароли и логины. С уважением, Балжанов Адлет.

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

Hello 2018 by being Purple for the first time :)

Thanks tourist for a great contest! :D

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

The difference between WA on test 8(pretests passed) and AC: [](https://imgur.com/gallery/LLTRc)

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

shbhm_5301 Please explain your solution of C (34024529)

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

Thank You [user:tourist]for nice and pretty problem. Now I am a Blue Coder :'(. I am Very Happy For That. :). After 2 years.

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

Thank you very much for the great contest tourist. I've finally become blue.

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

TC 17 of problem B:

13 1 2 2 2 1 6 6 6 1 10 10 10

Node 1 doesn't have 3 leaf children, so it isn't a spruce tree. But the correct answer is YES. Can someone explain it to me?

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

    I just got the idea and understood why the correct answer is YES. My big mistake :(.

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

      The answer for that test case is NO.

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

        I figured out that I understood the problem correctly but there is a bug in my program. How silly of me! :(

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

    This is interesting. It is heavily dependent on the compiler, but it seems like these two lines can get interpreted differently:

    ll b = (get + v[cur] > L) ? dfs(cur - 1, get, cost) : 1e19;
    ll b = (get + v[cur] > L) ? dfs(cur - 1, get, cost) : (ll)1e19;
    

    Again, this is compiler-dependent, but I tested this on VC++ 2017 and it seems like in the first case the compiled code interprets 1e19 as a double (which it is) and converts it to an unsigned long long at runtime via a low-level function __dtoul3. As you might know, conversion from double to integral types can introduce precision errors. In the second example, the compiler treats (ll)1e19 as an integral constant (i.e. it behaves exactly as it would if you were to write 1 followed by 19 zeores) and therefore no conversion error occurs.

    I know this is an unpopular opinion, but this is why I always advise against using scientific notation for integer constants. Even though most modern compilers behave in the same way and work correctly, the C++ standard leaves many details about conversions to the specific implementation of the compiler. Although this doesn't usually introduce problems, sometimes it just might (and this is the perfect example). Just write 100000 instead of 1e5. You'll have to type out a few extra characters, but you'll avoid unpleasant surprises :)

    P.S.: my compiler gives me this warning in the first version of the code: warning C4244: 'initializing': conversion from 'double' to 'unsigned __int64', possible loss of data Even though it is in no way a must, personally I always fix warnings before submitting a code. It's good practice. (the company I work at compiles with the "treat warnings as errors" option).

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

      Thank you for your detailed explanation!! :>

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

      interprets 1e19 as a double (which it is) and converts it to an unsigned long long at runtime

      Yes, it interprets 1e19 as double, but it will promote the dfs return value to double and later cast to long long when assigning to b (this is where the warning comes from). Integer values are always promoted to floats, not vice versa.

      Also I don't get why it would be dependent on the compiler, seems well defined to me?

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

Hooray

That means we will have "Hello"-contests anually, doesn't it?

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

Does anyone notice that this contest's rating changes are lost?

UPD: It has returned already :)