Hi everybody!

Codeforces Round #371 takes place on 13 September at 19:35 MSK for the both divisions. This is our first round and we hope it won't the last one.

This round is prepared by me (Anton Tsypko) and Sonechko (Sofia Melnyk). We want to say thanks to GlebsHP (Gleb Evstropov) and Sereja (Sergey Nagin) for help with preparation of this round, MikeMirzayanov (Mike Mirzayanov) for Codeforces and Polygon systems, iSlava (Viacheslav Ocheretnyi), otoshol (Mark Mikhno), BigBag (Matvey Aslandukov), winger (Vladislav Isenbaev) and AlexFetisov (Alex Fetisov) for testing problems.

It's recommended for both divisions to read the Interactive Problems Guide before the round. Scoring distribution will be published right before the start of the contest.

Good luck!

Scoring:

Div 2: 500 — 1000 — 1000 — 2000 — 3000

Div 1: 500 — 1000 — 2000 — 2000 — 2000

Upd: Congratulations to the winners:

Div 1:

Div 2:

UPD: We are sorry that Div 1 C is very similar to this, but the contest will be **rated**.

Hope the Codeforces remain stable unlike last Div2 round.....

Hope so.. last round was pain :(

## Good day, good Codeforces, and tonight I will be a purple Coder.That is really great.Thank you everyone!Thank the is world!

tomorrow, eid day in bangladesh. we can celebrate eid with contest. hope it will be a great contest.

In previous round contain Interative problem I lose 100 point on problem C because fflush :)) I hope nobody wrong like this :))

How you passed the example then?

my code have many if and one of them I forget fflush :((

My strategie usually is make functions to interact, one for reading and one for writing. You can do this almost in all cases and you won't have to be worried about flushing or parsing at every moment.

in the name of allah, most merciful

which rounds contain interactive problems?

i hope somebody says numbers for practice.

have good contest.

680C - Медвежонок и простота за 100

in Codeforces Round #356 (Div. 2)

Oh no!!! Interactive problems again :(

hope for a stable Codeforces.

Eid mubarak for all muslims!

Eid Mubarak you too :)

Eid Mubarak Bro :D

Eid Mubarak Bro.

Eid mubarak

Eid Mubarak for all !

Eid Mubarak :D

Amin.

the holy Eid mubarak guys.

Eid Mubarak! :)

Eid Mubarak ^_^

Eid Mubarak brother!!!

Wow, Sereja is back! Is he also going to become coordinator of CF rounds?

His last contest was nearly 2 years ago!!! His problems are really awesome :D

I so want this round to be rated and hassle-free.

I feel very interest in interactive problems :) but can't solve well :( All though, good luck to me for this Contest! and today is also Eid Day for in Bangladesh! Hope good luck in this Eid Day Conteset :D I think Everything will be okay During the contest Time.

Hope you solve the interactive problem. and also Eid mubarak. :)

good luck to everyone :)

How to hack the interactive problem?

If you're on Linux, write

`sudo rm -rf /`

. Make sure you have root access or it won't work!If you're on Windows, make a file named something.bat, type in it

save and run it. It really works!

No one is such a arse I think!

It isn't funny.

3ib da enta red

I'm shocked! what the number of downwotes!

Isn't truth-seeker you ?!?!

`I'm shocked!`

yes, exact! he is me! but how you got it!? actually I can't have virtual on the contests that I have participated before and I have such a fake account!

Actually, we have common friend (;

What if I'm on mac? Can I do anything?? :((((((((

You must submit hacking program which will interact with target

It depends on particular problem. Instruction for writting hacking program always present in an interactive problem statement.

It will be described in the statement.

Eid Mobarok Everyone <3 from Bangladesh <3

Best wishes for Codeforces <3

Wish the Internet&server will be better..........

Wow! Interactive problems this time. Expecting Stable CF round this time :)

why interactive man?

Because the last line is "

It's recommended for both divisions to read the Interactive Problems Guide before the round"I have problem with registration to contest... I register and then I click to list of participants and I still see "Register Now" although I was registered...

interactive :D

It will be a rated round ?

yes

I'm shocked this comment is so far down, considering how it usually goes...

**** Get ready fellas! :P :P

