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

Автор antontrygubO_o, 5 лет назад, По-русски

И снова привет, Codeforces!

Я рад пригласить вас на Codeforces Round 580, который состоится в 18.08.2019 16:45 (Московское время). Раунд будет рейтинговым для обоих дивизионов.

Все задачи в этом раунде придуманы и подготовлены мной, antontrygubO_o. Я постарался сделать их идейными и очень надеюсь, что они вам понравятся!

Спасибо arsijo за отличное координирование раунда, 244mhq, gepardo, danya.smelskiy, reeWorld, Xellos, Mediocrity, I_love_tigersugar, KAN за тестирование и ценные замечания, а также Михаилу MikeMirzayanov Мирзаянову за отличные платформы Codeforces и Polygon.

В каждом дивизионе будет предложено 6 задач и 2 часа 10 минут на их решение. Как всегда, настоятельно рекомендую прочитать условия всех задач.

Всем удачи и высокого рейтинга!

UPD1:

Разбалловка Div $$$2$$$ раунда: 500 — 1000 — 1500 — 1750 — 2250 — 3000

Разбалловка Div $$$1$$$ раунда: 500 — 750 — 1250 — 2000 — 2500 — 3000

UPD2: Разбор

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

Div 1:

1. TLE

2. Um_nik

3. mnbvmar

4. Benq

5. Rewinding

Div 2:

1. kkkkk11

2. sucuk

3. ujrepacul

4. zzffxx

5. VahitGuetta

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

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

What are my chances of becoming a legendary newbie candidate after this contest?

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

What to do a Sunday evening, take a walk with friends or write a contest from antontrygubO_o? Of course I will write a contest from antontrygubO_o)

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

Больше никаких доминошек? :)

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

When you are waiting for the contest on codeforces and suddenly codeforces announced there will be a contest :)

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

идейными

IQ тест

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

    Кстати, а почему в английском версии нет этого слова?

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

Unfortunately, the Atcoder Beginner Contest 138 conflicts with this for 5 minutes. Is it possible to shorten the ABC or shift this contest by 10 minutes? (Mentioning chokudai for the ABC)

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

    We decided to do the following:

    • The contest will be shifted by 10 minutes.

    • The contest length will be 2 hours and 10 minutes.

    Therefore, there are 5 minutes between ABC and CF and other 5 minutes between CF and Cook-Off.

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

      Thanks! I know it's hard scheduling with contests on different platforms. I appreciate all the hard work you and the CF team do!

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

      Thank you for your kindness.

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

    That's ABC 138, not 038.

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

Usually I keep my vote after the contest is over, but for this one I will give you my up-vote now just for the lovely image <3

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

Good luck to all of you!

Btw,wish I can become a candidate master.

What I need is only +1 rating.

I think I can achieve that:D

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

Hope I can become a master after this contest even if the probability is so small.

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

Spiderman: Wherever I go, I see Iron Man. Me: Wherever I go, I see tourist.

BestMotivation.

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

Админ, где мемы

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

Div 1 orz

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

First div 1 Round for me and hope the result won't be bad:)

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

Every time I see a Division 1 contest I get excited about it and participate in it and end up in Division 2. But that does not stop me from participating again. :)

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

Every time I see a Division 1 contest, I get excited about it, participate in it and end up in Division 2. But that does not stop me from participating in Division 1 again. :)

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

thank you so much <3

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

Wow, I didn't know you created rounds too! Will participate using your vscode extension for sure

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

Participants attending the contest at 23:45PM https://i.imgur.com/KxJ7aAI.gif

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

i hope i can do well, good luck for all

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

three consecutive contest for me today :)

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

    I find it really hard to focus for that long. I've tried doing two contests in a day before and that didn't end well; this is just crazy :o

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

      i once did 2 consecutive before, and my performance in second was better than usual . So i am gonna try three tonight XD

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

I am late to comment this time.

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

Well!This contest started early (relative to most other contest). I think I will have better energy to solve the problems in this contest.

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

That 10 minutes can be lifesaver :)

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

I hope the problem statements are short and clear.

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

Programming Final tomorrow! ^_^ Probably my last contest:)))

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

I hope the problem statements are short and clear.

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

GOOD LUCK

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

Participating in a contest after nearly 50 days. Hope this goes well!!!

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

Huge waiting times! please look into it.

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

Long queue time anyone?

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

