Hello, Codeforces!

I'd like to invite you to Codeforces Round #329 (Div. 2). It'll be held on Wednesday, November 4 at 19:30 MSK and as usual Div. 1 participants can join out of competition.

Writers are Stanislav Naumov (josdas) and Roman Korobkov (romanasa). There will be 5 problems and you'll have 2 hours to solve them. I hope you enjoy the problems.

Great thanks to GlebsHP (Gleb Evstropov) for helping me preparing the contest, to Delinur (Maria Belova) for translating the statements into English, to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon.

The scoring distribution will be announced later.

Good luck and high rating!

**UPD:** The round will use the dynamic scoring with 250 points step.

**UPD2:** Editorial

gl & hf!

I'm so sorry, it seems like no one enjoys this problems...

No one except div1 guys and div1 guys with div2 accounts :D

There are even some Div1 contestants that can't solve these problems

hope to see short statement .... and good luck to every one :)

short statements are not always clear , right?

Short Clear Statements*

Shortest doesn't mean the simplest :D

Is there any punishment for those who doesn't write this,"thanks to MikeMirzayanov (Mike Mirzayanov) for the Codeforces and Polygon." in their contest blog???,, Just curious to know..!!!

Look at the previous contest description. It is quite concise and yes, it doesn't include the phrase. So ask Morphy, I hope he is able to answer after that:)

Good Luck!

Does anyone want to guess how long will system testing take? What about rating changes? Hopefully they won't take very long.

is this contest was in gym before :D see tags

Tutorial of ыфф

Announcement of Либо баг, либо фича.

Announcement of Короб лучший

Discussion of Короб не голубой

As I understand anyone can attach any phrase to blog if he creates mashup with this name. :)

Excited!!

My First Contest On CodeForces.

Exited!!It should be

excitedinstead.Sorry for being picky :)

Welcome to codeforces :).Wish you best luck!!!

Why?

And the last 5 link are linked to this page :-| And i can't read russian and is there any one to tell me what does they mean?

It says "You are not allowed to view the contest" when I click on the links. Does anyone one know why?

successful hack

First round from blue coder?)

Color revolution

No, http://codeforces.com/blog/entry/19590

Hello all, why are regular rounds not

scheduled for the weekendif possible? It seems that by moving contests to the weekend, more people (especially students or employees of different time zones) could participate.Thanks, and I hope everyone enjoys this round.

weekend itself isn't a common thing :D

Hope see good translation :3

completing whole contest, hacked on A being like :'D

┬─┬ノ( º _ ºノ)

We learn from our mistakes :)

Am I the only one who thinks its funny that fml stands for f*** my life :p

Sorry romanfml31.

lol. Physics and Mathematics Lyceum. In russian language "fiziko- matematicheskiy litsey"

Haha :D

Nothing H-HUMILIATING about it then ;)

My avatar is about color revolution, I didn't change it just to write a comment ;)

Hey!!! Blue is not humiliating

Actually it means:

ФизикоМатематический Лицей (Physics and Mathematis Lyceum) -> ФМЛ -> FML -> Well :D

Why dynamic scoring :'( why why

What does dynamic scoring mean?

Problems will be sorted by expected difficulty or shuffled?

Problems will be sorted by expected difficulty

But it was random :|

shocked

it seems that "The score distribution will be announced later" better than early announcement with dynamic score :(

we can wait man :D

Best wishes to all participants !

By the way, Soccer fans will be happy cuz there will be European champions league after the contest:)

What about order of problems? Are they will be sorted from easy to hard by authors? Or random?

It's okay too be dynamic scoring, but I hope the round will not be the battle of

speed.short Blog = Long problem :| (I I learned from contest 328)

In fact, why is the scoring distribution "announced later" every time?

The site is quite slow now, my solution was being evaluated for something like 5 minutes and when I want to click on some link it loads longer than it usually takes. I hope this will not be the case during the contest, at least :)

