scanhex's blog

Codeforces Round #534
By scanhex, 6 years ago, In English

Hey everyone!

I'm glad to invite you to Codeforces Round 534 (Div. 1) and Codeforces Round 534 (Div. 2), they will start on Jan/22/2019 17:35 (Moscow time). The round will be rated for both divisions.

Problems were prepared by me, Ivan isaf27 Safonov, Denis altruist Anishchenko and Ildar 300iq Gaynullin. Thanks to Um_nik for testing and MikeMirzayanov for the great Codeforces and Polygon platforms.

You will be given five problems in each division and two hours to solve them.

UPD: Score distribution: Div1:500-1000-2000-3000-3500, Div2:500-1000-1500-2000-3000

UPD: Congratulations to the winners!

Div. 1:

  1. mnbvmar

  2. whzzt

  3. aid

  4. dotorya

  5. TLE

Div. 2:

  1. aequa

  2. RatingBooster_2

  3. ujerpacul

  4. Igor_Zakharov

  5. halohalo

UPD: Editorial

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

Comments Comments (221)
| Write comment?
»
6 years ago, # |
  Vote: I like it -133 Vote: I do not like it

First time seeing 0 comments in a codeforces round blog :p

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

    Maybe that's because you checked it right after it was created? Your comment is just an elaborate way of saying well known "First!"

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

Whoa!! What a short precise round announcement.Hope problem statements are like that too :p.

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

    Why it is always necessary to make such standard comments?

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -69 Vote: I do not like it

i'm really happy i became expert after the last contest.
now i really hope this one won't have the useless math involved. god, please don't mix these two things together. it doesn't make any sense.
let's hope for a decent problemset, everyone

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

"I'm glad to invite you to Codeforces Round #534 (Div. 1), which will be held on Tuesday ..... The round will be rated for both divisions."

