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

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

Приветствую сообщество Codeforces.

18 июня 2015 года в 19:30 MSK состоится очередной раунд Codeforces #308 для участников из второго дивизиона. Традиционно, участники из первого дивизиона могут участвовать в соревновании вне конкурса.

Это мой второй Codeforces раунд(первым был раунд Codeforces Round 280 (Div. 2)). Надеюсь, он вам понравится.

Большое спасибо Максиму Ахмедову (Zlobober) за помощь в подготовке задач, Марии Беловой (Delinur) за переводы на английский, Михаилу Мирзаянову (MikeMirzayanov) за замечательные системы Codeforces и Polygon.

Участникам будет предложено пять задач и два часа на их решение.

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

UPD: Поздравляю победителей:

  1. Ttocs45

  2. RNS_JKS

  3. RNS_CUS

  4. kouekosita

  5. grenade

UPD: Контест закончен. Всем спасибо за участие :)

UPD: Разбор задач

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

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

Автокомментарий: текст был обновлен пользователем Wild_Hamster (предыдущая версия, новая версия, сравнить).

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

i hope this round has harder problems than round #280.

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

    Your last round was interesting and solvable ! I believe it will be easier than round 307 :)

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

    just noticed round #280 is my first contest in code forces. Well, and after this round I am in Div-1, so when is the next round maybe i will be red :D

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

      You are really lucky to get your solution for D passed! :P :D

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

      My history:

      First Codeforces round participation = round #235

      First Codeforces round to get in div1 = round #263

      difference in number of rounds = 28

      Your history:

      First round = 280

      First round to get in div1 = 308

      difference = 28

      And my current rating is the same as that after round 263 . So clearly this is not a good metric to judge how soon you would become red :)

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

Happy Ramadan holiday to all. I wish luck for today's contest to every participants.;)

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

Всем УДАЧИ!))) Хочу сегодня стать синим))))))

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

    Синим ещё куда не шло, главное голубым сегодня не стань :-)

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

      шутки про голубых не для таких сайтов, как Codeforces

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

        а какие шутки для таких сайтов как Codeforces?

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

          Например такие: Однажды ты спросишь меня, что для меня на первом месте: ты или программирование? Я отвечу тебе, что ты. Но ты никогда не узнаешь, что программирование для меня на нулевом месте:)

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

          про молоко

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

        Зачем же сразу минусовать? Человек с чувством юмора. Ничего плохого нету ;)

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

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

    а я думал что я тут слабый, всего-то фиолетовый, а тут люди синими мечтают стать

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

Izi problem, izi life

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

I hope this round have some problems which i am not able to solve.

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

    then u should attempt div 1 mate !!!

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

      The fact is that in many div 2 only contests there are some problems which are very hard and brilliant!Beyond that , i participate unoffically this contest so it is more important for me to learn something new than to get a good rank.

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

Wild_Hamster has a recursive profile pic