it's 10 left minute to start the round and the score distribution is not announced yet !

UPD : now it's 1 min and nothing announced :(

Relatively few people registered(in both divs). I hope that means a working website!

It took me only 10 mins to register for the contest this time.

Is everything working fine for everyone ?? For me on main codeforces page top menu is invisibile like in mobile view

No. I wait 5 minutes each time for submit page to open.

the last round my first time solve two problem and from first submission , I hope do it again :)

Eid mubarak to all :) hoping a great contest

লাইক দিয়ে পাশে আছি, ফ্রান্স।

I'm not able to submit You should be registered for the contest to be able to submit but on the contests page it says registration completed.

I am having the same problem.

fixed

Cannot submit.It says should be registered for the contest even though I registered.

I cant see other codes when block my problem :(

cant open room, random pages are loading ! clicking on a submission, it says soln already hacked or resubmitted ! but thats not the case

Not able to hack solutions

Can't submit any solution.

when I click submit button, I just see nonsense err.

How can I test interactive code on ideone? Any help will be deeply soulfully appreciated :D

Write some code which will answer the questions automatically instead of answering them in stdin

It is just unfair to include problems like this div2E/div1C

as you can see a lot of people had it passed in around 20 minutes

there is one who solved it in 4 minutes ( after he solved A )

13C - Последовательность

it's here :)

too much creativity

Man! Now I get the reference. I thought it was a joke only I didn't get!!

Pasting link to the same problem, with visible solutions, during the contest... genius.

The problem is not the same.

You are right of course, but the only difference is non-decreasing vs. increasing, what is handled by line

`t[i] -= i;`

. So, almost the same problem.It is genius!!! Way to protest like a boss :p

it was actually posted here blog about 1 hour before the end of the contest so posting a comment before 10 minutes isn't that genius

Omg, make it unrated pls

And your comment here fixed the whole situation.

At least don't make it unrated just remove the question from consideration.

Great idea !!

Yeah if you just solved the C or smth you better be GO TO HELL IT'S THE PERFECT IDEA EVERRRRRRRRR!!!!!!

Seriously, it looks like "great idea" to you?

Oh I forgot that it would be unfair for those who solved C only.... or maybe I didn't forget and it was just sarcastic comment.

the real genius is the problem setter i mean i wouldn't have pasted anything if it weren't some old codeforces problem

Do you remember all problems that ever been on Codeforces? Neither do I, GlebsHP, authors, MikeMirzayanov or anybody else. Posting such link during the contest makes things only worse; you (and all who did the same thing except you) could've posted such a link after the contest ends so that results of people wouldn't be affected.

After all, there is no difference between knowing a solution of problem because you studied many algorithms (even unpopular ones) and knowing the same problem beforehand. It's your advantage, use it. Posting it in public is equivalent to spoiling the solution during the contest.

I just checked the thread by spiral_out. It appears this comes on the first page by a simple google search. Sure a co-ordinator shouldn't be expected to do this, but it's mind blowing how the author didn't even spend few minutes checking if it's original or not by a simple google search.

After all checking if your ( as an author ) 5-8 tasks are original ( as in not easily googleable) or not has nothing to do with you knowing the whole problem set on CF.

I agree with you. Still, this is not an excuse for ruining contest for everybody else. This is not how the contest ethics works.

But let me ask you a question. You may often see a problem in div2 and even in div1 that may easily be reduced to a shortest path problem in directed weighted graph. You type in Google "shortest path algorithm" and it suggests you "Dijkstra" even until you press Enter. Does that frustrate you in the same manner?

In this case it is not even the same problem; one should come up with replacing

a[i] witha[i] -itrick to transform it to that problem.ok dude , you don't remember any and you don't need to actually remember all problems on codeforces

but that doesn't mean checking if a problem is googlable or not :)

You are intentionally ignoring my point :) I'm not trying to find excuses for authors and coordinator, it is indeed a fail from their side.

What I'm talking about is that you and the guy who posted something at the middle of the contest did the wrong thing. In the conditions when this fail already happened, posting the link to the problem is a wrong move. Do not do that. Post it after the contest ends.

And yes, I know you were the second one to do that. This is not an excuse for you. Hope it is now clear what I mean.

At this moment I stop this conversation.