Another $$$Queueforces$$$ Round!! :(

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

К сожалению, после дополнительной регистрации не могу сдать ни одну задачу. При попытке посылки задачи (любой) всплывает сообщение "Ранее вы отсылали абсолютно такой же код".

P.S. Хочется чтобы в таком случае для меня контест не учитывался в рейтинге

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

    Ну фактически же ни одной посылки не совершилось? Тогда априори не будет никаких изменений в рейтинге.

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

      Хм, не знал про эту особенность.

      Если так то здорово, спасибо!

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

Two consecutive Queueforces. :(

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

I can't submit any answer. When I'm trying to submit, the web page say "You have submitted exactly the same code before". How can I solve this problem?

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

    try writing a comment and then submit

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

      It doesn't work. It is not allowing me to submit even my first attempt. It is always showing "You have submitted exactly the same code before", but there is no submission in queue.

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

Guys, when would good tests appear?)

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

    yes, A contest with good problems on algorithm and datastructure with less/NO guess work or pattern finding stuff...

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

Could this round unrated or semi-rated?

I tried to solve div1C,and I succeed

But then,the problem changed,and I got WA on test 1

????

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

    Actually it is a problem, but not a really serious one which can make the round semi-rated.

    It is solved after 6 minutes the contest starts.

    and not many people was doing C that time.

    By the way, actually it doesn't waste much time. Isn't it? :P

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

Speedforces I miss the days when C was an interesting problem

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

Absolutely love the feeling when I have to wait for 3 minutes in queue just to receive the verdict, wrong answer on test 1

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

I am waiting for Julia to be supported to compete in these rounds.

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

Mathforces?

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

OMG...that didn't went well. How can everybody solve C and I do not see how?

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

    I think because there exists cheating cases in rounds and this problem was like find pattern and get AC. Can anyone prove it with math or etc?

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

    I wrote a brute force that worked in n*((2*n)!), and found a pattern (Only used cases n<=5).

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

How to solve D?

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

    The idea is the same as

    Problem Source, Spoiler Warning

    First, we solve for star graph. Choose a constant $$$C$$$ in the range [N/3, N/2], then assign edge weights 1, 2, ..., C and (C+1), 2(C+1), ..., (N-1-C)(C+1).

    How to solve for general graph? Root the tree at centroid. We claim that there exist a subset of children of the centroid so that their subtree sizes sum up to [N/3, 2N/3]. If one of the direct child of centroid has subtree size >= N/3, we're done. Otherwise, keep adding subtrees until the sum is >= N/3. Since each subtree size < N/3, total sum does not exist 2N/3.

    Now, we use the same idea as star graph within these two sets and we're done.

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

Hey guys, how did you solve Div 2 D?

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

    Let's ignore all vertexes with $$$a_i = 0$$$ because they never be in any cycle. So if there left more than something (I don't know exactly how many, choosed 500) that answer is 3. If there less vertexes then you can run $$$n$$$ bfs'es to find shortest cycle.

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

      Why downvotes? It's pretty correct solution.

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

        Yeah, I solved it this way — by limiting number of vertices (and I think 120 is enough).

        Maybe the downvotes are from people who had the idea to limit the number of edges (like in the editorial) and think this is wrong.

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

    The approach is simple compute for each bit i from 0 to 64, which all numbers have the i th bit set. Then if any of bit i have less than 2 numbers with that bit set, it will not affect and will not result to any connection. Otherwise if any of bit i have more than 2 elements, then the answer will be 3 always(take any 3 elements among those).

    The case rises when we have bits with 2 entries. So maximum edges resulting from these bits will be 64. Considering these edges we can use out edge removal approach explained here :Find minimum weight cycle in an undirected graph

    If no cycle then answer will be -1.

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

[Delete]

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

How to solve Div2 D?

If I used a vector to store the connected nodes I would get MLE.

And after that I got TLE by searching in O(n) for the connected nodes :/

https://codeforces.com/contest/1206/submission/59044914

Can anybody please share his / her approach?

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

Nice zeroes in D.

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

is div 2 D based on that there will be max 18 edges ?

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

can someone please tell me why my solution for E got WA?

I tried on my terminal and it works fine I guess. Can someone please find the mistake?

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

Welcome to Speedforces!!

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