For being good in dynamic scoring contests it is very good to solve first problem B or C but it is a big risk because if you don't solve it fast or wrong then the contest will go on very bad. You can choice to risk or not BUT I THINK DYNAMIC SCORING CONTESTS ARE NOT GOOD FOR TESTING CODING ABILITIES !!!!

If you solve all five problems in any order and in any time I guarantee you will do good in the contest and get a big rating increase.

If you solve all five problems in any order and in any time I guarantee you will do good in the test and get a big rating increase.

Better than lags for all contest.

Как дела?

Вообще четко, жду, как и все.

Delay as expected!!!

10 min delay

OK, I don't participate

Nobody cares.

Thank You :) You just increased my probability of getting a higher rating :D

It's loading really really slowly...

Delay again ????

TC admins are DDOSing CF ^^)

.

Do you guys think its a good idea to participate in a contest when you're sad about something in your life?

I think it is one of the best ways to relax and forget about problems(not CF, problems of life=)).

The delay got me thinking...... maybe today I should pass it....but you guys have a point.

Cf contests makes you forget all your problems and just think about the problem..

No. You won't be focused as you expect.

"Be Obsessed. Do something which you are passionate about. Do it because you love to do it. Everything else is secondary."

It looks like we should donate again.

what an unruly contest!!!:(

dynamic delay

wtf am I doing in this stupid hentai picture?

CONTEST IS BEGINNING LATE! 10 MINUTES DELAY :/

What's wrong?

Not 10 minutes,AlreadY 15 minutes.

AlreadY 15 minutes late. After system testing....................?

delayed why?

The longest delay everrrrrrr. :/

15 min delay. wow

You mean: "as usual Div. 1 participants can join with fake accounts"

Bec that always happens in every Div. 2 only contests

There are more than 750 new accounts participating this Contest!

Many contestants are honorable and participate as "out of competition"

But unfortunately some of them are not!

How cares about that!!! It is their business. I am focus on my own performance.

`delayed 10 mins`

`delayed 5 mins`

Unknown language round?

These Problems should be in Div.1.

Is it div 2 or div 1?? I am confuse.

Div2 contest with Div1 problems :(

what a HARD contest !!!

contest is hard or I very weak :|

Not complaining, but there's a reason why there is a separate category on CF here called Div 2.

A very steep difficulty curve indeed..

Bad contest :|

The worst contest I've ever seen, it couldn't be worse. Sorry for my bed English :(

you mean this ?

div 2 ????!!!!

OMG!!! C problem with 3000 pts

Dynamic scoring.. :/

The new coordinator sucks. :)

What a hard contest! I couldnt solve even problem A completely! This is frustrating and I lost 150 points in resubmissions!! wtf

Respect to Problem C!

How to solve B?

put each line intersecting with line x1 and x2 in a vector pair then sort it and iterator from the begining to end and find the solution.

If you try a brute force method of checking each pair you wont pass because its a O(n^2) algorithm.

Instead of lines think of them as line segments from

X1toX2You have to find the y intercepts at

X1andX2.Create a pair vector of the form {

line_number , X1_Y_intercept}Create another pair vector of the form {

line_number , X2_Y_intercept}Sort them both based on

X1_Y_interceptandX2_Y_intercept.Now

if the ordering of the

line_numberis the same in both vectors thenthere is no intersectionelse

there is an intersectionUPDATE :Since I got lot of upvotes I thought I shall make it clearer by an imageoh and make sure to use long long (unlike me) cuz input may overflow integers

el3el2, and make sure to use doubles cuz input can be decimals too :D

That just means the points of intersection need not be integers. The input is all integers. They just wanted to discourage trying to go through the x-axis checking whether two lines cross at that vertical line.

Thank God that contest has finished

i enjoyed this div-1 contest....!!!!!

I think this contest is like a Div-1 contest.

Not really Div 1 problems are hard but these problems are ugly !

I feel bad for the people who are taking part for the first time. They will probably think Div 2 people are expert programmers after seeing such problems :P

Interesting how you are more concerned about the fact of whether DIV2 coders are expert or not. You are supposed to be worried about the expression it would have on them after a relatively not so simple contest. I think you are a narcissist, egotistical maniac.

That was.. Quick..

Geometry contest ?

NOOOOOOOO. line equation. :)

How to solve B?

I solved x = (b[j]/(k[i] — k[j])) — (b[i]/(k[i]-k[j])) and check if x > x1 && x < x2 and got TLE on test 16.

Something like this (lines[1,...] — k, lines[2,...] — b):

And TLE too...

This is my idea

I have two vectors where I save the interception with x1 and x2 for each line. The tricky part is that I am saving in the vector a pair<double, pair<double, int>> where the first element is the y_intercept value and the second value is a vector with the other y_intercept and the index of this line in the input.

Then, I sort both arrays and for each element from the sorted array, I check if it is the same element. If at position i, there is not the same index line then, we have an interception between 2 lines. If the order in both arrays is the same, there is no interception between any two lines.

I hope this solution passes the systest.

PS:PASSED SYSTEST, LOL!!!!!This Image should explain it :)