Is this a[i] — i trick a trivial transformation? Enough to deem the problem non-original? (Genuine question — I didn't know the trick — I was wondering how common it is).

Not exactly trivial, but it was obvious to me and should be to most people who are at the level of usually solving div1C. Basically, subtracting 1 from every difference.

ok i am the guilty guy

some guy just copies an old codeforces problem and include it as a div1C problem

and some pedophile posts the solution one hour before the end of the contest

and i am the one who is guilty

i just commented here 5 minutes before the end

go paste the statement into google and you will find a post on quora

thanks people

Triggered lol.

We can agree that it's impossible to know all problems. But Google does. IMHO every setter before the very beginning of preparing the problem should try to find it on the internet. Otherwise, such situations will surely happen

But Google knows so many things it is hard to specify what are you looking for. Googling tasks is not easy. I copied my code from my high school's online judge, but was unable to find a thread on CF about that task which I know I have read.

Change a[i] by a[i] — i, it becomes 13C. Is it correct?

Yes I just realized -_-

12 or 13 ?

UPD:fixedI accidentally down-voted your comment while trying to up-vote it and Codeforces won't let me change it. Sorry.

Also A isn't very original, I am sure I have seen easy variations of it twice in recent contests.

Waiting for rated contest for infinity time and now it will be unrated with almost 100% probability. That's fun.

It is still funnier than losing a lot of ratings because of not Googling the solution :P

No, unrated is fine for me, because I didn't google the solution. And got too much trouble with Div1B.

I think it didn't affect so much because people are not accustomed to reading blogs during contests. Div 1 people would not google and for Div2 the number os submissions show people being unaware of it. Around 300 submissions should have raised suspision.

Div1 people would not google? You'd be surprised...

I've been told that nowadays most valuable skill is not to know a lot of information, but rather to be able to get information you are missing in a short time :)

(Ideally — without bothering other people with your questions while doing it)Me too. But from now on google and I will be best friends.

*the problem is well known*

*it was spoiled halfway through the contest so many people saw the solution*

*there is one more contest in 4 days :D*

Wait, I didn't get it, your reason for unrated event is "there was a problem in a contest which is rather well-known", right? :) Not technical issues, not problems being badly prepared, but the fact that some problem doesn't contain brand-new idea?

Maybe it is time for me to hope for round being unrated as I didn't manage to solve D which is also well-known and classic :)

I believe it was sarcasm, right? :)

Anyway, why is D well-known and classic? I didn't come up with a solution with reasonable running time asymptotics and submitted parallel binary searches with 2D Fenwick tree and heavy optimizations that works in

O(nmlog^{3}n). Though, on pretests and my own tests here on CF it runs for <4s.UPD: ok, I got it. The solution is to do a binary search and then make a 2d-minimum query in the small rectangle. What exactly here is well-known and classic?If you mean first part of my answer — I missed the fact that there were some comments about this problem and discussions right during a contest, yet I don't think it is enough for making it unrated.

For a second part — my solution is far from being cool, it is similar to your idea, and there is high probability that it will fail:). Even if it will pass — I haven't actually solve problem in terms of figuring out proper solution, and that makes me sad anyway. For me

"find maximum in a static submatrix (using sparse table)"sounds like a very classic problem.UPD. Oh, it seems that for other people transition to binary search + max.query was not so obvious, while I got stuck on a part about finding max in O(1).I think it's okay as long as the chance this event happened in codeforces is very low. I mean if you skilled enough, everything on internet could become the spoiler for the problem. The point is getting solution with that method is also required certain skill.

It's quite funny that

713Cis similar to13C. Maybe it was intended joke? lolHow to solve Div.1 C???

Let b[i] = a[i]-i. Then it can be thought that you're to make non-decreasing sequence instead of increasing sequence. From that, a dynamic programming idea comes out. D[i][j] : minimum cost of making b[1] ~ b[i] sorted, such that b[i] = j: D[i][j] = min(D[i-1][k]) + abs(b[i]-j) for k <= j. j has to be one of the initial values of b, so the time complexity is O(n^2).

http://codeforces.com/contest/713/submission/20589839

How does b[i]=a[i]-i convert strictly increasing problem to non decreasing?

