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

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

Всем лучей добра!

Надеюсь, что за прошедшие дни вы все прекрасно отдохнули, вдоволь наигрались с цветами и хэндлами и преисполнены позитивных ожиданий в отношении 2018 года :)

В свою очередь, я рад анонсировать первый контест этого года — Codeforces Round #456, который состоится в эту пятницу в 17:35 по московскому времени. Раунд будет рейтинговым для участников из второго дивизиона. Впрочем, мы будем рады видеть и первый дивизион на внеконкурсных основаниях.

Авторы раунда — GreenGrape и rek (не пугайтесь, это всего лишь новогодняя магия ^^). Спасибо Коле (KAN) за помощь и координацию раунда, Грише (gritukan) и Олегу (x3n) за ценные советы, тестирование и помощь в вычитке и переводе условий, Диме (cdkrot) и Глебу (glebodin) за прорешивание и Майку (MikeMirzayanov) за прекрасный Codeforces и фичи в Polygon.

Надеемся, что наши задачи скрасят ваше времяпрепровождение в холодный зимний вечер.

Удачи!

UPD. В раунде будет пять задач со следующей разбалловкой:
500 — 1000 — 1750 — 2000 — 2500
Как и всегда, советуем прочитать все задачи :)

UPD. Обратите внимание, что регистрация перенесена на несколько часов вперед.

UPD. Контест закончен.
К сожалению, получилось чуть сложнее, чем мы ожидали. Но надеемся, что вам понравилось и вы узнали что-то новое для себя :)

UPD. Разбор!

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

Div. 2:

  1. apink
  2. anger_of_singledogs
  3. markiz
  4. supy
  5. ratel

Div. 1 (unofficial):

  1. dotorya
  2. ksun48
  3. irkstepanov
  4. Benq
  5. quailty
 
 
 
 
  • Проголосовать: нравится  
  • +499
  • Проголосовать: не нравится  

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

The announcement is made early for once :)

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

For some of us it might be morning

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

"Time to forget about messing with handle colors and get back to coding!"

If the registeration was by color ... there would be no div.2 participants, the whole scoreboard will be painted in red :D

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

Что? Раунд от зелёного? Ах, да. Новый Год же.

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

Don't skip the opportunity to hack legendary grandmasters

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

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

Thank you GreenGrape for one more contest, also I'm really thankful to MikeMirzayanov for giving us chance to have fun.Good Luck and Have Fun)

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

Задачи будут на русском ?

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

    На обоих языках. Все раунды на кф пишутся на двух языках (мб и больше).

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

At first, I freaked out seeing the authors' handle colors...then I looked at my handle color xD

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

Wew!@ Time to do what I once didnt/couldn't:)

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

Welcome to the first contest in 2018. Sure fun for us.

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

First one in 2018 ;)
IsIt0.5Rated?

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

a lot of Legendary grandmaster will participait in this contest sounds like very intresting :)

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

Educational round 35 был про время перед новым годом. Good Bye 2017 был про сам Новый год. Codeforces round 456 может будеть про время после Нового года

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

New Year magic workouts! Makes LegendaryGrandmasters to Brain storm for score in Div.2.

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

hacking might get confusing!

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

    don't worry, now colors are deceptive, but during the contest they will be returned to the real state if I'm not mistaken.

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

Wishing everyone high ratings and lots of green AC this year

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

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

LOL

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

rated hahahaha

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

My solution was caught in plagiarism with another of my own solution in the last educational codeforces round. The problem has not been rectified yet. Can somebody help ????

Upd: The solutions have been accepted but the rating change has not been reflected. P.S I am a div2 contestant . Don't look at my color.

Upd2: I saw mike's blog post . The issue has been resolved. Thanks

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

Time for changing color ;p

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

A contest where newbies and pupils will hack grandmasters codes. :P

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

Old handles are appearing in the contest registrants page instead of new ones, is it a bug? Or its meant to be ???

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

Fastest score distribution ...!!! :)

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

this contest will be pretty confusing to these people who depend on color to hack

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

My new year's resolution : "Become a candidate master". Wishing for ratings, not colour. :)

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

Надеюсь авторам не придётся извиняться перед Kadyrov_95

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

RUSH B!!!!!!!!!!!!!!!!!

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

I hope D and E will be very difficult so nobody can solve them

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

There are so many Red Coders participating this time!! :P

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