try it with long long int :D

Lets hope Arsenal wins today. Its already a bad day after such a hard contest.

beaten handsomely mate

15 minutes delay + dynamic scoring + extremely difficult problems -> a disaster!

Even O(n^2) solution passed B . I lost a few points trying to hack, not cool at all :)

how O(n^2) pass?

it is an old trick. they just check the first 6000 elements... if YES print yes else it prints no (because these tests are made by system).

LOOOL, WHAT.

99% the answer is no when the answer is no in 6000 elements.

so they may TLE in system test?

It's easy to make hacks for those solutions, though.

I made a case where the input consisted of 1e5 parallel lines, but the solution passed in about 850s . However, someone else hacked it using increasing slopes lines.

Mmh I was talking about the "N^2" solutions that only consider first K points for some K.

By the way, take a look at the loop conditions in the submission you tried to hack, specifically the inner loop in solve(): 14073024. It doesn't actually run for N^2 operations on the case you tried.

Looks like the author's two mistakes (doing N^2, but with incorrect implementation) cancelled each other out on your specific test case. :|

no it got TLE

No, solutions that have O(n^2) time complexity didn't pass system test, and it failed also when checking just the first 6000 elements .

If you saw such a solution please link to the submission .

hahahahahahahahahahahahahahahahah

How to solve Problem-D?

Just some thoughts. You can observe that you need to divide Y by at most O(log(MAX_VALUE)) numbers greater than 1. So now

I thinkyou can use HLD to quickly answer queries "Which is the next number in this chain which is greater than 1?". However, I didn't implement that. And a friend of mine told me we can solve it using LCA-like approach (with powers of 2) with union-find but I don't really understand that :DParticipated in div1 in a div2-only contest.

I had never spent this much time on Div 2 B Nice problem :)

What a hard contest:

problem A: harder than usual, took me >10 minutes to solve it.

Peoblem B: Passed pretest with ~0.6 seconds. I'm not sure if python can pass 1 second time limit with full 100K input.

Problem C: Are you kidding? I have no idea how to solve it.

Problem D: I know it's HLD but I never and can't implement it.

Problem E: Time to learn C++! ugh getting compilation error. :p

Seems problem D can be solved by DSU and LCA.

not sure if python solution for B will pass for given time limit. yeah, time to learn C++ seriously.

