### scanhex's blog

By scanhex, 2 years ago,

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:

Div. 2:

UPD: Editorial

• +347

 » 2 years ago, # |   -133 First time seeing 0 comments in a codeforces round blog :p
•  » » 2 years ago, # ^ |   +179 Maybe that's because you checked it right after it was created? Your comment is just an elaborate way of saying well known "First!"
 » 2 years ago, # |   +88 Whoa!! What a short precise round announcement.Hope problem statements are like that too :p.
•  » » 2 years ago, # ^ |   +83 Why it is always necessary to make such standard comments?
 » 2 years ago, # | ← Rev. 2 →   -69 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
 » 2 years ago, # | ← Rev. 3 →   +32 "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 :).
•  » » 2 years ago, # ^ |   -33 i'm pretty sure this would classify as cheating.
•  » » » 2 years ago, # ^ |   -8 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.
•  » » » » 2 years ago, # ^ |   -43 i have a higher rating than you therefore i am more intelligent than you.
•  » » » » » 2 years ago, # ^ |   0 Lol , Good for you.
•  » » » » » 2 years ago, # ^ |   +19 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.
•  » » » » » » 2 years ago, # ^ |   -14 i legitimately don't understand the point you're trying to make. i don't understand how an account can be fake.
•  » » » » » » » 2 years ago, # ^ |   +26 I legitimately don't understand why you claim you became expert when you are not=)
•  » » » » » » » » 2 years ago, # ^ |   -12 ? what are you talking about. i am expert
•  » » » » » » » » » 2 years ago, # ^ |   +27 Wow nice! And I am legendary grandmaster
•  » » » » » » » » » 2 years ago, # ^ |   -32 cool
 » 2 years ago, # |   +79 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!
•  » » 2 years ago, # ^ |   -37 i don't
•  » » 2 years ago, # ^ |   0 right , new question pattern
 » 2 years ago, # |   -17 first!
•  » » 2 years ago, # ^ |   -21 Nope
 » 2 years ago, # | ← Rev. 2 →   -28 Thanks!
 » 2 years ago, # |   +435
•  » » 2 years ago, # ^ |   0 How about Codezilla?
•  » » » 2 years ago, # ^ |   -8
•  » » 2 years ago, # ^ |   0 turned out amazin'thank you, next next
 » 2 years ago, # |   +10 Hope the problem statements will be as short as the blog.
 » 2 years ago, # |   +43 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. SpoilerHe starts barking about how I'm wrong by writing more cancerous comments, because he thinks showing indifference for downvotes will make him look less of an asshole.
•  » » 2 years ago, # ^ |   -18 that would be called abuse
•  » » 2 years ago, # ^ |   -39 stop being a hater and get good
•  » » 2 years ago, # ^ |   -32 i call bullshit
 » 2 years ago, # | ← Rev. 2 →   -19 ...
•  » » 2 years ago, # ^ |   +2 ... on codeforces
 » 2 years ago, # | ← Rev. 2 →   0 Sounds good..Hope the contest will be good as like as this announcement..
 » 2 years ago, # |   +34 My mind says study for exams .. my heart says participate in cf rounds.
•  » » 2 years ago, # ^ |   +11 My stomach says go eat your launch.
•  » » » 2 years ago, # ^ | ← Rev. 3 →   0 Stomach always wins XD!
•  » » » » 2 years ago, # ^ |   -15 No doubt XD
•  » » » 2 years ago, # ^ |   +67 My mouth says Shut up
 » 2 years ago, # |   -12 i visit so many coding sites but i don't know i always attract towards codeforces.
 » 2 years ago, # |   -18 I have just eaten a whopper
 » 2 years ago, # |   -8 GL & HF amigos
 » 2 years ago, # |   +6 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 ?
•  » » 2 years ago, # ^ |   +1 10 min after start of contest for next 20 min
 » 2 years ago, # |   +6 All the best to all
 » 2 years ago, # |   0 Unable to register for div 2.
•  » » 2 years ago, # ^ |   0 Registration closes 5 min before contest. Wait for late registration (10 min after start of contest)
•  » » 2 years ago, # ^ |   +16 This is speedforces. If you still havent registered dont even bother giving this contest.
 » 2 years ago, # |   +14 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.
 » 2 years ago, # | ← Rev. 2 →   -13 comment.skip();