Great, this time I can participate in Div1 without being in Div1 :).

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

    i'm pretty sure this would classify as cheating.

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

      Actually OP only invited for Div1 in his announcement but telling that it will be rated for both division, I am just taking it in a funny way.

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

        i have a higher rating than you therefore i am more intelligent than you.

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

          Honestly, it just seems that after you were blamed for creating fake account (and it's definitely a fake created just for trolling), you decided to write 1 contest to defend from those accusations in future.

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

Looks like the last three contests (including this) were written by first-time problemsetters.

A lot of people complained about the problems (as they always do, tbh) but I personally enjoy seeing some fresh faces among the problems setters; looking forward to the contest!

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

first!

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

codecmeme

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

Hope the problem statements will be as short as the blog.

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

MikeMirzayanov Could you please consider banning account ....................? Not only does he constantly write annoying, non-constructive comments, he also likes to intentionally offend other users. Examples are abundant. I don't have much knowledge on networking, but is it possible to find his internet gateway's IP and ban him from there? So he can't create other fake accounts.

Spoiler
→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

...

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

Sounds good..Hope the contest will be good as like as this announcement..

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

My mind says study for exams .. my heart says participate in cf rounds.

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

I have just eaten a whopper

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

Why am I unable to register on Div 2 right now? Will there be any late registration, if yes, how long after the contest starts ?

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

    10 min after start of contest for next 20 min

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

All the best to all

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

Unable to register for div 2.

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

    Registration closes 5 min before contest. Wait for late registration (10 min after start of contest)

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

    This is speedforces. If you still havent registered dont even bother giving this contest.

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

Problem C should be a little harder and problem D and E should be a little easier than today's for DIV 2 . Recently most of the DIV 2 contests have been unbalanced.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -13 Vote: I do not like it

comment.skip();

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

    No, it's actually good to have interactive problems, we will get used to it, but the difficulty should be not this hard for DIV 2. I personally have never solved an interactive problem here. But i think it is fun.

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

    if(problem.interactive()) binarySearch.learn();

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

      yeah, i agree with you, i tried to solve using binary search / using power of 2's but couldn't get the logic used.

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

Score distribution for Div2 should be 500-750-1000-5000-20000-100000.

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

Missed today's contest, due to internship :(

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

How to solve Div2-D/Div1-B?

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

    I guess we have to consider first 45 fibonacci numbers but then when we find between which two fib's is A I don't know how to find it

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

    First, find p such that 2p < a <  = 2(p + 1).
    "? 2^p 2^(p+1)" // At max 30 queries.
    Let x=2^(p+1).
    Binary search on (x/2,x]. // At max 30 queries.
    "? m x" // At max 30 queries.

    Take care of a = 1.

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

      Haha, the "take care of a = 1" part definitely was tricky. I managed to fix it about 30 seconds before the end of the contest, and the servers were a bit slow, and I only found out my solution was correct when the problems opened for practice..

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

    If you consider every (x, 2x) pair from x = 1 to x<=1e9, the answer would lie in the first pair where it will answer 'x'. This is because if a > 2x, it will always answer 'y'. This would take 29 queries.

    Let's call the first found segment (X, 2X). a would lie between X+1 and 2X. So, we can binary search with low = X+1 and high = 2X asking query (X, mid) in each iteration (If a is greater than mid, we will get 'y' otherwise 'x'). This would take 30 queries at max.

    Does anyone have a better solution by the way?

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

      How can we be sure that when we query (x,2x) There will be atleast a answer 'x' ??

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

Can someone explain what the hell is going on with pretest 1 to div1B, div2D?

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

    Well for B, implement stack, and if you erase character, it will be the value s[i] is same as top of stack.

    As for D implement log(n) answer, imagine you have some x and y (x<y). If answer is x then answer is in segment [x+1,y]. Then you can notice that incrementing by power of 2 (like (1,2);(2,4);(4,8);(8,16)..) you can find if answer lies between some of these segments. And special case is when a=1. At least that's how I wrote it out.

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

      I'm not asking about solution, I'm asking about pretest.

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

      I also think that sth was wrong with pretest results.

      I got a lot of TLE instead of WA(Too many queries).

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

What's wrong with this answer for D? I got like 20 idleness limit excedeed.. I flushed after every answer, what could be else?

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

Very weak test case in B. Even if you delete a single repetition in a traversal, you will pass the pretest. For eg — for string — abccba delete cc start again from i=0.

And to my suprise, I got an unsuccessful hacking attempt in that. (code: 48750680) He had used erase function (unknown complexity) and was using above described method.

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

    Got 4 unsuccessful hacks because of that. People who used std::erase() got it in ~750ms on the worst case(Palindrome of length = 10^5 using 'a' and 'b').

    Codeforces systems are fast, really fast :(

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

      I ran the .erase thing on custom invocation with my hack case. It ran in 600ms. The .substr submissions ran in 1.2s

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

        erase may be close to O(1) but still you will have more than 10^9 operations.

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

      However I got one Successful hacking. He too had used similar method. But he added characters to a string one by one. Seems erase function played its magic for many.

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

    A lot of N^2 solutions passed B. Compiler magic works wonders.

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

div2 D was a nice problem. how to solve it. I think something related to bits.

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

    Used binary search. Twice.

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

      can u explain a bit more , how bs will lead us to answer ?

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

        First,check if a==1(by asking"? 0 1").

        Now think about "? x y" when x < y ≤ 2x and you know x < a,if the reply is x,you can make sure that x < a <  = y,otherwise y < a.(since x < a,,if x < a ≤ y, and the reply is x)

        So you can ask "? 1 2","? 2 4","? 4 8"until the reply is x,now you can make sure that (i is the first number in "? x y").Now you can use binary search to find the exact a(i + 1 ≤ mid ≤ 2i,so you can check if a <  = mid by asking "? i mid").

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

Problem A was absolutely one of the worst problems i have ever read , not that it's not clear, it just wasn't even a problem.

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

Me after solving div2 A-B-C:

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

Problem D pretest 4? Whats wrong with bitmask dp solution?

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

Can Div2D be done with binary jumping?

I was exceeding the 60 question limit for some reason.

I was printing

(0, 1)

(1, 3)

(3, 7)

(7, 15)

Untill it returns x (it will once return x)

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

    a = 8

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

      For that I will get x in (7, 15)

      then I do reverse (7, 11) return x

      (7, 9) return x

      (7, 8) return x

      When jump size is 1 and return is x then x + 1 is answer

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

    Yes, but do it until (x,y) becomes y-x=1

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

    Yes, I got ac asking

    1 2

    2 4

    ...

    2x 2x + 1

    And if answer on query 2x 2x + 1 is x, then you should do binary search on [2x; 2x + 1].

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

      how will binary search work in 2^x and 2^(x+1)

      because it might increase then suddenly become 0 and then again increase?

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

      Cool, I came up with the idea of asking the power of 2 but missed the binary search. It's a huge pity for me indeed

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

      I did a similar thing here My submission can you help me where exactly I went wrong.

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

Using brute force (string::erase(i,i+2)) can easily accept DiV2B.

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

    Wont it time out because string erase is linear? I guess.

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

      It didn't ! Even it didnt timeout for the people who deleted single repetition in a single iteration. maybe codeforces upgraded its server(which do the testing) ;D and downgraded the servers running the site.

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

How to solve D? My solution works in something like 611·11, but it passed pretests in 1 second. Is there a faster solution? Or is there no test where the number of operations is close to my bound?

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

codeforces was a bit slow at times for me.

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

How to solve C?

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

    Let's run dfs. If number of leaves is at least k than we can find k cycles, otherwise we can find a path with length at least n / k.

    I didn't get AC, but I think it should work

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

    Build dfs tree from some vertex. If its depth is at least n / k then we found a path. Otherwise by pigeonhole principle tree has at least k leaves. Let's choose k leaves. Our tree is a dfs tree, so all edges not in the tree go from some vertex to its ancestor. Each degree is at least 3, so each leaf has 2 edges going up. Each of these edges forms a cycle. If both of these cycles have length divisible by 3, then we can build a cycle with both of these edges and its length will not be divisible by 3.

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

      What about the 10^6 total numbers printed requirement? Can't the cycles become very long like this?

      EDIT: obviously depth is at most n/k, so nevermind

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

        The depth is less than n / k, so we output k cycles of length less than n / k.

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

      I couldn't understand some things, how does pigeonhole principle tells us that tree with atmost n/k depth will have k leaves?

      Also, in case of no solution (-1), couldn't there be a path if we have taken the dfs tree from some other vertex? How do we prove there couldn't be another path even with any other vertex?

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

        Suppose T is a rooted tree with leaves. If the depth of any leaf is at most d. Then T has at most nodes.

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

      We don't even need k leaves. It should be enough to go through all vertices in decreasing order of depth, if a vertex was already in some cycle then ignore it, otherwise take a backlink from it. This way, the vertices for which we choose cycles are already representatives and we either cover the whole tree with less than k cycles (so one of them has to have length  ≥ n / k) or find at least k cycles.

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

      If both of these cycles have length divisible by 3, then we can build a cycle with both of these edges and its length will not be divisible by 3.

      Hm, can you explain why? Upd: Ah, nevermind, those back edges are guaranteed to go the ancestor, they can't be cross edges. So if depth of leave is x, and depths of those 2 vertices are y and z (let's assume y < z), length of cycles are 1 + x — y, 1 + x — z, 2 + z — y. If first two are divisible by 3, y — z also is => last cycle is not divisible by 3.

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

great contest except D which had some math and that's why me and a lot of other people couldn't do it. see? don't mix math and programming together.
don't math in here, it doesn't belong here

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

    don't cook soups with water, water doesn't belong in cooking, it's not that tasty

    → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +16 Vote: I do not like it

Div.2

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

    i see this kind of memes after every contest...

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

Should have warned the participants that there would be interactive problem : (

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

    Should have warned they upgraded their servers ;D

    → Reply
»
6 years ago, # |
← Rev. 6   Vote: I like it -25 Vote: I do not like it

I try to hack some submissions of Div2.B (O(n2)). After I got a sucessful hack, I found that some code using string::erase won't be hacked, even though the worst complexity is O(n2).

Such as this submission

So I push a question.

I got this.

UPD: maybe the reason is wrong, I just want to say some O(n^2) algorithm can pass it.

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

    mine actually got hacked with that time limit?

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

      Yes. Your code's worst complexity is O(n^2)

      But I don't know why I can't hack that which is similar to yours.

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

    The questioner should read How not to read problem statements — Um_nik.

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

      You should know that I didn't use BAD STATEMENTS

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

        You should know what types of question you are supposed to ask.

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

          I still think that question is very important.

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

    string::erase uses a __builtin_memmove function call (as defined in basic_string.h, char_traits.h), which is just a well optimized function. For example, check vincentgable.com/code/memcpy_memove_lab.c code which memmoves an array of size 4 million 100 times in 0.03s, so can do 1.4e10 operations in one second, which contradicts the standard rule of "1e9 operations in a second" but does not mean the answerer is wrong...

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

      But it traversals all the string n times.

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

        Yeah, and the whole string is of length n, which is about n2 operations, or 1010 in this case, which he just pointed out can be done in under a second with how well optimized std::memmove is.

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

Why I can't hack this solution on maxtest? Asymptotics of his solution is O(n^2). My test: ababab...(50k)aaaaaa...(50k). Every time it is still possible to remove something, it runs through the prefix of 50k elements. Total 50k * 25k * (erase)> = 1.25 kkk. Now I can not show that I sent such a test, because the link is not available to him.

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

    I think this gives worst case.

    char s[100000];
for(int i=0;i<50000;i++) {
    	int ii = i%26;
    	s[i]=(char)('a'+ii);
    	s[100000-1-i]=(char)('a'+ii);
}
    → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    erase doesn't probably shift all elements ahead of a deletion. And it gives much better than O(n)

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

How to do Div2D,Div1B,I'm so self closing orz orz orz

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

Can anyone tell me, what solution for Div2D is? I am sure that it is a kind of binary search, but I have no idea, how to use it here

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

    I couldn't pass pretest. I used the graph of x mod a. start with x = 1. x = 1, y =2. check if and y lie on the same bar i.e. x and y are less than a. keep doing this with x = 2, y = 4 then x = 4, y = 8... . The moment y reaches next bar, there are only two possible conditions: x%a = y%a or x%a > y%a ( I'm not sure about this one. I used graph to get this). In second case, if you go from x to y, then X%a first increases, becomes 0, again starts increasing. So apply binary search in this region to get the value at which X % a is 0 and this value of X is ans as you are at end of first bar. In first case, ans will be y — x. I don't know what's the mistake in it.

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

    Ask for {(0,1), (1,2), (2,4)... (x,2x)} until x % ans > 2x % ans, now you know x < ans < 2x. Binary search between x and 2x can do the rest.

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

I submit same code twice for second Question but on first submission it give wrong answer on Pretest case 10 but again on submitting same code all pretest passed.Unable to understand Why??

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

    codeforces system doesnt allow you to send same code as previous

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

      it means you changed something in code and then sent it

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

interactive ~ binary search

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

What is the point of limiting hacking tests to one test case per input (like in Div1B)? What if I find some slow solution and wanna create multiple test cases to make it TLE?

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

    Usually it's done to disallow the hacking attempts by throwing loads of random test cases into solutions that "just don't look right but I'm too lazy to create a hack".

    But yeah, there are also some disadvantages of this rule (your argument being probably the most important).

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

    Maybe the setter just wants to let slow solutions pass, with the time limit there just so you don't hog CPU time. Consider that problems with a limit on queries correspond to situations where you have plenty of computing power for yourself, but communicating with the oracle is costly.

    UPD: I forgot about non-divisibility by 3, which of course breaks this solution. Dealing with it isn't hard, but we need the leaves — or more specifically, we need to encounter at least K vertices with at least 2 backlinks.

    Also, I got AC despite a small bug.

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

    Also, this restricts you from hacking solutions which fail on subsequent test cases usually because global variables are not reset.

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

Div2D/Div1B was a really nice problem. Here's how I solved it:

Key insight, notice that if you guess (k, 2k), then you will receive response "x" if and only if . Then, we can guess (1, 2), (2, 4), and so on, and for the first n such that (2n, 2n + 1) returns "x" rather than "y", we know that lies in the range [2n - 1 + 1, 2n]. We can use a binary search to find , and then test the two possible values of a. Note that to test a value of a, simply query "? 0 z", which will return "x" if and only if z = a.

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

How to solve Div2 B in linear time?

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

    We have to match same characters similar to as in balanced paranthesis. Stack can be used for that purpose. Along with that keep count of number of matches. If number of matches are odd then first player is the last one to make a move otherwise second player is the last one to make a move.

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

The worst contest in my life

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

Could anybody help me why I am getting wrong answer in div2c:Submission

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

    Never mind found my mistake.

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

      could u tell what was the mistake? as my code is also failing on the same test case

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

How to solve div 1 c / div 2 e?

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

Probably the most rubbish round I have ever participated in.

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

Why I try to hack this solution while system told me

but actually he didn't resubmit or had been hacked. Could someone explain this (Is it a bug?)

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

    This happened with many times and really made me scared. This happens with me when I have ranklist or status page and contest ends.

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

      Just as you said,I submit my testcase and click the hack button 15 sec before contest ended and what I said above happned.

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

    Yes, this has also happened to me when I have a solution opened and the contest ends. It's just that the message needs to have "or the contest has ended" appended to it.

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

How to solve Div1D?

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

~

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

    can you please explain how you arrived at this solution?

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • You reserve one column for all verticle blocks. Even blocks will erase the whole column.
      • For all horizontal blocks, you reserve 2 columns. When you put 4 verticle block that will clear 2 columns.
      • For example: in my case, i have reserved the first column for verticle block. So first vert block i will put at > (1,1) second vert block at (3,1). Note that when the third block will come we will have clear column, so we can again put at (1,1) and so on.
      • Same can be done for the horizontal block, just that for the horizontal block we need 4 block to repeat the sequence. In my case i am using last two columns for horizontal blocks.
      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    My solution was: Place horizontal tile on (1,1) and (3,1) alternatively. Place vertical tile on (3,4) and (1,4) alternatively.

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

    MadLad sighted

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

Did anyone notice MikeMirzayanov profile shows Headquaters? CF is upgrading in every aspect. But atleast decrease the Time Limit if servers are running faster.

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

Not at all suspicious hacking of A:

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

    This is hackers profile Mr_Emrul

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

      two hackers vatsals1

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

        I am not the hacker but Mr_Emrul is. It can be proven because the first hack attempt was made by him at about just 2 minutes after the code was submitted by xzccry. I was trying to solve D but later I thought about hacking and I found that xzccry was being hacked so I also attempted him to hack just like everyone else but later realised that it's too dumb and I am just wasting time on this stupid thing and left it. Mr_Emrul was still hacking him and thus he should be at fault if someone should be.

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

          I hacked his first submission after 2 minutes of his submission because, after my B got hacked, I was searching in my room for hacking. And I finally got his submission.

          Moreover, I already requested to the judges for skipping these hacks. Because, I did these only for fun purpose, not for getting fake ratings.

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

            Only I and you were hacking his submission which means either you or I am the main account because the person who made this fake account would not be submitting these many submissions if he was not in the same room because he can't benefit from it. So it's probably you.

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

    notorious_coincidence

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

Ban this profile Mr_Emrul, He cheated using fake account xzccry hacks.

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

What's wrong with this solution(https://codeforces.me/contest/1104/submission/48757133). I know it should get WA for a=8(I fixed it later). However, I have no idea why I got TLE.

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

is it really necessary to set the number of questions limit to 60?

many solutions got idleness limit exceeded just because of asking about 61 or 62 questions!

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

    The limit is very deliberate. I think you even have at least one extra question as a buffer, the highest I ever saw when testing my solution was 59.

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

Why solutions of B with O(n2) are accepted? I got unsuccessful hack because of that https://codeforces.me/contest/1104/submission/48742016

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

Mr_Emrul hacked his own submissions with another handle. (That's what it looks like)

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

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

      How much fun did you have doing it? Do you recommend to others?

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

        No. I realized now that doing these hacks basically useless. And I am feelling guilty for that, may be I could find idea of D if I tried instead these hacks.

        → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

sad to see 2nd question copied from https://www.geeksforgeeks.org/delete-consecutive-words-sequence/ MikeMirzayanov scanhex. Um_nik

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

    From Timus 1654, actually

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

    Exactly. This is unfair!

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

    All three problems mentioned here are not the same is problem from round. Problem from round is more interesting because it doesn't say that the result is unique and for this problem (and not for problems you mentioned) this is not required.

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

When the total number of test cases are 76 and you get wrong answer on test 75. :( 48734381 P.S. And then you just remove a condition and get AC. :P

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

can anybody tell me what's wrong with my submission for problem C 48763210

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

    Try for the case '10000'
    You output
    1 2 1 1
    1 4
    3 4
    1 4

    After you put a tile on {1, 4} the first time The board looks like

    ....
    *..*
    ....
    ....

    When you put on 1 4 again, it overlaps with the piece left on 2 4.

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

Some number of wrong solutions passed the tests for problem B, having complexity O(n2). Is anything going to be done about this? I hacked two of those solutions, so I think it could've been avoided with stronger tests.

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

I was able to solve problem D in O(XP4P) were P is the number of prime factors of the gcd of the array and X is the number of distinct numbers in the array considering only the prime factors in the gcd.

however, I am not able to recognize what is X in terms of P I know that it is inversely proportional to P can someone help ?.

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

Hi, why this 48747775 gets WA instead of expected RE?

if (buffer[0] == 'e')throw(1);
→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

Div 2 second Question: I knew I have seen this problem in GFG but I didn't want to peek in GFG.I tried a lot, thought of many ways but I was not able to solve it, then I peeked in GFG and tried to understand the code but later I figure out that I have written in my note that this GFG code is out of my ability!! I lost hope somehow I tried to understand that GFG code but when I submitted the code it just gave me a wrong answer. Losing all hope I thought to gave up the contest but just for sake gave that problem one more try and suddenly thought about stack and hurray! I solved it. And later in 10 min I also solved the 3rd one too!! Best moment for me so far !! <3

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

my solution for Div2 C problem,it might be helpful for anyone. I solved it with greedy, just foucs on this 3 cases: 00, 11, 1010....

in first one: you will put the 2 tiles in the last column (first one in last column in row 3 and the other in last column row 1) so you will have 1 4 and 3 4 in second: you will put the 2 tiles in the first row (first one in first column in row 1 and the other in third column row 1) so you will have 1 1 and 1 3 in third: you will start put a title in (last column in row 3) then title in ( row 1 in column 1) then ( last column row 1 ) so you will remove last column and put last title in (row 1 column 3) and delete the first row and so on...

solution: https://codeforces.me/contest/1104/submission/48743875

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

Can anyone tell what is wrong in this:

https://codeforces.me/contest/1104/submission/48755607

Failing on 10th test case!

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

    Check for: 111001111. 3rd horizontal tile.

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

      Not failing for this but failing for 1000000 ... Thanks to you i got the idea where i was wrong

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

Any ideas for solving d ? how should i do query ?

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

    (2X % K) < (X % K) if and only if X < k <=2X, we do 0 1, 1 2, 2 4, 4 8, ...until first x, then we binary search between X and 2X to find the last point P it didn't switch, then output p+1

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

      HanaYukii is k =a with respect to problem .

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

        Number we need to find

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

          suppose a = 9

          HanaYukii so if we query :

          (0,1) = 1 = y

          (1,2) = 2 =y

          (2,4) = 4 = y

          (4,8) = 8 = y

          (8,16) = 8 = x

          we have to stop at (8,16) ??

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

            HanaYukii ok , i understand ..

            we will stop at 8,16.

            then we do bs using the same property like

            (8,12) (13,16)

            in first return will be x , in second y so x%a > 2x%a so the number will lie in range 8,12

            we again do bs

            8 10 = return 8 = x 11 12 = return 4 = y so again a will lie in 8,10

            similarily we do the same thing untill we find a .

            Am i right ? ?

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

      How do we prove (2*x)%k < (x%k) iff x<k<=2*k ?

      I mean if x<k<=2k then x%k will be x, but (2*x)%k can take values from 0 to k-1 and k-1 can be bigger than x.

      Also, if x%k < (2*x)%k then how can we say that k will be greater than 2*x (the skipping to next step i.e. 2x to 4x). I mean I can see the obvious solution that if k>2*x then x%k==x and (2*x)%k==2*x and 2*x>x (for x>1) but cannot see how it is always true the other way around.

      Sorry if it is trivial but I can't seem to prove/see this.

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

      I am not sure about this claim. Let X=8, K=5, 2X=16. Then 2X%5=1, X%5=3. 2X%5<X%5, but X>k.

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

        i think my iff miss writting an important condition if x>k then iff sorry for inconvenience

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

A great contest which makes me fall back to blue again TAT. Hope to publish the editorial as soon as possible.

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

mnbvmar is a madman for solving E

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

    I solved it during contest too but had tiny bug in inverse FFT and couldn't fix it before the end :'(

    48762778

    Just as always though

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

      I thought your implementation is pure DFT instead of FFT.

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

        It's true, they're a bit interwoven in my head

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

When will you release the tutorials?

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

Did the contest setter forget to post tutorials? It seems to late!

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

    YA I ALSO THINK SO PLEASE I REQUEST THE SETTERS TO UPLOAD IT SOON BECAUSE I EAGERLY WANT TO KNOW ABOUT THE DIV2D PROBLEM SOLUTION

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Solution for Div2D
      → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone explain the input and output of the Div2 D(for i can't understand the evaluation result)

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

    First line of input is number of games, then the number to guess is given each line. Each line of output is expected/actual number of queries used to guess the number. It is OK if number does not exceed 60.

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

Please help me on understanding what is happening on interactive system of 1104D - Game with modulo.

My previous submission, 48831942, outputs "! 161" after starting game with 160. On local environment, it then terminates normally after receiving "mistake" but seemingly does not terminate and gets TLE.

On the other hand, I altered my accepted solution to reproduce the problem on 48846517. It normally gets WA.

Can someone explain exactly what happened on my TLE submission?

→ Reply