Even using HLD problem D is very tricky. I thought pre-computing the multiplication of the edges and use HLD but... Xi <= 10^18 :(

The Yi<=10^18,too.Maybe you can limit the multiplication of the edges in 10^18:p

This could be avoided by carefully checking for overflows. Take a look at my solution: http://codeforces.com/contest/593/submission/14073334 (lines 256-258, or ctrl+f "__builtin_smulll_overflow"). I think you could also replace the check

ab≥ 2 × 10^{18}with something like .But yeah, avoiding these kind of overflows is definitely not fun and I think it would have been better to put limits of the form

x≤ 10^{9}instead ofx≤ 10^{18}.:o I didn't know about that function! Thanks :D

Can anyone explain DSU-LCA approach for problem D?

I never thought this solution in contest-time but I'll try to explain:

If node a and node b has edge weight = 1 you can merge node a and node b since multiplying or dividing by 1 has no effect.

Otherwise because edge weight is an integer so number of multiplication or division will not exceed ceil(log(10^18)) = 60 operation. I guess this can be done without LCA(?), just save the parent and depth of a node(?)

You must have LCA. How else could you tell how far should you traverse up the tree?

Edit: My bad — you don't need an LCA.

First observation is that if you keep dividing y, you'll quickly get 0. (Of course, if you divide by a number bigger than 1)

This is the basic idea

This is too slow because of

`***`

part. It's too slow when we have a lot of edges whose value is 1. Basically, we want to skip all edges whose weight are 1.For that we can use DSU.

Initializing... (This must be done before processing query)

Every time you update the cost, we can do the same.

Can anyone please explain why this output is wrong for C:

I consistently got WA in pretest 1 and I think pretest 1 must be the sample.

10 + 0 * (

t- 2) is invalid, it should be 10 + (0 * (t- 2)). Look at the examples under the testcases.You are right.

I'm always right!

You aren't right always, correct is only: (10 + (0 * (

t- 2))) (without spaces of course)I'll go sit in a corner and be quiet now.

Okay, let me see

TodaY most of the hacker are <=300. (Hacked B).

18 solutions for problem C, seriously?

I was not able to solve B :3

this my first div1 contest

How to solve problem D?

Notice that we will pass not more than ~64 edges with something greater than 1 written on them. Therefore, the only thing we need to do fast while travelling on a tree is to pass sequences of edges with 1 written on them (because they don't change your

y_{i}anyhow). This can be done by DSU — merge two adjacent vertexes (u,v) if you get request "write 1 on (u,v) edge, and simply update number on edge if the number ≠ 1. Also you need to update the topmost vertex for this set in DSU. Now we answer on every request by checking if there are more than 64 numbers on path ≠ 1 or by finding all these numbers and consequently applying all the divisions toy_{i}..

I'm dying :D

LOL me too. I was hoping I could hack someone like me. xD

You should have been in my room.

отличные претесты. Можно было что угодно запихать

Delinur please translate to english. :)

hahahahahh .... are you serious :D ?

It is sad, but I have to downvote :(

Don't even care about the system testing. :D

Kudos for problem C! I spent the whole first hour writing my solution, and I'm still a bit worried about the full system tests, but I really liked it. I'm really fond of problems where you have to construct an object that satisfies certain properties, no bullshit 'find the shortest path with a twist' problems, but something you actually have to think about.

EDIT: yay, passed the systests! It also seems my solution finds much shorter answers than the jury solution :)

I tried to use polynomial interpolation on the axes independently, what did you do? I dont understand the part of your code where you are taking modulo 50

I exploited this function: W|A plot. It's zero for all

x≤cand forx>cit satisfiesf(x) = 2(x-c). In other words, this function only becomes relevant after positionc. Let's denote this function byf_{c}(x). If you pick for your functiong(t) =a_{0}+a_{1}*f_{0}(t) +a_{2}*f_{1}(t) +a_{3}*f_{2}(t) + ..., then this function will satisfyg(0) =a_{0},g(1) =a_{0}+ 2 *a_{1},g(2) =a_{0}+ 4 *a_{1}+ 2 *a_{2},g(3) =a_{0}+ 6 *a_{1}+ 4 *a_{2}+ 2 *a_{1}. If you pick your coefficientsa_{i}appropriately, you can reach any even value you want (or equivalently, exclusively odd values if you pick a_0 odd). Since the cirles have at least radius 2, this is sufficient jump into any circle.I also thought about polynomial interpolation but the fact that you couldn't do division was a bit unfortunate.

