Hello everyone!

Codeforces Round #407 for both divisions will happen on Mar/29/2017 19:05 MSK.

The problems were prepared by me (Ihor Barenblat), Stanislav Stastomash Tomash and Anton arsijo Tsypko. Great thanks to Ivan Fekete Fekete, Adalbert Adalbert Makarovych, Roman pisos_pro Derkach, Vladislav winger Isenbaev and Alex AlexFetisov Fetisov for testing the round, Nikolay KAN Kalinin for his help with the round preparation and Mike MikeMirzayanov Mirzayanov for the Codeforces and Polygon systems.

As usual, contestants will have 2 hours to solve 5 problems. Scoring will be announced closer before the round.

Hope that everyone will find interesting problems. Good luck!

**Scoring distribution**:

**Div2**: 500-1000-1500-2250-2500

**Div1**: 500-1250-1500-2000-2250

**UPD.** Editorial is published.

Congratulations to winners:

**Div.1:**

**Div.2:**

Nowadays number of problem setters+tester of each contests are more than the number of problems :D That's cool. Thanks to all the problem setters for giving their important time in problem setting for us B-)

Yeah! you're right!

My Boy !!! They are not setters ; they are Testers

so, 3 setters and 5 testers? That's also good.

Contestant's are 7000+.... That's awesome

4056 + 461

Hope to have interesting problems and good problem description.

wish high rating for all

now you can see my pokerface

I actually see it is a see-saw and your art gives me an impression that rating have to be balanced in a round, therefore "wish high rating for all" is an illusion.

:|

:|

How many problems？

"As usual, contestants will have 2 hours to solve 5 problems."

thanks！i havn't read the instruction carefully

It already not usually

who is maria ivanova I_love_Maria_Ivanova ?

The most beautiful girl in the world)

Sorry, but Meghana is the most beautiful girl in the world :)

I_love_Tanya_Romanova

All of you are wrong.

I agree.

Thanks!

How about my UNCLES? :'3

All of you are wrong, Rem is the best waifu. /s

but dude! i_love_daniel . And (to round 407) LetsDoThis

i_love_ayrawhsia_nodnat

THEN WHO AM I?

THOSE WHO ARE DOWNVOTING ME JUST REMEMBER THE JOY THIS GIRL GAVE YOU.

I_Love_Vasilina

I will be in top 1000 this contest!

Well I m new in programming contests ... Can you plz tell me that in in which Division should I register.....It will be great if you can give some tips to me .

If you are new, you should register in Div.2

Rating prediction: div1 div2

Extensions:

Have fun & high rating:)

WHY DON'T YOU PARTICIPATE AND CHECK CORRECTNESS OF YOUR TOOL.BTW IT IS AWESOME.Hey, Can you Github it? and share the link, please?

It's already on github. Also you could read blog on cf about it.

Hey, What's the matter with accuracy? Why not accurate when you know the results?

The results of this predictor are very much accurate.

Gotta try it from now, lets see how today's contest rolls up. all the best everyone.

Is a2oj down?

YES A2OJ IS DOWN AS LIKE AS YOUR STANDARDSI believe I can fly.

I BELIEVE, I CAN KICK YOUR ASS.you can‘t kick my son’s ASS！

you are not my father

You can't kick my grandson's ASS!!

THANKS,MY MOM,MY GRANDMA,MY DAUGHTERDid I offend you? Why do you want to kick my ass? Who are you?

I'm you missing Biological father！！！ CALL ME FATHER

DID I OFFEND YOU? HOW CAN YOU FLY?