•  » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +14 if(problem.interactive()) binarySearch.learn();
•  » » » 2 years ago, # ^ |   0 yeah, i agree with you, i tried to solve using binary search / using power of 2's but couldn't get the logic used.
 » 2 years ago, # |   +17 Score distribution for Div2 should be 500-750-1000-5000-20000-100000.
•  » » 2 years ago, # ^ |   +19 There were 5 problems.
•  » » » 2 years ago, # ^ |   +8 You get my point.
•  » » » » 2 years ago, # ^ |   0 That's right.3k People passed C but only 300 passed D and 2 passed E
 » 2 years ago, # |   -23 Missed today's contest, due to internship :(
 » 2 years ago, # |   +6 How to solve Div2-D/Div1-B?
•  » » 2 years ago, # ^ |   +3 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » 2 years ago, # ^ |   +1 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..
•  » » 2 years ago, # ^ |   +5 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?
•  » » » 2 years ago, # ^ |   0 How can we be sure that when we query (x,2x) There will be atleast a answer 'x' ??
 » 2 years ago, # | ← Rev. 2 →   +3 Can someone explain what the hell is going on with pretest 1 to div1B, div2D?
•  » » 2 years ago, # ^ | ← Rev. 2 →   -17 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
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +5 I also think that sth was wrong with pretest results. I got a lot of TLE instead of WA(Too many queries).
•  » » » » 2 years ago, # ^ |   0 Looks like you didn't read "e"
•  » » » » » 2 years ago, # ^ |   0 No, look at my last tle submit.
 » 2 years ago, # |   +6 What's wrong with this answer for D? I got like 20 idleness limit excedeed.. I flushed after every answer, what could be else?
 » 2 years ago, # | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ |   +3 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 :(
•  » » » 2 years ago, # ^ |   0 I ran the .erase thing on custom invocation with my hack case. It ran in 600ms. The .substr submissions ran in 1.2s
•  » » » » 2 years ago, # ^ |   0 erase may be close to O(1) but still you will have more than 10^9 operations.
•  » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +24 A lot of N^2 solutions passed B. Compiler magic works wonders.
•  » » » 2 years ago, # ^ |   +3 printf("Yes, You are totally right\n");
 » 2 years ago, # |   +3 div2 D was a nice problem. how to solve it. I think something related to bits.
•  » » 2 years ago, # ^ |   0 Used binary search. Twice.
•  » » » 2 years ago, # ^ |   0 can u explain a bit more , how bs will lead us to answer ?
•  » » » » 2 years ago, # ^ |   +13 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").
•  » » » » » 2 years ago, # ^ |   0 yes.. i understood it . first we will find the range in which a will lie. using the property .. xmodk > 2xmodk then . x
 » 2 years ago, # |   -8 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.
 » 2 years ago, # |   -14 Me after solving div2 A-B-C:
 » 2 years ago, # |   0 Problem D pretest 4? Whats wrong with bitmask dp solution?
•  » » 2 years ago, # ^ |   0 What was the logic?
 » 2 years ago, # | ← Rev. 2 →   +3 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)
•  » » 2 years ago, # ^ |   0 a = 8
•  » » » 2 years ago, # ^ |   0 For that I will get x in (7, 15)then I do reverse (7, 11) return x(7, 9) return x(7, 8) return xWhen jump size is 1 and return is x then x + 1 is answer
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 Yes, but do it until (x,y) becomes y-x=1
•  » » 2 years ago, # ^ |   0 Yes, I got ac asking1 22 4...2x 2x + 1And if answer on query 2x 2x + 1 is x, then you should do binary search on [2x; 2x + 1].
•  » » » 2 years ago, # ^ |   +1 how will binary search work in 2^x and 2^(x+1)because it might increase then suddenly become 0 and then again increase?
•  » » » » 2 years ago, # ^ |   0 Yes
•  » » » 2 years ago, # ^ |   0 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
•  » » » 2 years ago, # ^ |   0 I did a similar thing here My submission can you help me where exactly I went wrong.
•  » » » » 2 years ago, # ^ |   0 You are using too many queries.
 » 2 years ago, # |   +8 Using brute force (string::erase(i,i+2)) can easily accept DiV2B.
•  » » 2 years ago, # ^ |   +6 Wont it time out because string erase is linear? I guess.
•  » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   +28 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?
 » 2 years ago, # |   0 codeforces was a bit slow at times for me.
 » 2 years ago, # |   +16 How to solve C?
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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
•  » » 2 years ago, # ^ |   +72 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +8 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
•  » » » » 2 years ago, # ^ |   +47 The depth is less than n / k, so we output k cycles of length less than n / k.
•  » » » 2 years ago, # ^ |   0 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?
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 Suppose T is a rooted tree with leaves. If the depth of any leaf is at most d. Then T has at most nodes.
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   +3 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.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
 » 2 years ago, # |   -39 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
