antontrygubO_o's blog

Codeforces Round #580
By antontrygubO_o, 5 years 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, 244mhq, gepardo, danya.smelskiy, reeWorld, Xellos, Mediocrity, I_love_tigersugar, 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. Rewinding

Div 2:

1. kkkkk11

2. sucuk

3. ujrepacul

4. zzffxx

5. VahitGuetta

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

Comments Comments (184)
| Write comment?
»
5 years 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?

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

    0.5

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

    drstrange1 i know it

    → Reply
  • »
    »
    5 years 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?

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years 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)

→ Reply
»
5 years 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 :)

→ Reply
»
5 years 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)

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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!

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      Thank you for your kindness.

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

    That's ABC 138, not 038.

    → Reply
»
5 years 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

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it -35 Vote: I do not like it

    。。。

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

    You will not get it

    → Reply
    • »
      »
      »
      5 years 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~

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

        No he will lose -100 delta in this Contest

        → Reply
        • »
          »
          »
          »
          »
          5 years 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~

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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 RedLycoris's rating can be greater than mine!

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

              wish zrmpaul become international grand pupil

              → Reply
  • »
    »
    5 years 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, RedLycoris may become purple if he has a try. And also it's really mean of them to say such words.

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

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

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

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

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

    Good job!

    → Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Div 1 orz

→ Reply
»
5 years 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:)

→ Reply
»
5 years 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. :)

→ Reply
»
5 years 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

→ Reply
»
5 years 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

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +3 Vote: I do not like it

i hope i can do well, good luck for all

→ Reply
»
5 years ago, # |
  Vote: I like it +10 Vote: I do not like it

three consecutive contest for me today :)

→ Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
»
5 years ago, # |
  Vote: I like it -33 Vote: I do not like it

I am late to comment this time.

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

That 10 minutes can be lifesaver :)

→ Reply
»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I hope the problem statements are short and clear.

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Guys check this out: https://codeforces.me/blog/entry/68888

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

GOOD LUCK

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

Huge waiting times! please look into it.

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Long queue time anyone?

→ Reply
»
5 years ago, # |
  Vote: I like it +17 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Two consecutive Queueforces. :(

→ Reply
»
5 years 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?

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

    try writing a comment and then submit

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys, when would good tests appear?)

→ Reply
  • »
    »
    5 years 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...

    → Reply
»
5 years 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

????

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Speedforces I miss the days when C was an interesting problem

→ Reply
»
5 years 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

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Mathforces?

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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?

    → Reply
  • »
    »
    5 years 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).

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

How to solve D?

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Hey guys, how did you solve Div 2 D?

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +22 Vote: I do not like it

      Why downvotes? It's pretty correct solution.

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

[Delete]

→ Reply
»
5 years 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.me/contest/1206/submission/59044914

Can anybody please share his / her approach?

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

    If there exist three number with common bit you got the answer. Else build the graph which contains only few edges. Find shortest cycle in it.

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

      How do you know which edges to include?

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

        Which have a common bit in them. And bits are just 18*log(10)/log(2).

        → Reply
»
5 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Nice zeroes in D.

→ Reply
»
5 years 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 ?

→ Reply
»
5 years 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?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Welcome to Speedforces!!

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

The queue is dead, long live the queue!

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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)

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Please ignore

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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?

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Mathforces，Guessforces（

→ Reply
»
5 years 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!

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +86 Vote: I do not like it

Editorial is published!

→ Reply
»
5 years 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

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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

→ Reply
»
5 years 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 :)

→ Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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)

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

    → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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?

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

        Its all due order of adj vertexes.

        → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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 - 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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 - Down or Right.

      → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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 :)

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
  • »
    »
    5 years 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

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

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

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

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

        → Reply
  • »
    »
    5 years 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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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();

    → Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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.......

        → Reply
        • »
          »
          »
          »
          »
          5 years 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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              5 years 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.

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

                no problem, happy to help :)

                → Reply
      • »
        »
        »
        »
        5 years 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)

        → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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.. :(

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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

→ Reply
»
5 years 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！

→ Reply
»
5 years 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 ...

→ Reply
  • »
    »
    5 years 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

    → Reply