I think, question Div2-C has some patterns about numbers but I could not solve it :( Could you guys tell me, if you've already solved it?

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

The queue is dead, long live the queue!

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

Интерактивка без предупреждений незаконно.

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

    Для того чтобы уметь решать интерактивку, практически никаких предварительных специальных знаний не требуется (тем более, инструкция о вводе-выводе есть в самом задании).

    Почему заранее не объявляют, что есть задачи на дп, графы, деревья отрезков и проч.?

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

Can anyone figure out what is the meaning of n odd in div2 E?

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

    if n is even, then the problem is much easier! (try to think about it)

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

    Please ignore

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

      Why is this true? Don't both corner squares still have the same parity?

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

        Ah, you're right. I am misremembering stuff (I got pretests passed in last 10 seconds so adrenaline rush). My solution relies on the fact that there exists a 3x3 square in following pattern:

        patterns:
        1xx
        xxx
        xx0
        
        or
        
        0xx
        xxx
        xx1
        

        which is not necessarily true in even case, but true in odd case. Maybe that is author solution?

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

Div 2 D there these two pieces of code should be accepted :(

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится
    if (n < 500) {
        gate();
        return 0;
      }
      puts("3");
    

    Wrong. If there just 500 zeroes then answer is -1.

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

Mathforces,Guessforces(

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

Thank you so much for this contest! Although have not done my best but really enjoyed it. Love problem E!

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

An outstanding round! Enojyed all the problems, especially D. My screencast will appear here as soon as it's processed.

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

Editorial is published!

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

Really intriguing contest.

With the fact that I will get -108 rating for this contest, I still give it my up-vote

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

Why something like "Note that the graph does not contain parallel edges. Therefore, one edge can not be a cycle. A cycle should contain at least three distinct vertices." was accounced in B? It's clear that it has nothing to do with making statement clear since it is crystal clear in this matter, it's just a hint to the solution about supposedly popular bug.

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

Откуда так много + за раунд ? Нельзя называть раунд идейным, если все задачи на одну тему. Лично от меня — уважение antontrygubO_o.

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

    На какую тему все задачи?

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

      Конструктив + слабые претесы

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

        Не согласен, что претесты слабые.

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

          Ну давай посмотрим на решения див 1Б . Большое количество человек написало ДФС и получило ва 74 ( Хотя ДФС в корне неверное решение )

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

            Если только по одной из 8 задач упало ~15% решений, это не значит, что претесты во всех задачах слабые.

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

              А что это значит?

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

                Это значит, что претесты, в целом, хорошие.

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

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

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

Div2 D, E very good problems! Thanks for this round!

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

Thanks for extending this contest by 10 mins than usual. Finally, in last 30 seconds D1C got AC and I became master after a long wait :)

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

For those of you who get WA on test 14 for problem D on Div 2. You probably add some edges more than once.

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

For problem D of Division 2, I would like to point out to everyone the existence of this problem: Problem: Find the Length.

The problem asks you to calculate the length of the shortest cycle containing a given vertex. Furthermore, N, the number of nodes, is limited to only 300.

How to limit the number of nodes you ask? In our problem, N can be 200,000! Well, for any given a_i, its representation in binary can be no longer than 60 characters long (2^60 > 10^18), the problem limit. Store the binary representation of the N numbers in an array, of dimensions Nx60.

Now, we have two cases. If there are more than 2 ones in any single column of our 2D array, then it means that 3 or more numbers are all connected to one another. This means that the minimum cycle length is 3, so we can output 3 and end.

Otherwise, the graph is extremely sparse. If there are only 2 ones in 60 columns, it means that there are a maximum of 120 ones in the binary representation of 200,000 integers! An integer must have at least 1 one in its binary representation. This means that, in the worst case, N is at most 120!

At this point, problem D becomes identical to the other problem. Simply use BFS or Dijkstra's algorithm to solve the problem. The runtime will likely vary, but most runtimes on the reduced graph will pass.

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

    Note that the fact that a_i can equal zero can be a problem. Since 0 bitwise-AND with anything (including another 0) is 0, you can simply ignore that a_i.

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

Thanks to this contest, I learnt that depth first search doesn't generate all simple cycles of the graph(which maybe a common sense for lots of people, but wasn't for me)

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

    It implicitly does, you just need exponentially more time to actually find them.

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

Got WA on test case 28 in Div2D. Can anyone figure out the mistake ? Link

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

Loved the problems: less coding, more thinking. But I was confused by the phrase "It can be shown that the answer always exists" in 1205C - Palindromic Paths. It led me to thinking that the answer is not unique — but there is actually no condition that it has to satisfy, so it was not clear how is our output validated (as soon as it does not contradict with out queries).

I would phrase it like "Your set of queries should unambiguously determine all cells of the grid". Actually the first time I would appreciate something like "Vasya filled the grid with ones and zeroes, and you have to figure out the entire grid by asking him queries" :) Anyone had troubles with this or is it just me?

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

    When the goal is to print a correct solution in an interactive problem, there must be at most one correct solution.

    My solution, which was "find 2 possible grids, find a query where they give different answers", makes it clear that you can decide if there are 2 indistinguishable solutions or a unique one. That's a big benefit of this approach.

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

      True. My solution was exactly the same, it is just before the last step I started thinking: do I really need to choose between two? Probably I am just spoiled by no-brainer statements like in 1023E - Down or Right.

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

    Yes, I noted it as well that saying "It can be shown that the answer always exists" is a complete nonsense xD. Checker has some hidden board and answers some questions about it, such a statement makes no sense at all, it is not some constructive problem where answer satisfying some constraints may exist or not.

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