•  » » 2 years ago, # ^ |   0 don't cook soups with water, water doesn't belong in cooking, it's not that tasty
 » 2 years ago, # | ← Rev. 2 →   +16 Div.2
•  » » 2 years ago, # ^ |   0 i see this kind of memes after every contest...
 » 2 years ago, # |   +3 Should have warned the participants that there would be interactive problem : (
•  » » 2 years ago, # ^ |   +1 Should have warned they upgraded their servers ;D
 » 2 years ago, # | ← Rev. 6 →   -25 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.
•  » » 2 years ago, # ^ |   0 mine actually got hacked with that time limit?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   +1 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.
•  » » 2 years ago, # ^ |   -18 The questioner should read How not to read problem statements — Um_nik.
•  » » » 2 years ago, # ^ |   0 You should know that I didn't use BAD STATEMENTS
•  » » » » 2 years ago, # ^ |   -10 You should know what types of question you are supposed to ask.
•  » » » » » 2 years ago, # ^ |   0 I still think that question is very important.
•  » » 2 years ago, # ^ |   +18 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...
•  » » » 2 years ago, # ^ |   0 But it traversals all the string n times.
•  » » » » 2 years ago, # ^ |   +1 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.
 » 2 years ago, # | ← Rev. 3 →   +1 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.
•  » » 2 years ago, # ^ | ← Rev. 4 →   0 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); } 
•  » » 2 years ago, # ^ |   0 erase doesn't probably shift all elements ahead of a deletion. And it gives much better than O(n)
 » 2 years ago, # |   0 How to do Div2D,Div1B,I'm so self closing orz orz orz
 » 2 years ago, # |   +1 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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.
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 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.
•  » » » 2 years ago, # ^ |   0 I used the same logic. I think I made a mistake in implementation.
 » 2 years ago, # |   0 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??
•  » » 2 years ago, # ^ |   +3 codeforces system doesnt allow you to send same code as previous
•  » » » 2 years ago, # ^ |   +3 it means you changed something in code and then sent it
 » 2 years ago, # |   +3 interactive ~ binary search
 » 2 years ago, # |   +19 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?
•  » » 2 years ago, # ^ |   +55 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).
•  » » 2 years ago, # ^ | ← Rev. 2 →   +16 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.
•  » » 2 years ago, # ^ |   +10 Also, this restricts you from hacking solutions which fail on subsequent test cases usually because global variables are not reset.
 » 2 years ago, # | ← Rev. 3 →   +39 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.
 » 2 years ago, # |   0 How to solve Div2 B in linear time?
•  » » 2 years ago, # ^ |   +1 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.
•  » » 2 years ago, # ^ |   0 May be stack can be used
•  » » 2 years ago, # ^ |   0 May be stack can be used I am not sure , only pretests passed
•  » » » 2 years ago, # ^ |   0 i used stack , link
 » 2 years ago, # |   -12 The worst contest in my life
 » 2 years ago, # |   0 Could anybody help me why I am getting wrong answer in div2c:Submission
•  » » 2 years ago, # ^ |   0 Never mind found my mistake.
•  » » » 2 years ago, # ^ |   0 could u tell what was the mistake? as my code is also failing on the same test case
•  » » » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # | ← Rev. 2 →   +5 How to solve div 1 c / div 2 e?
•  » » 2 years ago, # ^ | ← Rev. 2 →   -51 Sorry i explained div2 c problem
•  » » » 2 years ago, # ^ | ← Rev. 2 →   -8 can you please explain div2 c problem solution?
•  » » » » 2 years ago, # ^ |   -8
 » 2 years ago, # | ← Rev. 2 →   -35 Probably the most rubbish round I have ever participated in.
 » 2 years ago, # |   0 DIV2-C Where I am wrong https://codeforces.com/contest/1104/submission/48760214
 » 2 years ago, # | ← Rev. 3 →   0 Why I try to hack this solution while system told mebut actually he didn't resubmit or had been hacked. Could someone explain this (Is it a bug?)