"a[i] is increasing" and "b[i] = a[i]-i is non-decreasing" are equivalent.

Okay it founds an answer but how to be sure it's the smallest one? We convert our array, how can it be the right answer?

Suppose not. Suppose there is a set of moves that's smaller than our answer. use the same set of moves on b[i] = a[i] — i. It will be a non decreasing array. Which will cause a contradiction.

Div1C: go left to right, increase values greedily up and count how much you add. Also maintain a sorted vector of best costs for moving down the current stairs by one. E.g. you pay 1, 1, 1, then 2, then 3, etc. Costs are groupped so vector consists of pairs (cost, number): (1,3),(2,1),(3,1),...

When next element is larger than current height, you increase all costs by 1 and push (1, h-1-x) to the vector's back.

When next element is smaller or equal, you increase it by

dto make it higher. Then you reduce the latestsdcosts by 1 (you may need to split some group in vector into two groups). And you increase all other costs by 1.Then you take all non-positive costs from vector's back and "use" them: decrease current answer and height.

So this vector grows linearly, leading to

O(N^{2}) solution. This can also be seen as DP.Missed the registration...a pity.

I figured out a solution via MCMF.

First we can consider another array:

a_{2}-a_{1},a_{3}-a_{2},a_{4}-a_{3}, ...,a_{n}-a_{n - 1}.Let's consider this new array as

b_{i}, and find the impact of increasinga_{i}tob_{i}.For increasing

a_{1}, we getb_{1}decrease by 1.For increasing

a_{i}(1 <i< =n- 1), we getb_{i - 1}increase by 1, andb_{i}decrease by 1.For increasing

a_{n},we getb_{n - 1}increase by 1.Notice that we can add arbitrary number to

a_{i}.Let's viewb_{i}as n-1 piles of stones(allowing minus stone number), then we can perform 2 types of operations.1.Generate 1 stone at pile 1 or pile n-1.Cost is 1.

2.Exchange 1 stone between adjacent piles.Cost is 1.

Out goal is to make every pile at least 1 stone.

Let's solve this model by MCMF.

Categorise

b_{i}as three types A(for piles with number more than 1), B(for piles with number less than 1), C(for piles with number exactly 1).Connect SOURCE to

b_{1}andb_{n - 1}edges with infinity flow and cost 1.(Meaning generating stones.)Connect SOURCE to type A vertex edges with (

b_{i}- 1) flow and cost 1.(Meaning redundant stones.)Connect type B vertex to DRAIN edges with ( -

b_{i}+ 1) flow and cost 1.(Meaning required stones.)Connect bidirectionally between adjacent vertexes edges with infinity flow and cost 1.(Meaning exchange.)

Perform MCMF and you are done.

Problem B. Filya and Homework ***** In this problem, Filya is allowed to pick any integer X, even x = 0. For each element of the array he can decide whether to add x to it, subtract x, or do nothing. He can choose to not add x at all, or not subtract x at all, or just do nothing at all. For each particular element he can add x to it (or subtract) no more than once.

This costed me 3 WA -_-

Yes, same here. I got 1 wa and waited for an announcement to clarify this. :/

fml.

.

No, 3 1 2 4

I had taken care of this case, and mistakenly typed > instead of >=.

fml, lol :D

That was a lot of hacks!

I have a complicated solution for div2D, too easy to make bugs...

Yeah i hope it had strong pretests...

Could problem C div 2 solved using simple bst? I represent the structure using 1D array.

It's just simple trie problem.

Trie sounds like an overkill. Can't we simply use maps here?

Lol, I just copied my implementation of trie and changed it a little bit.

I think no because of anti-hash test!! not sure though!!

I kinda worried about maps speed so I'm using array instead. So the root of tree is 1. If current node is x and the digit is odd, then we visit node number x*2 + 1, else we visit node number x*2. I'm taking advantage that the maximum number of digits is 18. So 2^18 < 600000.

I'm sorry if it sounds dumb. But Isn't trie derived from bst?

Can't we just use an array of size 2^18 ?

Now I feel stupid for coding a trie from scratch -_- .

Did you trie your best?

I can't even... you're the odd one aren't you?

I am unable to think of a story for these comments.

Yes. I know I'm