EDIT: As a bit of background, the idea for this came from the beautiful identities:

max(a,b) = (a+b+ |a-b|) / 2min(a,b) = (a+b- |a-b|) / 2(verify this yourself! hint: consider $a \geq b$ and separately)

It would be great if you could use these functions directly so you could make the step function

max(0,min(1,x-c)), but unfortunately we cannot divide by 2, so this step function would make jumps of size 4. So I dropped the minimum, ending up withfas described above. Then you have to mess around with your coefficients, andpoofyou have a working solution!Nice solution :D I'll try to implement this

Sorry community, I must accept that this round was too hard for div. 2. I will try to better evaluate the difficulty in the future.

I have 1 suggestion for C: Why do you need to have so many brackets? I don't think it is that hard to write judge that works without those extra brackets, but it makes life of contestants much easier.

The problem is already quite hard, and you're making it much harder for contestants that could come up with some complicated functions but failed to insert brackets correctly.

Ok, you should definitely lower Div2 problem difficulty... Problems A and B were excellent. Problem C... i don't even know what to say about problem C. It's difficult to even understand what is asked. Problem D should at least move to most difficult and problem E is for Div1 ...

This is my humble opinion, but i think others will agree.

D was standard HLD. Just the overflows had to be taken care of. But how to approach E?

I think it doesn't need HLD.

May be there are simpler approaches, but what came first to my mind was HLD.

Can you please explain how to solve it without HLD?

How did you approach D? and what is the intended solution of E?