•  » » 2 years ago, # ^ |   0 This happened with many times and really made me scared. This happens with me when I have ranklist or status page and contest ends.
•  » » » 2 years ago, # ^ |   0 Just as you said,I submit my testcase and click the hack button 15 sec before contest ended and what I said above happned.
•  » » 2 years ago, # ^ |   0 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.
 » 2 years ago, # |   +10 How to solve Div1D?
 » 2 years ago, # | ← Rev. 2 →   0 ~
•  » » 2 years ago, # ^ |   0 can you please explain how you arrived at this solution?
•  » » » 2 years ago, # ^ |   0 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.
•  » » 2 years ago, # ^ |   +8 My solution was: Place horizontal tile on (1,1) and (3,1) alternatively. Place vertical tile on (3,4) and (1,4) alternatively.
•  » » » 2 years ago, # ^ |   0 that also works.
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   0 can u please explain why i am getting WA on testcase 14. https://codeforces.com/contest/1103/submission/48764362
•  » » » » » 2 years ago, # ^ |   0 https://codeforces.com/contest/1104/submission/48766342 i got WA on test 14 i don't know why
•  » » » » » » 2 years ago, # ^ |   0 Check my comment above.
•  » » 2 years ago, # ^ |   0 MadLad sighted
 » 2 years ago, # |   -15 Did anyone notice MikeMirzayanov profile shows Headquaters? CF is upgrading in every aspect. But atleast decrease the Time Limit if servers are running faster.
 » 2 years ago, # |   +57 Not at all suspicious hacking of A:
•  » » 2 years ago, # ^ |   0 This is hackers profile Mr_Emrul
•  » » » 2 years ago, # ^ |   0 two hackers vatsals1
•  » » » » 2 years ago, # ^ |   +33 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.
•  » » » » » 2 years ago, # ^ | ← Rev. 2 →   +4 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.
•  » » » » » » 2 years ago, # ^ |   -16 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.
•  » » » » » » » 2 years ago, # ^ |   +53
•  » » 2 years ago, # ^ |   0
 » 2 years ago, # |   +14 Ban this profile Mr_Emrul, He cheated using fake account xzccry hacks.
 » 2 years ago, # |   +5 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.
 » 2 years ago, # |   0 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!
•  » » 2 years ago, # ^ |   +2 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.
 » 2 years ago, # |   -9 i wanna specially meet the problem setter of div2 A .set a legend question . l***u
 » 2 years ago, # |   0 Why solutions of B with O(n2) are accepted? I got unsuccessful hack because of that https://codeforces.com/contest/1104/submission/48742016
 » 2 years ago, # |   0 Mr_Emrul hacked his own submissions with another handle. (That's what it looks like)
•  » » 2 years ago, # ^ |   +24
•  » » » 2 years ago, # ^ |   +39 How much fun did you have doing it? Do you recommend to others?
•  » » » » 2 years ago, # ^ |   -7 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.
 » 2 years ago, # | ← Rev. 2 →   -19 sad to see 2nd question copied from https://www.geeksforgeeks.org/delete-consecutive-words-sequence/ MikeMirzayanov scanhex. Um_nik
•  » » 2 years ago, # ^ |   0 From Timus 1654, actually
•  » » » 2 years ago, # ^ |   0 Codeforces too: 81A - Plug-in.
•  » » 2 years ago, # ^ |   -17 Exactly. This is unfair!
•  » » 2 years ago, # ^ |   +23 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.
 » 2 years ago, # |   0 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
 » 2 years ago, # | ← Rev. 2 →   0 can anybody tell me what's wrong with my submission for problem C 48763210
•  » » 2 years ago, # ^ | ← Rev. 3 →   +1 Try for the case '10000'You output1 2 1 11 43 41 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.
•  » » » 2 years ago, # ^ |   0 thanks bro, i totally missed that
 » 2 years ago, # |   +1 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.
 » 2 years ago, # | ← Rev. 2 →   0 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 ?.
 » 2 years ago, # |   0 Hi, why this 48747775 gets WA instead of expected RE? if (buffer[0] == 'e')throw(1); 
 » 2 years ago, # | ← Rev. 2 →   +3 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
 » 2 years ago, # |   +1 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...
 » 2 years ago, # |   0 Can anyone tell what is wrong in this:https://codeforces.com/contest/1104/submission/48755607Failing on 10th test case!
