scanhex's blog

By scanhex, 4 weeks 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  

»
4 weeks ago, # |
  Vote: I like it -133 Vote: I do not like it

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

  • »
    »
    4 weeks 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!"

»
4 weeks 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.

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

    Why it is always necessary to make such standard comments?

»
4 weeks 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

»
4 weeks 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 :).

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

    i'm pretty sure this would classify as cheating.

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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.

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

          Lol , Good for you.

        • »
          »
          »
          »
          »
          4 weeks 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.

»
4 weeks 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!

»
4 weeks ago, # |
  Vote: I like it -17 Vote: I do not like it

first!

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

Thanks!

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

codecmeme

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

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

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

...

»
4 weeks 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..

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

i visit so many coding sites but i don't know i always attract towards codeforces.

»
4 weeks ago, # |
  Vote: I like it -18 Vote: I do not like it

I have just eaten a whopper

»
4 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

GL & HF amigos

»
4 weeks 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 ?

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

    10 min after start of contest for next 20 min

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

All the best to all

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

Unable to register for div 2.

  • »
    »
    4 weeks 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)

  • »
    »
    4 weeks 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.

»
4 weeks 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.

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

comment.skip();

  • »
    »
    4 weeks 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.

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

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

    • »
      »
      »
      4 weeks 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.

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

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

»
4 weeks ago, # |
  Vote: I like it -23 Vote: I do not like it

Missed today's contest, due to internship :(

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

How to solve Div2-D/Div1-B?

  • »
    »
    4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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..

  • »
    »
    4 weeks 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?

    • »
      »
      »
      4 weeks 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' ??

»
4 weeks 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?

  • »
    »
    4 weeks 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.

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

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

    • »
      »
      »
      4 weeks 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).

»
4 weeks 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?

»
4 weeks 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.

  • »
    »
    4 weeks 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 :(

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

    • »
      »
      »
      4 weeks 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.

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

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

»
4 weeks 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.

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

    Used binary search. Twice.

    • »
      »
      »
      4 weeks 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 ?

      • »
        »
        »
        »
        4 weeks 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").

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

          yes.. i understood it . first we will find the range in which a will lie. using the property .. xmodk > 2xmodk then . x<k<=2x . then do binary search to find a in the range using the again same property.

»
4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Me after solving div2 A-B-C:

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

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

»
4 weeks 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)

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

    a = 8

    • »
      »
      »
      4 weeks 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

  • »
    »
    4 weeks 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

  • »
    »
    4 weeks 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].

    • »
      »
      »
      4 weeks 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?

    • »
      »
      »
      4 weeks 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

    • »
      »
      »
      4 weeks 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.

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

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

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

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

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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?

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

codeforces was a bit slow at times for me.

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

How to solve C?

  • »
    »
    4 weeks 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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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

      • »
        »
        »
        »
        4 weeks 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.

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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.

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

          Thanks, I understand this much: the leaves will <=n(all at depth 1) and >=k (all at depth n/k (max depth allowed)).

          But I don't understand where pigeonhole principle is being used in this.

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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.

»
4 weeks 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

  • »
    »
    4 weeks 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

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

Div.2

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

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

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

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

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

    Should have warned they upgraded their servers ;D

»
4 weeks 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.

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

    mine actually got hacked with that time limit?

    • »
      »
      »
      4 weeks 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.

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

      You should know that I didn't use BAD STATEMENTS

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

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

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

          I still think that question is very important.

  • »
    »
    4 weeks 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...

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

      But it traversals all the string n times.

      • »
        »
        »
        »
        4 weeks 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.

»
4 weeks 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.

  • »
    »
    4 weeks 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);
    }
    
  • »
    »
    4 weeks 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)

»
4 weeks 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

»
4 weeks 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

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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??

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

    codeforces system doesnt allow you to send same code as previous

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

      it means you changed something in code and then sent it

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

interactive ~ binary search

»
4 weeks 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?

  • »
    »
    4 weeks 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).

  • »
    »
    4 weeks 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.

  • »
    »
    4 weeks 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.

»
4 weeks 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.

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

How to solve Div2 B in linear time?

  • »
    »
    4 weeks 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.

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

    May be stack can be used

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

    May be stack can be used I am not sure , only pretests passed

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

The worst contest in my life

