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

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

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

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

Why it is always necessary to make such standard comments?

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

"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 :).

i'm pretty sure this would classify as cheating.

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.

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

Lol , Good for you.

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.

i legitimately don't understand the point you're trying to make. i don't understand how an account can be fake.

I legitimately don't understand why you claim you became expert when you are not=)

? what are you talking about. i am expert

Wow nice! And I am legendary grandmaster

cool

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!

i don't

right , new question pattern

first!

Nope

Thanks!

How about Codezilla?

https://www.youtube.com/watch?v=gl1aHhXnN1k

turned out amazin'

thank you, next nextHope the problem statements will be as short as the blog.

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.

that would be called abuse

stop being a hater and get good

i call bullshit

...

... on codeforces

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

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

My stomach says go eat your launch.

Stomach always wins XD!

No doubt XD

My mouth says Shut up

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

I have just eaten a whopper

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

10 min after start of contest for next 20 min

All the best to all

Unable to register for div 2.

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

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

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.

comment.skip();

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.

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

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

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

There were 5 problems.

You get my point.

That's right.3k People passed C but only 300 passed D and 2 passed E

Missed today's contest, due to internship :(

How to solve Div2-D/Div1-B?

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

First, find p such that 2

^{p}<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.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..

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?

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

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

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.

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

I also think that sth was wrong with pretest results.

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

Looks like you didn't read "e"

No, look at my last tle submit.

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

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.

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 :(I ran the .erase thing on custom invocation with my hack case. It ran in 600ms. The .substr submissions ran in 1.2s

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

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.

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

printf("Yes, You are totally right\n");

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

Used binary search. Twice.

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

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

Now think about "? x y" when

x<y≤ 2xand you knowx<a,if the reply isx,you can make sure thatx<a< =y,otherwisey<a.(sincex<a,,ifx<a≤y, and the reply isx)So you can ask "? 1 2","? 2 4","? 4 8"until the reply is

x,now you can make sure that (iis 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 ifa< =midby asking "? i mid").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.

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.

Me after solving div2 A-B-C:

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

What was the logic?

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)

a = 8

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

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

Yes, I got ac asking

1 2

2 4

...

2

^{x}2^{x + 1}And if answer on query 2

^{x}2^{x + 1}is x, then you should do binary search on [2^{x}; 2^{x + 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?

Yes

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

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

You are using too many queries.

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

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

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.

How to solve D? My solution works in something like 6

^{11}·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?codeforces was a bit slow at times for me.

How to solve C?

Let's run dfs. If number of leaves is at least

kthan we can find k cycles, otherwise we can find a path with length at leastn/k.I didn't get AC, but I think it should work

Build dfs tree from some vertex. If its depth is at least

n/kthen we found a path. Otherwise by pigeonhole principle tree has at leastkleaves. Let's choosekleaves. 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.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

The depth is less than

n/k, so we outputkcycles of length less thann/k.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?

Suppose

Tis a rooted tree with leaves. If the depth of any leaf is at mostd. ThenThas at most nodes.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.

We don't even need

kleaves. 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 thankcycles (so one of them has to have length ≥n/k) or find at leastkcycles.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.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

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

Div.2

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

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

Should have warned they upgraded their servers ;D

I try to hack some submissions of Div2.B (

O(n^{2})). After I got a sucessful hack, I found that some code using string::erase won't be hacked, even though the worst complexity isO(n^{2}).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.

mine actually got hacked with that time limit?

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.

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

You should know that I didn't use BAD STATEMENTS

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

I still think that question is very important.

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

But it traversals all the string n times.

Yeah, and the whole string is of length

n, which is aboutn^{2}operations, or 10^{10}in this case, which he just pointed out can be done in under a second with how well optimized std::memmove is.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.

I think this gives worst case.

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

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

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

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.

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.I used the same logic. I think I made a mistake in implementation.

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

codeforces system doesnt allow you to send same code as previous

it means you changed something in code and then sent it

interactive ~ binary search

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?

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

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

Kvertices with at least 2 backlinks.Also, I got AC despite a small bug.

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

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 firstnsuch that (2^{n}, 2^{n + 1}) returns "x" rather than "y", we know that lies in the range [2^{n - 1}+ 1, 2^{n}]. We can use a binary search to find , and then test the two possible values ofa. Note that to test a value ofa, simply query "? 0 z", which will return "x" if and only ifz=a.How to solve Div2 B in linear time?

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.

May be stack can be used

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

jaqenhghar98 _olOlo_

i used stack , link

The worst contest in my life

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

Never mind found my mistake.

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

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.

How to solve div 1 c / div 2 e?

Sorry i explained div2 c problem

can you please explain div2 c problem solution?

https://codeforces.com/blog/entry/64685?#comment-486470

Probably the most rubbish round I have ever participated in.

DIV2-C Where I am wrong https://codeforces.com/contest/1104/submission/48760214

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?)

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

Just as you said,I submit my testcase and click the

hack button15 sec before contest ended and what I said above happned.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.

How to solve Div1D?

~

can you please explain how you arrived at this solution?

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

that also works.

can u please explain why i am getting WA on testcase 14. https://codeforces.com/contest/1103/submission/48764362

https://codeforces.com/contest/1104/submission/48766342 i got WA on test 14 i don't know why

Check my comment above.

MadLad sighted

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

Not at all suspicious hacking of A:

This is hackers profile Mr_Emrul

two hackers vatsals1

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.

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.

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.

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

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.

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!

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.

i wanna specially meet the problem setter of div2 A .

set a legend question .

l***u

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

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

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

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.

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

From Timus 1654, actually

Codeforces too: 81A - Plug-in.

Exactly. This is unfair!

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.

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

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

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.

thanks bro, i totally missed that

Some number of wrong solutions passed the tests for problem B, having complexity

O(n^{2}). 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.I was able to solve problem D in

O(XP4^{P}) werePis the number of prime factors of the gcd of the array andXis 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

Xin terms ofPI know that it is inversely proportional toPcan someone help ?.Hi, why this 48747775 gets WA instead of expected RE?

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

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

Can anyone tell what is wrong in this:

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

Failing on 10th test case!

Check for: 111001111. 3rd horizontal tile.

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

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

Glad to know I could help :D

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

(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

HanaYukii is k =a with respect to problem .

Number we need to find

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) ??

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

yeah think you got it

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

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.

2x % k = 2x-k > x since x<k

Thank You

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.

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

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

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

mnbvmar is a madman for solving E

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

I thought your implementation is pure DFT instead of FFT.

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

how to solve div2 d problem ??

When will you release the tutorials?

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

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

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

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

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

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

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

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

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

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.

Thank u!

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?