Could someone explain why am I getting an overflow error despite using long long which can store a number upto 10^18. This is my submission 59048621

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

    use: ll nw = 1ll<<j; 59052313 see, you passed TC5 by using 1ll :)

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

      Thanks for the help. Could you help me figure out the reason for the TLE. I think my code should pass given the constraints. Thanks in advance 59052813

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

    long long has limitation as well. usually it's 64 bits. and if you try to shift number 4 (which in binary form looks like 100) 63 times — then you'll get an overflow. docs

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

    Just remember, every time you use long long and want to write a number like 1 or 0 put an ll after it like 1ll or 0ll

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

Long queue(4-5 mins) during the contest is an upsetting thing :(

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

Could someone explain why I am getting TLE. I think my complexity is within limits. Thanks in advance. Here is my submission 59052813

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

    Because you use cin. Add the following lines: ios_base::sync_with_stdio(false); cin.tie(0); Or use scanf();

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

    because you wrote N^2. imagine a big TestCase where every number is the same and they're binery form is 1111.....111. in every DFS you look at all of them, even though you dont visit them. so N nodes visited in DFS, in which you look at all of the N other nodes to check them if you have visited or not, so N^2.

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

    there is a trick to this problem, don't want to spoil it, but imagine what would happen if you had 3 numbers who would share the same 1 bit an 100000 other nodes...... what would the answer be, and why? think :D

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

      Are you hinting towards the fact that the dfs should be performed in order of component size for faster execution, If yes, how would that improve the time complexity. I still feel it would remain the same, ans is the answer to your question 3?

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

        yes the answer is 3. so in your vector vals[64] for every i if(val[i].size>=3) the answer will be 3 either way. so in worst case every one of them will have size 2, it means in worst case you would have 128 nodes in total. so..... you could make and Adj_List for those 128 nodes, so you only have the nodes you need and their relations.......

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

          Yeah I just understood the trick.But I don't know why my code is failing at Test case 75, I find everything fine. 59054630

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

            i checked the TC. I suspected that dfs wouldn't work for this problem, I'm actually suprised it got to TC75 :D if you draw the TC, you'll see what the problem is. but for how to solve the problem use bfs, and use the fact that bfs visits every node in shortest time possible while the edges are the same size, dfs doesn't have this property, it just merely visits every node. if you check the TC, you'll understand what I'm saying..... good luck :D

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

        i did not mean that about dfs, i just meant you have made number of edges in total something like N^2...... so dfs turns to (N^2+N)

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

can someone tell me the name of algorithms that solve the contest question? I would like to study them

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

In problem C the judge is not printing -1 for more than n^2 queries... wasted so much time thinking i am getting wrong answer instead of qle.. :(

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

I wanna know whether the problem in Div.1 C has a solution when the element (1,1) isn't 1,element (n,n) isn't 0.For example,(1,1)=0,(n,n)=0.

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

    Consider the grid where it's all 0s or the grid where it's all 1s. You can't distinguish these via any queries.

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

    Grids

    101

    011

    111

    and

    111

    110

    101

    are undistinguishable So 1 in top left and 0 in bottom right were important.

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

I'm rk1 in Div2 untill D&F FST.now I'm nearly rk1000 TAT

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

Why i am rated? I registered for the div2 contest 10 minutes after the start of the game!

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

how we can know the path that we ask in Problem E (div 2) ?antontrygubO_o

like ? 1 1 3 3

path A : (1,1) , (1,2) , (1,3) , (2,3),(3,3)

path B : (1,1) , (2,1) , (3,1) , (3,2) , (3,1)

the rule for move is known as move to right or down and both follow rule

so which one is correct ? i read problem statement like 5 times and i didn't find anything guided me to know which one is correct ...

please help me ^^

and sorry for bad english ...