antontrygubO_o's blog

By antontrygubO_o, 5 weeks ago, translation, In English,

Hello again, Codeforces!

I am glad to invite you to Codeforces Round 580, which will take place on Aug/18/2019 16:45 (Moscow time). Round will be rated for both divisions.

All problems in this round were created and prepared by me, antontrygubO_o. I tried to make them interesting and hope that you will enjoy them!

A lot of thanks to arsijo for the excellent coordination of the round, kefaa2, gepardo, danya.smelskiy, re_eVVorld, Xellos, GandalfTheGrey, prof.PVH, KAN for the testing and valuable comments, and to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon.

Participants in each division will be offered 6 problems and 2 hours 10 minutes to solve them. As usual, I strongly recommend reading statements of all problems!

I wish you good luck and high rating!

UPD1:

Scoring distribution of Div $$$2$$$ round: 500 — 1000 — 1500 — 1750 — 2250 — 3000

Scoring distribution of Div $$$1$$$ round: 500 — 750 — 1250 — 2000 — 2500 — 3000

UPD2:Editorial

UPD3 Congrats to winners!

Div 1:

1. TLE

2. Um_nik

3. mnbvmar

4. Benq

5. CauchySheep

Div 2:

1. kkkkk11

2. sucuk

3. ujrepacul

4. zzffxx

5. Illicit

 
 
 
 
  • Vote: I like it
  • +1343
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it +134 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +26 Vote: I do not like it

    0.5

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    drstrange1 i know it

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +80 Vote: I do not like it

    What chance that problem on a heavy cycle flow centroid decomposition on bitsets will appear in the contest?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      If you decide to submit some of that, it will definitely appear in the contest.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -18 Vote: I do not like it

      See.. This is the type of question that drives an innocent ass Titan down the path of Thanos

»
5 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +308 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +52 Vote: I do not like it

      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 weeks ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Thank you for your kindness.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    That's ABC 138, not 038.

»
5 weeks ago, # |
  Vote: I like it +37 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +38 Vote: I do not like it

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 weeks ago, # ^ |
    Rev. 2   Vote: I like it -35 Vote: I do not like it

    。。。

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Why not? You can have a try!!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -34 Vote: I do not like it

    You will not get it

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      hello,

      do not discouraging any others from candidate masters,, this person has a greatest chance at a candidate master,

      generally a rule if u wish other persons to get a highest ratings as possible,, then u will also be high rating,

      wish u high rating, u can do it, rajeshwar~

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it -17 Vote: I do not like it

        No he will lose -100 delta in this Contest

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          losing -100 deltaa, is that what you say,,

          yes that is, u have the lost -100 delta, but that is mean in it that he will gain! 100 delta,,

          this is type of thinking u must have, not about the "he will fail" because if u think he will fail u might also have a fail,,,,,

          therefore, you must wish a high rating, like i wish u and all other contestants to this round,,,,

          wish u high rating,,

          rajeshwar~

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it +15 Vote: I do not like it

            there's no need of arguing with those people who are always expecting others to lose rating and stuff.

            And also wish zrmpaul's rating can be greater than mine!

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it +8 Vote: I do not like it

              wish zrmpaul become international grand pupil

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +22 Vote: I do not like it

    Those people who says things like "you won't" and stuff are really annoying, zrmpaul may become purple if he has a try. And also it's really mean of them to say such words.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

    Just imagine having a zero change. This will be legendary!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    good luck :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    congrats...give me some good luck also for becoming an expert...

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Congrats..!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Good job!

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -54 Vote: I do not like it

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

BestMotivation.

»
5 weeks ago, # |
  Vote: I like it +25 Vote: I do not like it

Div 1 orz

»
5 weeks ago, # |
  Vote: I like it +27 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +43 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I wish to have the same spirit for a long time :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 7   Vote: I like it +11 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 3   Vote: I like it +3 Vote: I do not like it

i hope i can do well, good luck for all

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

three consecutive contest for me today :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it -33 Vote: I do not like it

I am late to comment this time.