In registered user page, it's showing the previous username, not the changed username. Is it a bug or intentional?

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

I have a bad feeling, looking at the long queue 3 minutes before the contest...

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

I hope D and E will be very difficult so nobody can solve them

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

C is harder then usual codeforces round :(

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

I believe the problem setter has set the questions seeing the color of participants and not ratings. :(

Now I realize, how tough it is to be a LGM.

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

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

does Problem C refers to Dota2? Lol

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

I don't even understand C

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

Balancing the difficulty of problemset is the ground rule for preparing of contest.

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

How to solve E?

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

    Meet in the middle and binary search

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

      Can you explain your approach. I just hoped that bitmask will suffice.

      Okay, understood. I actually thought about MIM but didn't think bitmask would be tle.

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

        Divide array two parts and calculate answers for them as you do in MITM. Then binary search answer with counting numbers which satisfies condition. Be careful with overflow, it cost me 3 WA and a lot of time

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

Is intended solution for E is binary search + meet in the middle?

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

Can anyone help me with D? :(

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

    Linearity of expectation

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

      Can you please elaborate

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

        Expected number of fishes caught = Σ P(catching fish at (xi,yi))

        Now, select k distinct (xi, yi) such that sum is maximised.

        P(catching fish at (xi,yi)) = (#Net positions covering (xi,yi))/(#All Net positions)

        We can start by selecting middle element, and adding neighbors in the order of decreasing probability (using priority queue)

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

          How do you compute the probability for each of the individual cells of the matrix?

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

That moment when all you do in life is play DotA 2 and you can't even solve problem C which discusses the Hero Zeus' ulti.

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

My thought process while trying (and failing) to solve C:

At first I was overwhelmed by all the information, but then I realized I can probably store times where regen graphs cross the damage threshold in a treeset and process them before/after each query as needed, and simply ignore everything with maxhealth <= damage, as they will always be killable, so as a result if everyone's max health is less than damage you can kill them anytime (infinite bounty).

An hour of spaghetti later, I submit and get WA

"Oh, obviously! I forgot the case if regen of an enemy is equal to zero!"

WA again same test case

"Oh, of course! I forgot the case if increase = 0, then bounty can never be infinity"

WA again same test case

"Oh, right. He can only do integer values, so if it's not evenly divisible I have to consider integer value right before crossing the threshold and right after..."

WA again same test case

There are too many special cases and other things to consider in this problem in my opinion. Maybe Dota2 players who code are super familiar with the algorithm because they do it in their head every time they play, but for the rest of Div2 Codeforces it is not quite as easy. That's the only way I can think of this problem being selected as a C problem.

Anyway reply with elegant approaches/solutions if you'd like, they will be much appreciated.

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

    Important realisations: 1) If bounty increase is >1 and the max_health of any enemy is <= damage, the answer is -1 2) If bounty increase is >1 and health increase of any enemy is 0 and the last updated health of an enemy is <= damage, the answer -1

    After taking care of those special cases it is just easy time_line problem where you mark all the +1/-1 points (new enemy I can kill/since this point I can not kill some enemy).

    I used multiset at first, map later ended up with sorting a vector of time-line points, however always got TLE on the 8th test-case.

    Overall nice problems, but really pissed by the distribution of correct solutions of the tasks (compare C to D or B).

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

    C is annoying to code even if the solution seems elegant while thinking. Maintain 2 sets (RIP and non-RIP, RIP for heroes whose current health <= damage). Maintain an event priority queue. There are three kind of events: -1 (compute bounty), 0 (transfer a given hero from RIP to non-RIP set, to account for regen), 1 (Set current health of a given hero). Process the events in priority (-time, type). There are still annoying edge cases to handle (For example, future events of type 0 can be invalidated by events of type 1).

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

    missed the case when increase = 0 but still passed pretests :/

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

    I'm sorry to break it to you. But this is nothing like Dota2. The mechanism are totally different. The idea is only about Dota 2 nothing more. Examples:

    1) No hero has 0 regeneration

    2) Bounty is not this way

    3) You don't care how much gold you get and the bonus will never become infinity So, knowing Dota2 will completely change nothing.

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

      1) Ancient Apparation's ult or Spirit Vessel effect
      2) That's true, I must admit :)
      3) You actually do care about the amount of gold you get when you play Dota 2

      Though you are right that Dota 2 experience would not really help with solving this problem :)

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

        Well, what's important is general agreement.

        The statement implies that there can be a hero with 0 regeneration throughout the whole match, and that's impossible.

        You can't deny the fact that when you can kill, you'll kill. It doesn't matter how many you kill (AND YOU DON'T WAIT TO +INF TO USE YOUR ULTI)

        What's important is playing Dota 2 won't help you solve the problem, practicing will!