»
4 weeks 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

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

    Never mind found my mistake.

    • »
      »
      »
      4 weeks 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

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

        On greedily filling the grid by finding first free cell and assigning it to current tile (with clearing the row and column when required) can lead to a situation something like this:

        |F|F|F| |

        | |F|F|F|

        |F|F|F| |

        | |F|F|F|

        where F means the cell is filled. This situation occurs only when if horizontal and vertical tiles are placed adjacent to each other. To avoid this reserve first two rows for one type of tile and last two for other and always place same type of tiles adjacent to each other. Test case 14 checks for above situation.

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

How to solve div 1 c / div 2 e?

»
4 weeks ago, # |
  Vote: I like it -35 Vote: I do not like it

Probably the most rubbish round I have ever participated in.

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

  • »
    »
    4 weeks 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.

    • »
      »
      »
      4 weeks 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.

  • »
    »
    4 weeks 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.

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

How to solve Div1D?

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

~

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

    can you please explain how you arrived at this solution?

    • »
      »
      »
      4 weeks 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.
  • »
    »
    4 weeks 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.

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

    MadLad sighted

»
4 weeks 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.

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

Not at all suspicious hacking of A:

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

    This is hackers profile Mr_Emrul

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

      two hackers vatsals1

      • »
        »
        »
        »
        4 weeks 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.

        • »
          »
          »
          »
          »
          4 weeks 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.

          • »
            »
            »
            »
            »
            »
            4 weeks 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.

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

    notorious_coincidence

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

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

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

What's wrong with this solution(https://codeforces.com/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.

»
4 weeks 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!

  • »
    »
    4 weeks 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.

»
4 weeks ago, # |
  Vote: I like it -9 Vote: I do not like it

i wanna specially meet the problem setter of div2 A .

set a legend question .

l***u

»
4 weeks 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.com/contest/1104/submission/48742016

»
4 weeks 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)

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

    • »
      »
      »
      4 weeks 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?

      • »
        »
        »
        »
        4 weeks 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.

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

    From Timus 1654, actually

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

    Exactly. This is unfair!

  • »
    »
    4 weeks 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.

»
4 weeks 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

»
4 weeks 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

  • »
    »
    4 weeks 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.

»
4 weeks 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.

»
4 weeks 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 ?.

»
4 weeks 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);
»
4 weeks 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

»
4 weeks 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.com/contest/1104/submission/48743875

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

Can anyone tell what is wrong in this:

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

Failing on 10th test case!

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

    Check for: 111001111. 3rd horizontal tile.

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

      I still dont see any intersection or overlap in this test case. Please verify

    • »
      »
      »
      4 weeks 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

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

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

  • »
    »
    4 weeks 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

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

      HanaYukii is k =a with respect to problem .

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

        Number we need to find

        • »
          »
          »
          »
          »
          4 weeks 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) ??

          • »
            »
            »
            »
            »
            »
            4 weeks 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 ? ?

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

              yeah think you got it

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

                thanks for your effort. the only tricky oart was finding the range in which a will lie.

    • »
      »
      »
      4 weeks 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.

    • »
      »
      »
      4 weeks 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.

      • »
        »
        »
        »
        4 weeks 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

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

        actually it is the claim to find the first range that if xmodk > 2xmodk

        if k>xand k<=2x this property always holds. and we get the range in which a will lie

»
4 weeks 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.

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

mnbvmar is a madman for solving E

  • »
    »
    4 weeks 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

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

      I thought your implementation is pure DFT instead of FFT.

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

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

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

how to solve div2 d problem ??

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

When will you release the tutorials?

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

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

  • »
    »
    4 weeks 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

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Solution for Div2D
»
4 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

can someone help me with my solution of problem c , i am getting "wrong output format Unexpected end of file — int32 expected" on test case 14 , here is the solution to my link https://codeforces.com/contest/1104/submission/48794438

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

Can anyone please tell me what's wrong with my code for Div-2 C problem. I am getting 'wrong output format Unexpected end of file — int32 expected' on pretest 14 here is my code--https://codeforces.com/contest/1104/submission/48759202

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

    apporv use different variables for the inner loops , you are using the variable "i" for the traversal of string "s" as well as using variable "i" in the inner loop for traversing the grid which can change the value of variable i for the outer loop also your limits for the vertical check and horizontal check are wrong it should be from 1 to 3 not 1 to 4 as it will lead to error on 4 as your i+1 or j+1 will become 5 which is out of your matrix limit

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

Why we don't have an editorial yet. Pls provide editorial. (Atleast for E)

»
4 weeks 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)

  • »
    »
    4 weeks 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.

»
4 weeks 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?