»
5 weeks ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I worked all Day in constructions thinking about this contest. Hope it will worth.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

That 10 minutes can be lifesaver :)

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Ten minutes == (this->score += abs(y) && this.rating.delta += abs(x)) :)

»
5 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope the problem statements are short and clear.

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it
»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

GOOD LUCK

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Huge waiting times! please look into it.

»
5 weeks ago, # |
  Vote: I like it +19 Vote: I do not like it

Long queue time anyone?

»
5 weeks ago, # |
  Vote: I like it +17 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Two consecutive Queueforces. :(

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    try writing a comment and then submit

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        try changing the name of a variable

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          It doesn't work too. The system always prints the same message even I submit "Hello, world". I hope it will not be reflected in my rating....

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, when would good tests appear?)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +37 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Speedforces I miss the days when C was an interesting problem

»
5 weeks ago, # |
Rev. 2   Vote: I like it +19 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Mathforces?

»
5 weeks ago, # |
  Vote: I like it +10 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +52 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +7 Vote: I do not like it

Hey guys, how did you solve Div 2 D?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +15 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Why downvotes? It's pretty correct solution.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. But can anyone please explain the bit part I have no idea of binary represntation or bit may be thats why I didnt understand the solution. Can anyone please explain it easily from scratch. Sorry for my poor english. Thanks a lot :)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    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 weeks ago, # |
Rev. 5   Vote: I like it 0 Vote: I do not like it

[Delete]

»
5 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice zeroes in D.

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Welcome to Speedforces!!

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    $$$a_i = a_{n+i} \pm 1$$$

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it +8 Vote: I do not like it

    Think about it as a window of length n. In one turn a number enter and a number leaves. Alternate the difference = number enter — number leaves between 1 and -1, you can find then when the condition will be impossible.

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

The queue is dead, long live the queue!

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The queue is feeble during the contest. And now it's gone. R.I.P

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Please ignore

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

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

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it
    if (n < 500) {
        gate();
        return 0;
      }
      puts("3");
    

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

»
5 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

Mathforces,Guessforces(

»
5 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +104 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +86 Vote: I do not like it

Editorial is published!

»
5 weeks ago, # |
  Vote: I like it +22 Vote: I do not like it

Really intriguing contest.

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

»
5 weeks ago, # |
  Vote: I like it +47 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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

»
5 weeks ago, # |
Rev. 2   Vote: I like it +32 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it +64 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    you need to clear "vis" before every dfs, i had the same problem

  • »
    »
    5 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Using DFS to search for shortest cycle in a graph doesn't work. Consider this graph: 1-2, 2-3, 2-4, 4-5, 5-6, 6-1, 6-3

    Say you start your dfs from 1 and it traverses like this:- 1->2->4->5->6->3

    Back-edges found are 6-1 and 3-1, both of which give longer cycle length.

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      But dfs is done from all the vertices So it should find the smallest cycle.Right?

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Its all due order of adj vertexes.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        With enough bad luck, your order of vertices in adj list could be such that dfs can't find shortest cycle starting from any node.

»
5 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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 - Палиндромные пути. 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 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 - Вправо или вниз.

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 weeks ago, # ^ |
    Rev. 5   Vote: I like it +1 Vote: I do not like it

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

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      but he's saying 1<<j not 4<<j to get overflow

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        my bad, didn't notice, that thought it was not i << j

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe :)

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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 weeks ago, # ^ |
        Rev. 2   Vote: I like it +1 Vote: I do not like it

        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 weeks ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          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 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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 weeks ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              I completely got what you said.Thanks for helping out so much and being so patient.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                no problem, happy to help :)

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    For problem D,you can use floyd or tarjan to find the minmum circle

»
5 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

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 weeks ago, # |
  Vote: I like it +24 Vote: I do not like it

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 weeks ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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 weeks ago, # ^ |
    Rev. 2   Vote: I like it +25 Vote: I do not like it

    Grids

    101

    011

    111

    and

    111

    110

    101

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
4 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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 ...

  • »
    »
    4 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If at least one of all the paths is palindromic, you will get 1, otherwise you will get 0