different:)A simple binary tree ( 1D array ) is enough ... you put number of strings that have same parity structure in leafs ( 1 << 18 ) ... code : http://codeforces.com/contest/714/submission/20591546

Problem C isn't just old — it's a classical min cost flow problem. :(

Very weak pretests for A and B, especially B. My solution is completely wrong, but when I noticed it, it was already locked...

C can be solved in O(Nlog N) by using the fact that abs(x-k) is convex function, I think. (I have made almost the same problem and used in Japanese domestic contest.)

I also gave the problem with very similar trick about convexity to the Yandex Algorithm 2016 Finals (problem D).

I solved that D problem, but have no idea how that relates to this problem. My codes to those 2 questions have literally nothing in common (even headers are not common xD). Could you elaborate a bit?

Replace

a[i] witha[i] -ito transform problem the non-decreasing variant (this is not a necessary step, everything else may be done even in original statement, but it makes things easier to understand).Consider two DPs:

E[i][x] = minimum penalty for makingi-th number be equal toxandS[i][x] = minimum penalty for makingi-th number be smaller or equal tox. This obviously does not fit in TL and ML, but we will deal with it.We have:

E[i][x] =abs(a[i] -x) +S[i- 1][x] and . Actually this means thatE[i] andS[i] being treated as functions of real variablexare piecewise-linear, convex andSis obviously non-increasing. This allows us to store only the vertices of the plot ofE[x] in map and simply recalculate them inO(n) (with extralognfactor from the map).This may be simply improved to

O(n^{2}) by storing the points not in the map, but in the array, and furthermore, by storing them in some data structure that allows adding a linear function and binary searches (like segment tree or Cartesian tree), the running time may be improved to . The code is literally 40 lines.~~Could you elaborate please? Ternary search for the first value would work?~~UPD: I see it's not enough to determing the full sequence.

Hard Work Today XD

thanks for the nice contest =D

For Div2 A, most of the hacks included the cases when there was no intersection between the time intervals like [1, 2] and [3, 4].

Some other were due to the silly mistakes by the users.

Nice contest though.

Too bad it is going to be unrated .

If it is unrated....Good for me...I got a lot of penalty in B. Misread it completely -_-....BTW it is not helpful if there are too many unrated contests

Why ? those hacks were "due to the silly mistakes by the users."

Interactive problems look fun until you get WA and then you need to write more code to have a chance to find a bug(or spend even more time working as interactor while debugging).

Totally agree!

I think it's better to start with writing your own ask_query function, what should lead to something like this (version after changing it to the submitable version):

How can my solution for 2B be hacked?

https://ideone.com/L9PBla

3

1 1 2

The answer is "YES"

Thanks.

Damn, C was already discussed on CF few times :/. And in xdd. Copy pasted 4 years old code (like probably many people).

yeah there is genius who got it in 4 minutes

Can you provide a link with the thread where it was discussed in O(nlogn)?

I tried to find it right now, but wasn't able to do that. I remember that it was on USACO and someone mentioned super short solution by ecnerwal, but it wasn't sufficient for me to find it :(.

I knew the problem before as well, but not the NlogN solution (just the easy N^2). Can you please explain me the more efficient one or provide a link to some solution? I've been thinking for a while at it and was unable to solve it that fast.

Eid Mubarak Everyone :)

how to solve div 2 E

Can anyone share with me his solution for Div2/C using a trie data structure? My solution using trie exceeded the time-limit I am not sure why.

why not use stl map? trie is difficult to code, maybe you have some bugs

What is your approach to use stl map?

you can also use Array[1<<18] to save the binary system number , and then find the count

That's what i ended up doing :) But at first I tried solving it using a trie and it exceeded the time-limit, but I saw people in the comments here say that their trie solutions passed..

http://codeforces.com/contest/714/submission/20576143

Thank you!

Here is my solution , using trie data structure.

http://codeforces.com/contest/714/submission/20581318

a nice contest

when judge? i am newbee

You'd better go and do something else instead of waiting, because it can be (very) long. :P

it is 2:52 in china.... i want to sleep but i also want to know rating!!!!!!!!!!!!

When will the ratings be updated?

Takes hours at times. Relax. Come back after a sleep.

How to solve Div 2 D, binary search for each corner of each rectangle? I get stuck on finding columns of second rectangle, it is just too many cases? Anything simpler?

Binary search for each edge of each rectangle: http://codeforces.com/contest/714/submission/20603361

What is the intended time complexity in D? I wrote 10^9 solution and it passed pretest in <2s.

And my 10^9 is giving TLE on pretests :(

My solution is

O(N*M*logN*logM)Finally it passed.

I failed to hack someone 3 times on problem B cause he put that :( :(

LOL, should notice it :P

i didn't notice that cause i was in hury :\

It is his loss, not yours.

People regularly put

`#define long long int int`

to disturb hackers.Update : see the comments below. :P

`#define int long long`

actually...Indeed, sorry.

Don't you guys run their codes on your machine at least??????????

That takes too long to copy down. If you mean do that automatically, it's against the rules (and also kinda makes hacking silly as you could script the whole thing).

So, you'll rather lose points than test? Odd....

you cant copy the code you are trying to hack. do not reply to this comment. i know you have never tried to hack.

no of cours it takes so much time

Problem B's constraints are within 10^9, why would long long be necessary?

sorry i mean on problem A

Also notice when in someone's code there is an "if()" which it is wrong he might did this : if();

In problem D, the answer is 0 when there is no valid square i.e the region is empty, which I think should be noted in the statement. And I got WA on pretest 4 due to this issue.

When will the ratings be updated and system testing be done?

What is the solution to div.2 B?

We can make all values equal to either maximum value, minimum value or average of maximum and minimum(if (max+min) is divisible by 2).

get the median of all numbers without repetition store the values of abs(median-v[i]) in set if the size of set greater than 1 then the answer NO else the answer yes

Could you explain me why still am i unrated after finishing Round 370 and 371? I wnat to get my color...

370 was unrated due to server issues. 371's ratings are yet to be updated.

wait for it ..... system testing is still going on!

Thanks ,it's my first time to have contest like this so i needed your opinion

It seems Round 371 is gone from the contest list.

Why does finding max L and min R work in Div2A?

div1 E++: What if the directions can change during the game? (And I mean something better than .)

EDIT: changed "j-i" to "j-i+2", sorry for mistake.

I misunderstood a problem first and tried to solve such a version. My guess was that we should change the input to distances between consecutive owls and then print:

where $S[a,b] = d[a] + d[a+1] + \ldots + d[b]$.

The reason is that numbers in an interval of length

dcan be decreased by onlyd+ 1 owls (other owls will never help because it's stupid to overtake/outrun an other owl). So, onlyj-i+ 2 owls can fight against an interval of lengthj-i+ 1. And there is also a case when we consider a whole interval, what explains in the formula.I don't know if it's enough to print the above formula. And it's quite known how to compute it fast — one must binary search the answer first (and then it isn't hard).

I looked at E at some point in the contest, immediately recognised binsearch (it's quite common in this type of problems with parallel actions) and also misunderstood it as that at first. It seems harder to me than the contest problem — the optimal strategy within the binsearch isn't very clear.

Consider the case where the owls' positions are -2,0,2 with M=11. The optimal answer is 3 when the owl in the middle takes the two chairs next to it. Does that work with your formula? (Your "distances" are actually the number of chairs strictly between two owls, right? And

j-ishould be |j-i| + 1, right?)You test produces distances 1, 1, 6. My formula considers an interval with the number 6 only with fraction , what is correct.

(

j-i) means (j-i)%n, because we are on the circle.In your test I take maximum of 1 / 2, 1 / 2, 6 / 2, (1 + 1) / 3, (1 + 6) / 3, (6 + 1) / 3, (1 + 1 + 6) / 3. Reminder: taking the whole circle is a special case with dividing by

leninstead oflen+ 1.I was confused by the denominator

j-iprimarily because of division by zero. So it'sUnable to parse markup [type=CF_TEX]

according to what you write, or [number of owls in the summed interval including the two border ones].If the distances are 2,4,6, then your formula gives 4, right?

Oh, there should be

S[i,j] / (j-i+ 2) everywhere, I'm sorry for that.I managed to think

j-i+ 1 + 1 =j-i, which isn't really correct.Yes, my formula gives 4 for 2, 4, 6. Is it wrong?

Yeah, it is. You'd need everyone to take a chair in every move since 2 + 4 + 6 = 4·3, so nobody can turn around (the answer to the contest problem would need to be 4). That won't work for the pair with distance 2 and the 2 chairs between them.

Oh, we have two different wrong ways to understand the statement. I thought that a chair is removed and each time we choose to move to one of two neighbouring chairs. While your version has empty places where chairs used to be.

Lol, so this wasn't the actual version -_-? Something is wrong if all of us misread it (either with us or with statement).

The statement is correct, it's probably that people good enough to solve E read statements too quickly and don't notice that step 2 is out of the loop.

Usually numbered list in this kind of problem describes one turn, and it fitted here very well.

Div2 is still going to be rated right?

there are only 28 accepted solutions on E.

Problem C appeared on round 13 (http://codeforces.com/contest/13/problem/C). The only change is the resulting sequence must be 'strictly' increasing, but the idea is the same.

I can't believe this I didn't get a notification that my code on B was hacked I found that out when I was checking my friends standings.

:(

Fun fact: An

O(n^{3}+n*q) solution passed all test cases for D div 1. Bet that wasn't intended.http://codeforces.com/contest/713/submission/20595881

My 10^9 also passed. I think it is almost impossible to distinguish between O(NMlog Nlog M) and such a fast 10^9.

Setting TL to 2s would solve the problem. I can't see any reason for it to be 5s inviting stupid solutions to pass

Decreasing TL will cause some

O(log^{2}) solutions to fail. It isn't true that allO(n^{3}) solutions are faster thanO(log^{2}) ones.I prefer a contest where there is a gradual increase in the difficulty level of the problems....In this way you get a fair judgement. Just my opinion :)

Can we get the editorials ? Also will the contest be unrated ? At least for Div 2, it should be rated I think. My last 4-5 contests on CF have been unrated.

It will be rated. Don't worry.

Hi everyone!

I have a concern regarding problems given, so need your advice...

In a problem A. Meeting of Old Friends it states: The only line of the input contains integers l1, r1, l2, r2 and k (1 ≤ l1, r1, l2, r2, k ≤ 10^18,

l1 ≤ r1, l2 ≤ r2), providing the segments of time for Sonya and Filya and the moment of time when Sonya prinks. Please note on the statementl1 ≤ r1, l2 ≤ r2.However, in the Test #3, in the input given l1 is actually bigger than l2, which should not happen by problem statement.

Test #3: 6 6 5 8 9

It is said that L1<=R1 and L2<=R2 ! In the test case that you gave

L1=6, R1=6, L2=5, R2=8, k=9

Answer should be 1

So, is it rated or not ?

I hope no.

You didn't even participated!!??

UDP.You participated but you're not even showed in my friends standings,is it a bug?

perhaps he(she) was participated with his(her) other account.

Yes it's rated, blog updated!

http://codeforces.com/contest/714/submission/20582567 Submission in python (during contest) http://codeforces.com/contest/714/submission/20597376 Submission in pypy (after contest) Even though both are same codes i got TLE for python and AC for pypy. Can anyone explain why this happens ?? If pypy is very good why is codeforces not removing python ??

For some rare cases Python 2 is faster. And Python is more standard. It is good to have a choice.

http://codeforces.com/contest/714/submission/20597794 -> I used int(i) where i is a digit http://codeforces.com/contest/714/submission/20598043 -> Instead of int i used ord(i)-ord('0') First submission is TLE, but second got accepted both in Pypy. Can anyone explain ?

Does anyone understand how I got this compilation error:

For this submission: http://codeforces.com/contest/714/submission/20581077

I get that println believes it can't be sure what the ternary operator is returning (either an Object of class Integer or int), but I would have thought the ternary operation would resolve first with the associated type. Is this simply not the case?

For Div2C, time limit was 1 second for my submission in python. Is time limit same for all the languages?? If that is the case, isn't it unfair?!!

I thought the time limit given in the problem statement page is for languages like C, C++ etc., and for slower language like Python, Java etc. the time limits are longer. For example, for Python it's around 5x, for Java it's around 2x etc. Could someone please clear my doubt?

I have to say, ur knowledge of languages and their TL is very very bad. First of all, before you participate in a contest, u are expected to know the judge environment and the rules. Do you want somebody to come to ur place and explain to you in detail? And secondly, python is much much much slower than Java, if its 2

xfor Java, its 10xfor Python. Did u get it?My bad! I meant other way round for Java and Python. But I seriously had no idea that all languages have same time limit on Codeforces. Sorry and thanks. Edited my comment slightly.

three 0 rating changes until now... (actually, thanks god I didn't get negative rating change!)

didn't get *

@arsijo and what about the spoiling of the problem......

It's totally unfair to leave it

rated.Why was it unfair? Everybody could google the problem.

Errichto this is sarcasm or what :D

Said someone who thinks that using an already known problem means that

"guy just copies an old codeforces problem and include it as a div1C problem". It was hard to say if you are joking or not.ok sorry

i know you don't mean it ... and i was pissed off there so i wrote "copies" in fact it is not really far from copying

So instead of being concentrated on thinking of problems , we keep searching on google ... I don't think this is the goal of making contests and participating in ....

Nobody said it's good that such a problem was used today.

Actually , It was fair. But it wasn't right and correct. so since it wasn't right, this contest should be

unratedAny hints to improve my python code to Div2 C problem: Details here http://codeforces.com/blog/entry/47095

Please, does anybody have any idea why this code doesn't work? I spent over an hour trying to debug it and even now when I see the test it fails on, I can't figure out what it is. When I enter the second test locally, it works. I`flush`

the output everytime and the code to simulate queries seems fine as well. I also had an assert to check if it doesn't use too many queries and it does not.On your output line 22:

`? 1 2 0 9 -> 0`

Notice

`x2 < x1`

but the task says`(1 ≤ x1 ≤ x2 ≤ n, 1 ≤ y1 ≤ y2 ≤ n)`

Thanks a lot, still not sure where it happens, but a simple if fixes it. Didn't even know that you would get WA for that, but I suppose it makes sense.

In problem D, you pass first 3 pretests if you swap x and y values in input... I think that might be really misleading during contest especially when the order of x and y are nonstandard. Fortunately I had also another bug in my solution xD

I passed the first

ninepretests of E reading n and m in the wrong order. I guess pretests were a bit weak this time around.Div.1 Problem C was new for me and I got accepted it in O(N^2 log N).

My code : 20594137

That was a great round :D Became pupil for the first time. ( another one was decreasing pupil :P ) Thanks round 371 :D

I mean why can't problem setters just google the question before adding them to problem-sets , because no one runs a script to match keywords with problem , people just google it. Its third time i have encountered a similar situation .

1 ) That pythagorean triplet Question, people pasted it from quora link .

2 ) That trie question, copied code from other sites

3 ) Today's problem C

Can someone tell me why does my self made hash function fail in problem c?(AC with SET) http://codeforces.com/contest/714/submission/20599219

Cheers

Could you please tell me why this http://codeforces.com/contest/714/submission/20590906 solution is wrong? Running it in local outputs the correct answer.

Try changing the language to GNU G++14 6.2.0

I will deliver one nonpleasant spank for every problemsetter that denotes rows indices as x and columns indices as y :(.

I am unable to understand problem B div 2. why is the case that if there are only 2 distinct numbers then answer is always yes? also why the condition as mentioned in the tutorial for the case 3?You can choose a number only once so say for example 1 10000000 so i choose 1 then i can only substract or add to 10000000 ,no way we can make these 2 numbers same by choosing any of the number and add or substract from other number.

You don't

haveto always add or subtract numbers. In the case you mentioned, you can add 9999999 to the first number and do nothing to the second. Then, both numbers will be equal to 10000000.is it not necessary to choose from the given array itself?

No,

xcan be any number.Problem Statement Says that

l1 ≤ r1, l2 ≤ r2But apparentlytest case 3is6 6 5 8 9Isn't the problem statement wrong. I got 4 WA for this constraint during contest time. :(6 <= 6 and 5 <= 8 so those constraints are valid.

Nice and relatively easy problems (DIV2s)... brushing up for icpc-2017

Please help me!

here is my code for problem C http://codepad.org/zrZTXOBM

everything is ok in my compiler. but CF shows it's giving output '0' at every testcases!