E: (I'm using zero-based index, which is different from problem statement)

This can be solved by dynamic programming with matrix multiplication.

In a nutshell, make a vector V that keeps the number of ways to get to each cell and make a square matrix C such that C*V is the information about 1 second later. And basically keep doing (C^n)*V with some changes on C.

Here is a more detailed solution.

Let f(i, j) = i * M + j. (This maps location (i, j) to an integer, and it's bijective.)

First make a column vector V such that f(i,j)th element has the number of ways to get to (i, j) at some point. Initially, V is filled with zero except f(0,0)th element is 1.(Because we have 1 way to be at (0, 0))

And make a square matrix C whose size is (N*M) x (N*M).

Fill 1 in matrix C such that C*V is going to be a column vector such that f(i,j)th element has the number of ways to get to (i,j) 1 second later. More specifically, for each (i, j), we need to fill C[f(i,j)][f(i',j')] = 1 if you can move from (i',j') from (i,j).

Now to get the information of n seconds later, we just need to calculate (C^n)v. (C^n) can be calculated very fast by using Exponentiation by squaring.

Cats can be handled by changing the elements in C. When a cat shows up at (i, j), every element of f(i,j)th row of C is going to be 0.

Can you explain how to solve it without HLD?

http://codeforces.com/contest/593/submission/14078235

Check it out. :D

Solution without HLD.First observation is that you need to make at most 60 / with numbers >1 to make it 0. I note 1 edges>1 and 0 edges=1.So I want all 1's on path from a to b,if there are more than 60,the answer surely is 0.

So starting from a,b I go to lca and should have a function that gives the first ancestor of x that has 1 to have no more than 60 steps on each query.

The brute force is using disjoint sets.The problem is the updates on edges,but update is of form x[pi] to ci with ci<x[pi].So from a 1 it can be 0 but not reverse,this helps a lot.

Try firstly to do this problem 1D on an array,then it will be similar(just that position x+1 is father(x)).

Complexity O(q*log(max_y)).

If the updates were random,I can do a query in O(60*log^2),does anyone have a better complexity?

System testing please?

lol i wish this contest as unrated

Too hard for me... Only able to solve the first problem.

And failed on the system test..... :(

Maybe stupid question, but how solve A? :)

Try all of the combinations of two letters and check what length of the text we'll have if we take only words with these letters :-)

Count the maximum number of words that can be formed with every pair of letters

I_love_Hoang_Yen didn't solve C :'D and I am expected to?

What is wrong with this approach for B?

Take xi = x1+EPSILON and xf=x2-EPSILON for EPSILON = 1e-7. Find the indices of the lines with the highest value at xi and xf. If these indices are the same, print NO. Else print YES.

Draw two intersecting lines and then draw another one well above them.

seems I miss great contest!

Editorial?

2 solved problems + 2 hacks = 67 place. NICE.

Can codeforces show recent comments at the top instead of bottom of the page. We need to scroll down to find recent comments.

Also it would be best to too negative comment all together as it doesn't serve much purpose on this forum.

Are there any a, b, c such as [[a/b]/c] != [a/(b*c)]?

No. Let be the remainder of after division by , so we have and such that . Then . Now let be the remainder of after division by , so we have and such that . Note that , since . Then , and since , . So .

After that announcement I decided that HLD was bad idea)

P. S. To be honest I didn't even try to implement it.

The thing I liked the most is "Yes" and "No" were case insensitive. :D

Could have had such a good rating ...

Problem B...Failed System Test...changed int to long long int...Got Accepted :'(

I feel the same way with such stupid mistake. On D i have MAX=1e18+1 instead of MAX=1e18 and that made my program fail system tests.

I miss PrinceOfPersia 's contests :D

excellent contest provider ♥

I wonder how many solutions of problem E fails at this test case:

5 4 10000

1 1 1 i*10000 + 100

There is no restriction in the statement that forbids using this test case, right?

I don't see what is special about this case?

Yes there is nothing special about it. It is just an ordinary maximal test case. For instance, your code with that input, gets TLE on custom test.

You are right. It seems either the test cases are extremely weak, or the constraints and restrictions are misleading. Here's a more extreme version of the worst test case:

5 4 10000

(Followed by 10000 lines, i = line number)

1 1 1 i * 200000

I can pass this in 3 seconds but my implementation is heavily optimized. I'm certain most solutions will fail in this case. I got accepted in 156 ms and that's a joke, considering I can generate test cases quite easily where it takes > 3 seconds.

problem D A Big Trouble I use quick_mul to judge the num is exceed 1E18 or not,and this solution has no accuracy error!But someone may use log function to solve the problem,but we know the double only has 15~16 bits of accuracy,but the problem can have 18 bits,so this solution has no accuracy error! When I submit my solution,I get WA.Just a big data,the answer requires 0,but I output 1.But I think whether my answer is wrong.Because if standard procedure use log,I think may the data is wrong because of accuracy! So does everyone know standard procedure uses which method?

This contest was very difficult, but I must admit I overthink problems like B :( always seeing "geometry" problems like demons ...

If I remember it right, this blog should have gotten nearly 70-80 down votes after the contest ! I think you're not alone with the vision

First round from blue coder, they said

Easy contest gunna be, they said :P

Actually the lower rated the coder, the harder the contest. They are just trying too hard.

Some bug in my code for Problem B Anton and Lines, please, thanks you

my submissions WA on test 24

Just change the variables to long long

It's so difficult that those whose scores are around 1700 can only solve the first two problems,and the third problem is so difficult that I don't think it's a successful problem.So sad.

Finally Experted!

hope see you in red ;)

Necroposting may be discouraged by the community, but I trust they'll forgive me for making the very necessary comment that problem C is the most absolutely horrendously disgusting dumpsterfire of a problem in the history of computing, and that the fact alone that there exists a human smart enough to see a solution, yet not smart enough to see the ungodly number of reasons it should have been rejected as a problem idea before being typed is proof enough we do not live in a simulation.

Also the "Incorrect functions" section has a typesetting error in example 3. But I do not recommend anyone dare to fix it, because I am not cruel enough to show such a statement to even my worst enemy, let alone someone trying to be helpful.

That is all--carry on.

it would be funny if they actually corrected the sample