»
4 месяца назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится
If (k == 1) {
  cout << n;
  return 0;
}
»
4 месяца назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

B is a b!*ch -_-

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

Didn't even read C

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

Спасибо за интересные задачи!

Всех с новым 2018 годом

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

Any idea what TC4 is in C?

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

Idea for E?

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

    split array into two parts (I had 6 and 10)
    calculate all possible numbers for every part with dfs in two arrays L and R
    then do binary search for answer and you must for mid calculate how many are there i and j that L[iR[j] ≤ mid
    that can be done with two pointers
    works 1.5 sec

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

In div2.B I didn't read "no more than k", I thought I had to choose strictly k. :c RIP rating.

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

    in B i thought it was saying about exactly k element need to take.

    but after 1 hour i saw that not more than K.

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

    I thought it was exactly k too, but I don't think it matters for me because I couldn't solve it anyway

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

      Just set all the bits.

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

        Oh yeah, I think "at most k" is easier, because it is guaranteed to find two numbers in range 1..n who are 1's complements of each other ..

        is the answer 2^( ceil(lg(n)) )-1 ?

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

          find the right most set bit of n and set all the lower bits. If x is rightmost set bit then ans is = 2^x +2^(x-1)+...+2^0

          Base case if K=1 then ans is n

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

            Yeah, and 2^x +2^(x-1)+...+2^0 = 2^(x+1)-1

            Can't believe it was so simple >_>

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

Is D just hard work with cases and formulas or there's some elegant solution?

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

    Maybe mine
    I had Dejkstra algorithm. Just start from (n + 1) / 2, (m + 1) / 2
    take each time point with largest cost
    cost can be calculated like this

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

Can anyone tell me what's wrong with this hack?

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

    The fact, that only you can see it =)

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

      Oops, sorry. It will probably be available after systests.

      It's a hack for problem C:

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

It seems me, that Python and accuracy are incompatible http://codeforces.com/contest/912/submission/33928268

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

Problem A: very funny...

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

After reading Problem C

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

Problem D: Use linearity of expectation.

For a cell (i, j), number of squares can be calculated like this: https://ideone.com/KbWoW7 (For upper left corner You find a valid range for lines, a valid range of columns and then you multiply the ranges lengths)

Now we have 2 vectors L(i) = the length of range for line i, C(j) = the length of range for column j. So number of squares that contain cell (i, j) = L(i) * C(j);

Sort vectors L and C in descending order. So L(0) >= L(1) >= ... >= L(num_of_lines) , C(0) >= C(1) >= .... >= C(num_of_columns)

Now at each step we need to choose a line i and a column j which gives the best L(i) * C(j).

Mantain a vector Last(i) = For the line i, what is the best column avaible? At the beginning Last(i) = 0;

We'll keep a multiset where we insert all lines, and we will keep the multiset sorted by L(i) * C(Last(i)) descending order.

Now, we do this k times: Extract beginning of set = A line i, add that L(i) * C(Last(i)) Value. Update Last(i) = Last(i) + 1 Add i to multiset again.

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

    Can you please explain the thought process behind the formula to calculate the number of squares for a cell.

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

If you solve E with only bitmask (and reverse sorting the given list of primes), what's the complexity?

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

    Still won't pass. I did my best putting in tons of heuristics ( that I even used to accept similar problems before), and always got TLE on pretest 5/6. Test cases are strong, good job to the testers/authors.

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

      Interesting. I thought as the masks grow, the number of values we need to try decrease significantly. Probably some randomization will be needed. What's the complexity anyway

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

E passed, time to back Div.1! :-)

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

I used tenary search for problem C, i still dont know where im wrong Here my code : https://ideone.com/grWZlx

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

С решило меньше, чем D. Вот что бывает, когда контест составлялиют зеленые! :)

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

Today I realized,

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

Problem C. Test case 4 is wrong 2 0 1 0 1 10 1 1 2 1 0

The second enemy has start health = 1, regen = 0. So I can wait forever to kill him (I have damage = 1), so I can have infinitely gold. The answer is -1. But Jury's answer is 2.