be quiet please, if you can`t write sth clever

haha, best reply ever :D

Good luck in the competition! Here's a little song to hype y'all up!

Beautiful program

Please run for me.

I've tried you in BASIC,

FORTRAN and C.

Beautiful program,

You've errors galore.

And each time I run you,

You're swapped out of core.

I'll make it as a comment in my submissions during the contest

You are good in programming (as I see your color) but sorry to say, not in literature.

Problems in CSAcademy are getting better than DIV2 CF Rounds. Long Problems, uneven difficulty levels.

Is it at all possible that problem E is just named "New task" because it is a placeholder name :P?

Hack page not loading... Can someone please check?

Problem with the hack page :/

Today we are going to witness the fastest system tests ever .

Hi div2 :V

RIP RATINGS...

What is pretest 14 in div2 B ? Your text to link here... What is wrong in my solution?

Try this:

5 0 4 1

1

I think it isnot this case because my pro can cover this

solution is inf?

inf?

ans is "inf" ?

Ans is "0". Because Masha will stop writing immediately if |

b_{i}| >L.That's exactly why I got WA on the first submission.

Now I got it.. Thanks

my sol is giving correct answer my solution

Ans is infinity.

Because 5 0 0 0 0 0 ... Now 0 is no=t in list...So ans is inf

it think ans is 0 i thought it was inf before i changed it and passed that test and the statement was confusing.

she will firstly write 5 that's bigger than l so she stop and write no number so answer is 0

I want to know too

i passed it by putting

if(abs(b1) >l) cout << 0 <<endl;

at the beginning

thank you , it must be this case

How come? if b1=0 and q=0 then the answer should be infinite!!

the condition has nothing to do with q it just compares b1 and L and if b1 =0 the condition will be false because L is always bigger than 0

if q==-1 && Math.abs(b1)>l then ans = 0; i think this is the case .

I don't know actually, but this case troubled me a lot today :-/ somehow, passed it in 11th submission.

How to solve Div2B. Got stuck for 1 hr.

check for exception cases — q = -1,0,1 and b1 = 0. for others apply naive method.

I got hacked once because of not putting b1=0 case seperately.

@mizuki instead of checking exception cases, we can count iterations here is my code (maybe it will fail in system test):

I did that ..can you check my submission?

i used that but i had wrong answer on pretest 9 .. could some one tell me why ? i thought i did it correctly i did all the cases ?

I tried for q=0,1,-1 and b1 = 0. As well as same way as of iterations count but got pretest 9 WA :(

Try this cases:

5 -1 100 2

1 5

Answer : inf

5 -1 100 2

5 -5

Answer : 0

5 -1 100 2

1 -5

Answer : inf

Just use binary search instead for checking if

b_{i}is 'bad'.or a map :)

What could be Problem B test 14 ?

I think it was abs(b1) > L.

I considered that case too along with q==-1 but still got WA

cannot tell sure, if you got TLE, then it can be infinity test case, for this output may be : inf.

if you got WA, then cannot tell sure what will be the test case#14. Wait until the test case reveal. Luckily i did not stuck in test case 14.

To solve this, i have considered these: test#1 -1 -1 1000000000 1 1 test#2 0 0 1 1 1 test#3 1 1 1000000000 1 0 test#4 125 1 100000000 1 1 For these kinds of test case, output will be infinity.

otherwise,

while(abs(b1)<=l) { if(b1 is not belong to bad integers array) count++; if(abs(b1)==abs(next_b1) && b1 is not belong to bad integers array) output inf, and return 0; if(abs(b1)==abs(next_b1)) break; update b1=b1*q; } cout << count << endl;

How to solve C?

The answer doesn't exceed 1000. But I don't know how to prove it.

If there exists a[i] == n, answer is 1.

Else if we don't have both a[i] < n and a[i] > n, answer is -1.

Else we have some a[i] == n — x and a[j] == n + y. Then we can take y bottles of type i and x bottles of type j. x + y <= 1000.

This >.<

me too :/

Mine is wrong too :(

Masha writes all progression terms one by one onto the board (including repetitive) while condition |bi| ≤ l is satisfied (|x| means absolute value of x).

So if bi>L u don't have to check for 0 too when common ratio is 0.

fail 4 times, which case did I missed?

Stop as soon as bi > l. I too made the same mistake.

Hacks, Hacks everywhere 8-) <3

Is Div1 D solvable by Java? I think the solution needs almost 300000 queries. An Educational Codeforces Round held some month ago has such problem (many queries needed) and no one can solve by Java since flush() is time-consuming.

Codeforces and ACM want people to code in C++, thats why I changed from java to C++ :(

If so, statement must not advice for Java or other languages' flush.

Well I should be doing 1.8*10^5 if that matters. Isn't there another way to make flush?

we can solve it in at most 100000 steps.

fix... my estimation is wrong before...

Can somebody tell, if for div1B suggestion, that 2 used only once edges are neighbour edges, is right?

Any two self loops can also be single edges.

Also any normal edge(non self loop) with any self loop can also form a pair.

is that only 2 cases? self-loops and neighbour edges?

1- pair of self-loops

2- self-loop and edge

3- pair of edges that share an endpoint

Can you please tell me a case where this would go wrong:

sz[i] tells the number of nodes adjacent to node i (not including i even if there is a self loop)

n is the number of edges which are not self loops..

As I said, pairs of self-loop's should be counted

Sorry I don't understand this very statement

pairs of self-loop's...for example:

2 3

1 1

2 2

1 2

My program gives 2, which I think is the right answer too.

Sorry if all this sounds really stupid..

Answer is 3. You can select any 2 of the 3 edges.

Using the two self-loops once the path is 1->1->2->2->1

Thanks.. got it :)

So something like this?

in this test the answer is 3, because you should also count this pair: (first edge,second edge)

I forgot second case anyway, so I got WA. But can you prove that only needed are these three cases ?

Eulerian path/cycle exist if the graph is connected (edge-wise) and degree of all nodes are even except for 0 or 2 nodes are odd.

so if all edges are doubled all degrees will be even, if a pair of edges don't share an endpoint then they will make 4 odd nodes

Fantastic proof, thanks !

I was so close to solve this :)

I did the same. Wrong Answer on pretest 18.

Edit: I messed up in checking whether all edges are connected or not.I did the same solution but I am getting WA on pretest 5 :/

Not necessarily, for example two random self-loops work.

Nope, check the graph 1->2, 2->3, 3->3, and you can use edges 1-2 and 3-3 only once by going 1-2-3-3-2-1.

Awesome problem set! problems was tricky though xD

Pretty nice contest. My most favorite problem is Div2-D. Though, I don't like Div2-B.

Btw, how to solve Div2-E? Is it some kind of DP?

UDP:I don't know if the words "geometric" and "depression" in Div2-B title are intended puns or not.Solve the multivariate linear indeterminate equation? I guess...

The crux here is to notice that all we need is the sum of (signed) distances of the cokes that we include to our desired amount is zero.

Then do we something like Knapsack's DP, except we notice that an optimal solution could be arranged so that we never stray beyond [0, 1000], supposing that we start at the desired amount and then add/subtract the distances from there.

To make it run faster, we implement it using BFS (store the reachable ones in an array that indicated how many steps needed)

"14" it became my worst number because of problem B

aoso to me

Please check this test: 2 0 1 1 0

me too !!! damn that 14 case

Announcement:

are announcements supposed to give hints or only to clarify the statement?

Guess they didn't want people hacking

It is in pretest 18 I think.

Actually, the statement is still incorrect:

Ok then announcement was needed, but I still think it gave hint to some people :D

Div2 B take a lot of time debugging.

And what about div2 B pretest 10?

How to solve Div2 A ?

In Div1 C, I really tried hard to hack O(N^3) solutions. But the CF evaluation server was too fast.. They all worked within 900 ms.

What was the expected solution?

My solution is O(N^2) with BFS.

Wow how did you solve ?

We are to pick some of (a[i]-n) such that the sum of them is zero. We don't need to go to a state greater than 1000 or less than -1000, because for all i, |a[i]-n| <= 1000 and we should make zero. Therefore, BFS with 2001 nodes ([-1000, 1000]) will be enough.

Which test case did you use to hack? As I feel intuitively that if you have a many types of a[i] the answer can be found quite fast and if you have a small number of different a[i] each iteration will have a small number of operations.

Almost all solutions that I tried to hack first check if there is n. If not, they divide numbers into two groups, and calculate available sums for each group with time complexity O(N^3). No matter what numbers come, they iterate full O(N^3) loop. So I handcopied them to custom invocation and just tried K = 1000000.

what the data of DIV 2 B test 8?

please read this : http://codeforces.com/blog/entry/51309

is it means the test data is wrong?

Problem B — Masha and geometric depression It looks like not only geometric who has depression

My Status Right now

[DELETED]

*Thanks for the round

You can't solve it,so you decide that it isn't your fault?

Thanks for the awesome round.I am ok with this round. Sorry for earlier comments.Wrong ideas? I don't understand. If you don't know how to solve it, you can look at programme that have passed

int main() { cout<<100000<<" "<<1<<endl; for(long long i=1;i<=100000;i++) { cout<<10000<<" "; } cout<<endl; }

Used this code to Hack a Div.2 A...why do i get invalid?

last element should not be followed be a space.

I made a hacking attempt with similar script expecting TLE. But the solution passed in 436ms. I guess that was because the operations were small (x++)

I want to see, how many DIV2C solutions will fail due to integer overflow. I managed to hack 4 people in my room alone, who used

`int ans=0;`

. My hack testCorrect answer:

`3000000000`

Can I already post "start systests" meme?

How to solve C ? I used two accumulative arrays where in the first array l=1 and in the second array l=2 (r=n in both arrays), then i looked for max range sum of both arrays. this is supposed to be O(n) but still gives TLE on pretest 10. help?

For Div 2 B,

Whats the correct answer for :

5 0 4 1

5

Main confusion:

Does abs(b)<=l check happen even if b is a bad number?

0

Mine gives

0it should be "inf"

It will be 0.. But if generating doesn't stop, It will be "inf".

you can write down “0” endless，,so it should be "inf"

You should immediately stop writing when |

b_{i}| >lIt should be 0.

0 because 5 > 4, so we never enter the while loop.

0, because of condition b(i) <= l

It should be 0 since initially abs(b1)>l is not satisfied.

So just a side note, not like the statement says the opposite? Really, why didn't you fix that? "At first, he decided to visit all the cities of his motherland — Uzhlyandia." or any other sentence does not even suggest that he may not want to visit all cities, does it?

Also, don't you guys think that "Boy thinks a path is good if the path goes over m - 2 roads twice, and over the other 2 exactly once." isn't well-defined for M=1? I made them tell me that the answer is 0 for M=1 on my third try.

Well u kinda cant walk -1 edge, so.. Kappa. Agreed, statements are awful

Yup, also "the other 2" suggests there are at least two edges. Not only did it take me three tries to convince them to explain the situation with M=1, but they didn't even make an announcement after that...

The English in that statement was also very sloppy at times.

I am in doubt, was their any DIV2 round today?

Yes, this contest was for both DIV1 and DIV2

can some one help me find out what is the difference between these two codes:

and this:

What I've noticed, is that the second code adds the remainder to the answer before dividing it. (wrong)

The first one is adding the remainder after dividing, which is the right way.

`ceil`

will return for example`51`

in case that the computer calculates`100.0 / 2.0`

as`50.00000000000000000001`

... floating point arithmetics are calculated with some machine specified fixed precision...thanks for the reply so you mean that the second one is correct?

Yes.

Division by 2 does not have such flaw since 2 has exact representation. It will break only if the numerator is already not exact, which for integers means it must be more than 2

^{53}.but in case of division by k this has a problem.(based on what others are saying)

I remember I tested it on two integers less than 100 and it failed. I don't exactly remember the numbers.

That is possible only if one of the numbers was already calculated with an error (for example, if you used the

`pow`

function).Here is an old but good TopCoder tutorial by misof to learn about integers and reals representation.

TFW you finish debugging 30 seconds after the round ends

feels bad man

Can someone tell differences between these codes for Div 2 A?

First one passed pretests and second didn't.

Code 1

Code 2.

same here.

I think there might be some precision issue involving doubles.I kept on getting WA on pretest 6.

I think there are some issue in Problem Div2 B. For this reason system test is delayed.

Started..

Here we go :D

Systest is still pending, because even the setters get WA 14 on Div2B :)

Div2.B... 13 is not unlucky number. now, 14 is unlucky number.

Div2 Problem B Case #14: 123 0 21 4 543453 -123 6 1424

Accepted. But A failed :-/

System test are over but div2 B test doesn't seem correct. 14 test case's ans should be inf but it shows 0

Here b1>l. Hence, answer should be 0.

but b2 < l

No. 0 is correct. Because b<l.

Div2 B :

1221pretests passed ->771AC ..May God be with us !!

Div2 B, WA on main test 43 opps :( :(

even though i am not the only one who dissapointed with problem B, but i do appreciate your effort for giving your time to us for making this contest, i'll wait for your next contest of course with a better problem to be solved, graciass

problem B

why output of this case is 0 123 0 21 4 543453 -123 6 1424

it must be "inf" because b1 = 123 will not be printed because it's invalid b2 = 0 will be printed because it's valid b3 = 0 will be printed because it's valid . . . infinity

l is smaller than 123? The process stops at b1. Beware of the difference between "skip" and "stop"

Thank you I got it. It's like the process will not run if the condition |bi| <= l is not satisfied.

123 > 21 ... 0

Auto comment: topic has been updated by I_love_Maria_Ivanova (previous revision, new revision, compare).editorial link is broken edit: fixed

http://codeforces.com/blog/entry/51312

Here's the fixed link

I don't why but there is some issue with the challenging system near the end of the contenst. It seems that my hack page keeps refreshing and it failed to load the hack interface so I cannot hack other's solution...

Surprisingly after I change from chrome to firefox it suddenly works...Don't know why there is a difference between firefox and chrome...

Happiness is getting into Deep Blue.

Congratulations!

System test data for Div-2 problem A are weak. They should test some hack cases too.

Here is interesting submission of Div2 E/Div1 C. It seems to be

O(500^{4}) with some heuristics. I try to find solution using one, two or three types if there is such. If no, then comes what should beO(500^{4}) DP. But it passes systests.Can anyone take a look at THIS submission please? This code gives correct output of the test case 15 on my compiler but wrong ans on codeforces' compiler. Help would be much appreciated. Input case : 3 2 115 16 24 48 12 96 3 720031148 -367712651 -838596957 558177735 -963046495 -313322487 -465018432 -618984128 -607173835 144854086 178041956 .Output should be '1' but on cf it gives me '3'.

Anyone please?? Atleast you can run the code on your compiler with that input and let me know if you get the wrong ans or correct ans. :/

Man !! you don't make your code easy to read.. do you...

Sorry :(

For part A: I initially submitted 25910962 with variables declared globally and I got wrong answer in test 5. But after that I declared the variables inside the int main() and the solution 25923127 was accepted. Can someone explain it to me how this makes a difference?Compare

`ll w[10000];`

to`ll w[n];`

. First one fails, because`n<=10^5`

, but you declare the size as`10^4`

Oh yes. My mistake. Thank you. :)

I can't find any bug in my code,but its giving error on test case 56,How is this possible? (The output on my computer is 1 for this case,but on codeforces it is showing 2,why?) http://codeforces.com/contest/789/submission/25932391

Thanks in advance

For B div 2, shouldn't the following test case output in "0" instead of "inf"?

because b1 = B, and |b1| > L, she shouldn't write anything on the blackboard.

But I might've missed something. The hack attempt is here: http://codeforces.com/contest/789/hacks/312464

Thanks in advance.

Ah, it is my blunder. I misread "expected output" as my own output.

Kindly ignore above question.

In Div2 Prob B test case 14 — 123 0 21 4 543453 -123 6 1424 The output should be inf because First 123 would not be written on the board as it is greater then 21 but 0 should be written as its not present in the m numbers ,So it should have been written every time. But why is the answer 0..? Answer should have been inf

Masha writes all progression terms one by one onto the board (including repetitive) WHILE condition |bi| ≤ l is satisfied. So if |bi| > l she will stop.

Thankyou :) Got it.

No. The question clearly states that the number won't be written if it's absolute value is greater than 'L' and the loop would break. In this case, 123>21. So even that would never be written.

The problem description state that she will write as long as the condition of |bi| <= L holds.

On the test case 14, b1 = 123 is already greater than 21, hence the girl will stop there.

There is a difference between skipping a number (because the number exists in bad number set) and stop writing (because the current number already exceed the given bound).

Thanks for the great contest!

Very clear description and interesting solutions. Unfortunately, I spent half of the time of the contest trying to figure out why my solution for problem C did not work? In the end, a friend told me that the function f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-l while I thought it is f(l, r) = sum_{i=l}^{r — 1} |a[i] — a[i+1]| * (-1)^i-1. Anybody else had the same problem?

I used the following generator code to hack a solution 25904282 for Problem Div2A:

Unfortunately, the attempt became unsuccessful as the solution produced the output in

998 ms.Later during the system test, the same solution gave a TLE on the exact same test case —

Test Case #27:(Such is life...

It's bad idea to hack solutions where only basic addition and subtraction operations are performed in loops.

See this solution. It is performing 10^14 operations still system test passed.

Lol no, this is compiler optimization :D

I have an interesting solution for div1 D and maybe it need only

O(n) queries.First we choose a number number

Gless than , probably (Mis the coordinate range andnis the number of lines). And we can random several times to find a pointa= (x,y) such that .Then, for vertical lines, we query all the point (

x+kG,y) which is in the coordinate range. And we can find several lines. But if there are many lines which are very close, we may only find out some of them.So, the next step, we need to find out the remaining lines. If the dis between two adjacent lines is larger than 2

G, then there are no lines between them. Otherwise, we can search between these two lines. Each time we query the midpoint of the search range, if we get a new line, then we try to search both sides and otherwise, exit.We can find out the horizontal lines analogously.

This is my code 25939395.

During the contest, I made some stupid mistakes and failed to pass it. Sad story.

My solution (25925383) also only uses O(n) queries and is very simple.