•  » » 2 years ago, # ^ |   0 Check for: 111001111. 3rd horizontal tile.
•  » » » 2 years ago, # ^ |   0 I still dont see any intersection or overlap in this test case. Please verify
•  » » » 2 years ago, # ^ |   +3 Not failing for this but failing for 1000000 ... Thanks to you i got the idea where i was wrong
•  » » » » 2 years ago, # ^ |   0 Glad to know I could help :D
 » 2 years ago, # |   0 Any ideas for solving d ? how should i do query ?
•  » » 2 years ago, # ^ | ← Rev. 4 →   0 (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
•  » » » 2 years ago, # ^ | ← Rev. 6 →   0 HanaYukii is k =a with respect to problem .
•  » » » » 2 years ago, # ^ |   0 Number we need to find
•  » » » » » 2 years ago, # ^ |   0 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 = xwe have to stop at (8,16) ??
•  » » » » » » 2 years ago, # ^ |   0 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,12we again do bs 8 10 = return 8 = x 11 12 = return 4 = y so again a will lie in 8,10similarily we do the same thing untill we find a .Am i right ? ?
•  » » » » » » » 2 years ago, # ^ |   0 yeah think you got it
•  » » » » » » » » 2 years ago, # ^ |   0 thanks for your effort. the only tricky oart was finding the range in which a will lie.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 How do we prove (2*x)%k < (x%k) iff x2*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.
•  » » » » 2 years ago, # ^ |   +2 2x % k = 2x-k > x since x
•  » » » » » 2 years ago, # ^ |   0 Thank You
•  » » » 2 years ago, # ^ |   0 I am not sure about this claim. Let X=8, K=5, 2X=16. Then 2X%5=1, X%5=3. 2X%5k.
•  » » » » 2 years ago, # ^ |   0 i think my iff miss writting an important condition if x>k then iff sorry for inconvenience
•  » » » » 2 years ago, # ^ |   0 actually it is the claim to find the first range that if xmodk > 2xmodkif k>xand k<=2x this property always holds. and we get the range in which a will lie
 » 2 years ago, # |   +5 A great contest which makes me fall back to blue again TAT. Hope to publish the editorial as soon as possible.
 » 2 years ago, # |   +22 mnbvmar is a madman for solving E
•  » » 2 years ago, # ^ | ← Rev. 2 →   +10 I solved it during contest too but had tiny bug in inverse FFT and couldn't fix it before the end :'(48762778Just as always though
•  » » » 2 years ago, # ^ |   +3 I thought your implementation is pure DFT instead of FFT.
•  » » » » 2 years ago, # ^ |   0 It's true, they're a bit interwoven in my head
 » 2 years ago, # | ← Rev. 2 →   -27 how to solve div2 d problem ??
 » 2 years ago, # |   +19 When will you release the tutorials?
 » 2 years ago, # |   0 Did the contest setter forget to post tutorials? It seems to late!
•  » » 2 years ago, # ^ |   -8 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
•  » » » 2 years ago, # ^ |   0 Solution for Div2Dhttps://codeforces.com/contest/1103/submission/48786346. Check this out for my implementation. Look at the number 60 = 2*30, and 2^30 > 10^9, which means the solution bears sth in common with binary-kindof factor. Naturally, you will come up with asking number x and 2*x. If x< a && 2*x < a then the query should return "y", but what if x < a && 2*x > a. We could prove by contradiction that in this case (2*x)%a < x%a. Please note that a <= 2*x < 2*a. So now by asking that kind of good query ("? x 2*x") we will soon find out the value of x such that x < a <= 2*a. The next part is binary search in the range (x, 2*x]. We are looking for the point ANS lies in this range such that ANS%a == 0. And we saw that the modulo a in that range looks something like this: [x+1, x+2,... a-1, 0, 1, 2,.., (2*x)%a]. So here we execute the binary search, asking "? x mid", if it returns "x" means x%a >= mid%a, we know that mid fall in the subrange [a, 2*x], then we should look at the lower range (r = mid-1), similarly if it returns "y" the we should look at the upper range (l = mid+1).Be careful of the case a==1. But I believe handling that corner case is easy.
 » 2 years ago, # | ← Rev. 3 →   0 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
 » 2 years ago, # |   0 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
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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
 » 2 years ago, # |   0 Why we don't have an editorial yet. Pls provide editorial. (Atleast for E)
 » 2 years ago, # |   0 Can anyone explain the input and output of the Div2 D(for i can't understand the evaluation result)
•  » » 2 years ago, # ^ |   0 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.
•  » » » 2 years ago, # ^ |   0 Thank u!
 » 2 years ago, # |   0 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?