My submission. 33945948,

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

Shouldn't they be disqualified because of cheating?

http://codeforces.com/submissions/Combi/contest/912
http://codeforces.com/submissions/Cinzaderius/contest/912
Upd: Only 1 submission was skipped, really?

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

    Wait Wait! there's no cheating there, they have a huge difference in problem B, one declared int and the other declared long ;o ._. haha. now on a more serious note :/ come on guys this is to improve over time not just for the ratings.

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

      I'm send my apology to everybody scerely because of that cheating.I won't send my code to him anytime in the future.Please excuse me!

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

    They are friends, I'm sure that the next time, they will continue cheating by changing template, such as #define int long long — #define long long long, etc... to avoid being skipped

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

Why this formula (pow(2,floor(log2(n))+1)-1) fails for #test 48 (n=288230376151711743, k=2) in problem B

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

Why this formula (pow(2,floor(log2(n))+1)-1) failed for #test 48 (n=288230376151711743, k=2) in problem B

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

    There are issues with built in logarithmic functions. For example, in python, the log of that number is 58.0000001 while the actual log is 57.9999...

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

      I used builtin log function even after being aware of this issue and having evaded this problem many times in the past. -_-

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

      But same code got accepted when I changed long long to long double for n and k. Why is this so?

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

        log2 and friends (log2f and log2l), as in the C standard library, accept only double, float and long double parameters. So what happens when you pass a long long to it? C++11 (and future versions) explicitly say integral types get converted to double (not long double!) before calling functions from <cmath>. Since the values in this testcase are not representable as a double, you get precision issues.

        Below's what the standard says in §29.9.1. Rule 2 applies in your case.

        "For each set of overloaded functions within <cmath>, with the exception of abs, there shall be additional overloads sufficient to ensure:

        1. If any argument of arithmetic type corresponding to a double parameter has type long double, then all arguments of arithmetic type (6.9.1) corresponding to double parameters are effectively cast to long double.

        2. Otherwise, if any argument of arithmetic type corresponding to a double parameter has type double or an integer type, then all arguments of arithmetic type corresponding to double parameters are effectively cast to double.

        3. Otherwise, all arguments of arithmetic type corresponding to double parameters have type float."

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

          I use type conversion. Even after it will not work.

          a = ((double)log2(n))

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

            Casting the return value cannot provide you with more precision (since the value is already calculated). That would be CSI-level enhancing :)

            We want to ask the function to calculate using type long double. There are two ways to do that: log2l(n) or log2((long double)n).

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

    The same condition happens to me and this is the very worst thing. Else we also get contest rating as well. 48.....

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

    I also faced the same problem and got wa only for this issue. i tried to get log2 by doing log10(n)/log10(2) but got wa.. while debugging the only thing i got was a precision related issue which i'm experiencing for first time in a built in function.. calling log functions with an extra 'l' at last(taking long double as arg) worked fine..

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

Please note that this announcement is not (yet) attached to the contest.

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

говно, а не раунд (чисто объективно говорю)

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

    а че вы минусуете, животные безмозглые? По-вашему, это нормально или что?

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

in problem B why my log does not work for big numbers. (log2 (2 ^ 58 — 1)) it will return me 58 which is wrong that's why My problem B is not accepted and failed in test case 48. please clarify me, is there any limit when log function will not work ??

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

why is rank of some users different from what their rating indicates? this probably happened during Goodbye 2017 coontest.

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

prob b http://codeforces.com/contest/912/submission/33945293 test 5 works on the csacademy compiler, but its not the correct answer here?

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

    1UL has type unsigned long. (unsigned) long on 64-bit architectures is a 32-bit type on the Windows ABI and a 64-bit type on Linux (LP64 ABI). Codeforces runs on Windows. You wanted 1ULL :(

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

Where did the editorial go?

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

My solution for A works more than 1 sec. On this test 10^9 10^9 0 10^9 0 Weak tests...

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

Please help me out with Problem B Link to code- http://codeforces.com/contest/912/submission/33950052 I first convert number n to binary, then traverse the binary string checking if '0' is there -> convert it to '1' and decrement k. Getting WA from test case 9.

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

the round was trash never problemset again

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

Hi, Could anyone tell me why Jury's answer for case 11 of Problem C is 1 ? Since I see there is a horizontal line (value = 1), my answer is -1. [input] 1 0 1 0 1 1 1 1