how did you make it

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

    His profile pic is in Russian, but my interface is in English :)

    Also the rating and contribution are different.

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

    My guess would be 1. take a screenshot of your profile. 2. copy+paste 3/4th of the screenshot to the remaining 1/4th space by reducing its size. 3. Repeat 3-4 times till its possible to do this within the smaller window each time. But this is just my guess.

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

    блиииин, забыл зарегатся(((((

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

Every contest is simply amazing !!

Somebody will participate officially , others no , but the idea is improve in each contest.

Enjoy the problems and keep the calm !!

Good luck and Have fun to everyone !!!

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

Every contest is simply amazing !! Somebody will participate officially , others no , but the idea is improve in each contest. enjoy the problems and keep the calm !! Good luck and Have fun to everyone !!!

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

I hope that there will be no delay, no lag near the end of contest, and no cheaters :)

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

I think it's time to publish scoring

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

When you know you are closest user to Div.1 but you know it will not be happen :(((

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

Please announce scoring.

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

Help please register me for this contest please.There is still time left.Please

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

Пропустил регистрацию можно что то сделать?

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

Please Register me for this round please.Please

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

Did you notice live judgement updates on the status page? Do not hope to see verdict faster by pressing F5, this page now gets live judgement stream directly from the judging module!

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

For me it's really interesting why each Div2 round there are persons like this http://codeforces.net/profile/liyankui who solves all the problems without participating in any other contest before.

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

    I'm gonna be captain obvious here in case there's someone that doesn't know — Div1 users make new accounts to win Div2.

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

      Ok, what is the goal of doing it?

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

        Very frustrating I know. What is the point of red/orange coders beating div 2 guys? What are they trying to achieve this way? Its somehow fun and exciting for them, but very frustrating for div 2 participants.

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

        There is none, they just want to see themselves on the blog and feel good for being top5. We've all agreed it's a stupid practice, and it has been discussed tons of times before.

        Sadly there is no efficient way to stop them from doing it without limiting other competitors.

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

Its not programming contest, its math contest...

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

    Brute Force, Digit DP, Number Theory ( ok, this one is math ), Geometry and I am not sure about the last one since I couldn't solve it. It was somewhat balanced I guess.

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

      C is brute force :D

      when w=2 or w=3 the answer is always YES , when w>3 you will not use more than the first 16 weights so you can use O(3^16) brute force

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

        not necessarily, my solution uses 100 iterations only

        http://codeforces.net/contest/552/submission/11642323

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

        it could even be done in O(216) . You assign m to one pane and w0 to w15 to any pane and then try to balance both pans by removing weights greedily.

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

        how did you know that you will not use more than the first 16 weights ?

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

          If w >= 4 and there are 17 weights, then the minimum number we can get (positive) is 4^16 — (1+4+...+4^15), more than 10^9. And it is clear that with more weights, the minimum is even more.

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

            then if we have in the first pan (1 + 4 + ... + 4^15) and in the second pan (4^16) the difference is larger than 10^9. however, why we can't put some weights to the first pan say (4^x & 4^y) then put (4^z) in the second pan to get the scale balanced again ?

            how did you prove that such numbers like x, y, z don't exist!

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

        3^16 brute force can be optimized with meet-in-the middle approach to do it in 2*(3^8)

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

        we can solve C in O(log n)

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

        Sorry, But how do you know that you will not use more than 16 weights? Is it depending on maths?

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

        Is it possible to find some weights more than w^16 to get the scale balanced ? If not , Can you explain that , please ?

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

Great! contest was very interesting! thanks to author

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

По задаче D, я не смог взломать решение за O(n3 / 6). Такое вроде не должно было проходить.

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

    А кто-нибудь решил её быстрее, чем за N^2logN?

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

      Ну логарифм вроде можно убрать. Но зачем?

      У вас логарифм от сортировки? Так она не нужна, можно просто пихать отрезки в какую-нибудь HashMap, чтобы находить кол-во отрезков, не совпадающих с данным.

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

    Там 4 секунды... Я такое решение сам у себя пробовал на C# — чуть чуть не укладывалось (5-6 сек было), так что на плюсах должно было пройти.

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

подскажите 5 тест на B, пожалуйста.

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

I have mistake in problem C :(

Problem D is classic, but I don't love geometry...

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

    I think D has less geometry than it seems to have.

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

      but how do figure out how many collinear sets we have ? after that it would be normal permutations and combinations.

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

      I didn't think about it a lot, but my solution have calculating coefficients , sortings and after that line sweep. Maybe I wrong ?

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

      D was also a brute force.

      As time limit for D was 4sec.

      It's sad that very few noticed it. :(

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

        10^8 iterations per second, isn't it?

        Then 4*10^8 iterations in 4 seconds.

        I don't get how come D passed for many submissions! It takes 2000*2000*2000 iterations!

        May be CF is too fast.

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

          I was going to hack a O(n3), then thought of running simple addition 2000^3 times in custom invocation and it took .7s. I was like "brace yourself, something terrible is coming :|"
          10^8 iterations theory doesn't apply to CF

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

          roughly 4 *10^8 iterations are there in 1 sec

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

        D can be solved in n^2logn using some concepts of geometry. It would be a nice one if time limit would have been 2 sec. You can see my code here

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

          I tried the same way but was not able to solve in the contest :( I was missing the condition when slope if line was infinity.

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

two WA due to inbuilt gcc pow function:( in 308-B never using it again...

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

    Yea, I realize now that my 308B is wrong ;_;

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

    Same here, Don't understand why gcc pow function fails though ?

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

    same problem ....faced twice on codeforces

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

      pow gives output in double i tried to cast it to long long but there can be precision issues like the pow function giving 2^3 as 7.999999999999 and not 8 which on casting will give lesser answer.

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

    For some reason codeforces, which uses mingw (i think) is giving a bad answer with pow. Ideone gave right answer for the same code of mine. I feel it should not have to approximate since pow(integer) would return an integer in double form, which would not need any truncation.

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

    I know that feel bro.

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

    Try powl someday or use pow with nearbyint ...

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

Решение задачи Д был перебор всех треугольников? У меня на претесте 13 выдало превышение времени :(

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

    Нет. Давайте почитаем число плохих троек точек(точек, лежащих на одной прямой). Переберем одну из точек тройки и покидает в set направляющие векторов от этой точки до всех остальных. Пусть у нас x раз встретился некий вектор. Тогда уменьшим ответ на x(x-1)

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

Условия задач короткие — реальные задачи! Браво автору! Краткость — сестра таланта

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

I like so much problem C

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

How do you solve C ? Someone please explain the solution. Thanks :)

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

Is it OK nowadays to have "write a brute-force, it works in 3.7 while TL is 4" and "use Python to write it in 10 lines, it has built-in eval" as two hardest tasks of contest?

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

What was wrong with this approach for problem C? http://codeforces.net/contest/552/submission/11653548

I tried decomposing m into powers of w and if some power of W is W-1 times i put a weight of W-1 on that side . :(

Eg- if 20=3^2+3^2+3^0+3^0 Now 3^2 is 2 times and 3^0 is also two times,so adding 3^2 and 3^0 on side of 20 and 3^3 and 3^1 on other side would balance it,i also handled corner cases

EDIT:GOT AC.Used same concept but properly handled corner cases this time :)

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

I tested my D solution for the worst case and it ran fast enough

I wonder can O(n^3) pass ? hope it will

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

Use Math tags for all of the problems :D

Nice contest thanks:)

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

Could someone explain the solution for C ? Thanks :)

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

    wait for the editorial

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

    If m = 2, then solution always exist — it likes writing m in binary base.

    If m >= 3, find the first value of n that w^(n-2)*(w-1) > m. With m = 3, n = 18 and as m goes greater, n goes smaller. So, an O(3^n) brute-forces (considering each scales to be on the same pan with the object, different pan with the object or outside the pan) with properly branch-bound should be fast enough to get AC.

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

    The answer is "YES" if it is possible to add another number that only contains 0s and 1s (in base w) to m such that the resulting sum only contains 0s and 1s as well. Just use the algorithm for naive sum, if the sum at the current digit is w — 1 set carry = 1, if the sum at the current digit is 1 set carry = 0, if sum at the current digit is different than 0 return "NO" .

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

    our m needs to satisfy m = a_100*(w^100)+ .... a_0*(w^0),where a_100..a_0 are -1,0,1 we just test if m satisfies this

    http://codeforces.net/contest/552/submission/11642323

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

    Write m in base w. let b[i] be the i'th least significant number in the representation m in base w.

    Loop over m (in base w) from right to left (from least significant to most significant).

    Then if b[i] is 1, we can match it using (w^i). if b[i] is w - 1 then we can add w^i to the balance side of m. Then the representation of m becomes such that b[i] = 0 and b[i + 1] = b[i + 1]+1. so we increase b[i + 1] by 1.

    Notice this could lead to have b[i + 1] equals to w in this case we should repeat the last case on b[i + 1] (i.e increase b[i + 2] by 1 and make b[i + 1] = 0).

    the last case if b[i] > 1 and b[i] != w — 1 and b[i] != w we cannot represent m.

    In contest I did not handle case where b[i] = w. But when i did (after contest) the solution passed all the cases) 11654584

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

    My solution was not brute force. You can convert m to base w. Then iterate from least significant digit to most significant digit. If a digit d[i] =0 or d[i] = 1 then skip it (w^i is either skipped or added to the set). If d[i]==w-1 or d[i]==w, then subtract w from it, and add 1 to the next higher value bit (d[i+1]+=1). d[i] will become either 0 or -1 (w^i is skipped or added to the other set). This works because subtracting w from a digit is equivalent to adding 1 to the next higher digit. If d[i] is anything else, then it is not possible. complexity: O(logw(m))

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

I’m so weak.QAQ

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

I thought C was about DP by assigning -1,0,1 weight to each power of 'w' to get 'm'. But then i realized, (10^9)^100 is impossible to calculate by the methods I know :( .

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

    I had the same idea! Also had no idea how to implement it. Although I believe that there's a O(1) solution. If that's true — can somebody give a hint? Thanks in advance.

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

      Like, exploiting some properties of 'm'... but I couldn't think of any.

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

      I took advantage that you won't ever need a power bigger than 10^9, so you can just compute the biggest power of m which is lower than that number, and do it your way.

      I did it recursive by brute force using that, taking into account that if w^k > m, you don't need w^(k + 1), because the sum of all the powers of w below w^k is less than w^k.

      Hope I made myself clear, sometimes I find it difficult to explain these things :P

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

    We have to find a solution to this equation: m=a0+a1*(w)+a2*(w^2)+...+a100*(w^100), where -1<=ai<=1 and ai is integer If w=2, then it is always possible, because every number have a binary representation. Let's calculate a0 when w>=3: m-a0=a1*(w)+a2*(w^2)+...+a100*(w^100) Note that m-a0 must be a multiple of w, moreover (m-1)%w != m%w != (m+1)%w. So there are just one possibility for a0. After calculating a0, we can divide both terms by w and repeat the process;

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

    You don't know python 11645160

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

Top 5 Filled with unrated users

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

Good set of problems. Thank you author :)

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

For Problem D,

Is the approach of total triangles(nc3)-triangles formed by collinear points(found using overlapping straight lines,ie,slopes) wrong? I was getting wa on 4th test case. here is my code http://ideone.com/k8J9Zu

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

Контест мне понравился

НЕ ОЧЕНЬ.

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

I just saw the 4 seconds time limit for problem D, now I think it should be B instead.

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

OMG very very Good problems

I love (short problem & good problem) that this problems are short and good so I love this problems so I love this contest so I'm crazy

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

C and D have the same number of accepted submissions.

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

Nice Contest , also with strong pretest cases.

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

If the N^3 complexity for the Problem D Passed, How It Can Be D??

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

why gnu inbuilt pow function fails?

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

как то не серьезно что в D проходит тупой перебор

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

    У меня (n^2)*log(n^2) не проходило, ну там конечно map.

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

      ТУПОЙ ПЕРЕБОР, КАРЛ! 11650147

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

        Вполне нормально по сути: 2000^3/6 * const = 1.3 * 10^9 * const оперцаии, const = 2 операции умножении и 4 операции разницы. Запросто уложится в 4 секунды.

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

Is a O(n3) solution worth 2000 points? Seriously?

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

For Problem D,

Is the approach of total triangles(nc3)-triangles formed by collinear points(found using overlapping straight lines,ie,equal slopes) wrong? I was getting wa on 4th test case. here is my code http://codeforces.net/contest/552/submission/11654496

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

Are you serious?

And it occured to nobody that some guys could write such solutions?

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

hey guys...in Problem B...Vanya and Books... it shown in test-6 my answer is wrong..for n=1000000 the result is 5888895 and the correct answer is 5888896 but when i run my code in terminal(g++) the output is 5888896.I used GNU C++ to submit. My Code: http://codeforces.net/contest/552/submission/11650994 Why this is happening?

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

    My guess is that it is due to different casting behaviors.

    If you cast pow(10,count-1) to long long int immediately, you will get AC.

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

My C Solution: http://codeforces.net/contest/552/submission/11647965 So basically, if we look at everything mod w, the only weight that matters is one, because everything else is zero. So if there is a way to get this to work, we can change the current weight and divide by w. Recursively, this gives the correct answer.

Surprised at high number of TLE's, I guess..

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

Just want to clarify for problem C,

we have to put weight(s) on both sides, right? If so, I'm curious that for a case that M = 1, W = 3, it's impossible to do so; however, we're still able to balance the pans by putting the weight on only one side, that is, put w^0 on the other pan.

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

B solution 11647913... why not.

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

Hi all.

552E - Vanya and Brackets

Could anyone explain the following judge?

Input 9*8+7*6+5*4+3*2+1 Participant's output 837 Jury's answer 1987 Checker comment wrong answer 1st numbers differ — expected: '1987', found: '837'

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

Is this logic correct for E: you will place bracket between * and * and if only 1 * then the bracket is either on left or right of it. So precalculating using DP= t= |s|^2.Total time=t + k^2, where k=number of * in expression(<=15).

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

I liked your contest not just because of the good problems but also because of fast rating change.(I got specialist though)

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

accepted solutions of problem D should be rejudged with stricter time limit so that O(n^3) solution timeout. Then only standings will become fairer.

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

pow()... :-|

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

I have a question guys. My code for problem B: 11655174 seems to return 99 when calling pow(10ll,2).
I notice this does the same on my mingw, but returns 100 correctly on g++ and ideone. Is there any reason for this?

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

Check ur new rating. Really fast.

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

Check ur new rating. Really fast rating.

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

Лол. Тесты #1 и #11 в задаче B совпадают.

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

Image and video hosting by TinyPic

Nice!!!

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

I read E outputs and there where all integers i taught i should use bignum and didn't solve it you should have garenteed that the answer is int or long long

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

Yay, finally in Div 1.

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

For ProblemB 'Vanya and Books' my answer is not 'Accepted' with the message saying "wrong answer on test 18'. But when I re-run the same code it gives me correct output. Don't know how the program gave an invalid output out of the blue. My Submission

Am sort of new to Codeforces, my apologies if this is not the correct place to put forth such queries.

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

    Your code is awesome, but you forgot one thing. You have taken all necessary variables in long long int but n!

    Your code works fine up to 8-digit. Even works for some 9-digit numbers too. But fails for large 9-digit numbers. Why? because, you need to do multiplication in long long.

    For 9-digit and 10-digit number, re-think about the lines: res += (n-99999999) * 9; and res += (n-999999999) * 10; respectively.

    Say, n = 999999999. Then what would be the calculation of (n-99999999) * 9 portion?

    = (999999999-99999999) * 9

    = (900000000) * 9

    = 8100000000 which is a 10-digit number and could not fit in long int.

    So, change the line long int n = 0; into long long int n = 0; and get Accepted!

    Another thing I have noticed in your code that you have used the same variable n as local and global at the same time. It is a bad practice for programming contest. Sometimes, it could massacre your contest!

    Thanks and sorry for my bad English as well as bad explanation. Happy Coding!

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

In case anyone is interested there is a way to solve problem C trivially without a computer if you are given the base w expression of n. My solution uses this approach, it runs really fast, you don't need to calculate anything, you just need to read the base w expression.

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

In problem B,my solution is working fine for a particular output on my system but its giving a different output when i submit the same solution.This was my submission 11656471 Is it because i am using long long int and lld specifier? In which cases does the online compiler might behave differently than my local system?Thanks

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

    It is for your (long long int)pow(10,(double)x). Be careful to use pow function. It is very dangerous! It calculates in double, so precision error occurs. Just handle it manually. Thanks in advance.

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

my solution of second at 5th test case is giving ryt answer in all other compilere like ideone etc....herein code force compiler it is giving wrong answer.....how is it even possible

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

Why liyankui was skipped?

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

为什么liyankui会skipped? 有老司机出来解释下嘛?

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

5道题目代码风格完全一样 还TM封号??? 给我一个liyankui作弊的理由! 题目太简单怪liyankui咯?

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

题目太简单都是liyankui的锅!

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

5道程序代码风格完全一样,程序没有雷同。凭什么skipped? 哦你可能说有5个人同时在做,妈的做这种sb题liyankui需要开挂?

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

随随便便就封号? 封你mb! why are you so diao?

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

我喷你了这么多,是不是也该把我封了啊? 哦对你是毛子看不懂中文哦! 我推荐用有道翻译!

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

Awesome contest !!! C and D were good but O(n^3) wasn't fair !!
finally div1 !!!
P.S:- Very Happy

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

I'm so sorry for my behavior just now ..

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

Hello, Div.1!!! Looking forward to the next round!

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

Whats the mathematical principle for problem C? I have seen some solutions they are operating on m (decrementing and incrementing according to divisibility by w which so conveniently uses powers of w only once) but cant seem to figure out how they came up with the solution e.g.11657140

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

    I don't know how that solution specifically works. But I notices that the base w representation of n can only have the following digits:

    0 (this can appear without any restriction)

    1 (this can appear only if the digit to the right is 0 or 1)

    w-1 (this can appear without restriction)

    w-2 (this can appear only if the digit to the right is (w-1 or w-2)

    Just read the base w representation and check if all the digits are as mentioned above.

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

Still waiting for tutorial....

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

Where is tutorial?!

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

question about problem D: can anybody explain why my O(n^3/6) solution was not accepted? here is the code 11645613

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

    You need to optimize your code for a brute force approach.

    You can get rid of the if statement in the inner loop by starting j = i+1 and k = j+1. Also move the x1, y1 computation one level higher so that it will not be recomputed for every k.

    It passes then 11670552

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

Editorial, please -

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

Мне кажется, или немного странно, что второе и треть место заняли люди с такими никами?

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

Can someone help me with my question B submission, its running fine on online compilers ? Here is the link: http://codeforces.net/contest/552/submission/11640318 Edit : Got it after reading the editorial !

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

http://codeforces.net/contest/552/problem/C

никак не могу понять алгоритм решения задачи С, помогите пожалуйста, смотрел правильные решения, но всё равно не понял

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

    1) Любое число представимо единственным образом как сумма степеней w-шек.

    2) Нам никогда не понадобится использовать гири, весом больше чем wlogw(109) + 1, для w ≥ 3. Ибо представим, что существует ответ и там есть гиря максимального веса (пусть на левой стороне), которая  ≥  чем ограничение выше. Тогда утверждается, что на правой стороне мы никак не сможем набрать столько же. Ибо там все гири весом меньше, а это легко доказать что . Причём разница между левой и правой частью будет больше чем 109, поэтому на какую сторону не добавь m, равенства всё равно не будет.

    3) Ну и всё. Получили решение. Для двойки yes. Для остальных: посчитаем какой вес, какой маске соотвествует. Это в худшем случае займёт 220. Потом будем ставить на ту сторону где m, различные наборы гирь (маски), и пробуем положить на правую сторону столько же массы. Если получается это сделать двумя различными наборами гирь, то ок.

    Мб излишне сложно, но как есть:)

    http://codeforces.net/contest/552/submission/11643866

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

Can somebody please elaborate the Problem C editorial? Whats the concept behind the solution. Why the number m needs to be converted to base w.

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

    OK I'll try . — we need to find if solution to equation M=w^0*a0 +w^1* a1 + w^2*a2.... Exist or not . This equation is equal to M-w^0*a0 =w^1 *a1 + w^2*a2.... Rhs has a common factor of w so lhs should be divisible by w . a0 can have 3 values -1 ,0,1 We try all cases of a0 and check if Lhs formed is divisible or not. Since w^0 is 1 we have m-1 , m+1, m. If any of the three is divisible my w. That would be new value of m. And equation now becomes m'= w^0 * a1 + w^1 *a2.... Which is solved similarly untill we reach a point such that m,m+1,m-1 is not divisible by w by m( answer doesn't exist) becomes 1 (possible)

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

    where are the editorials of the problems ?

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

wow, all top 5 winners had their first contest, kinda neat :)

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

uw_ttocs

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

uw_ttocs

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

Can you give me an editorial, Wild_Hamster?