Hi everyone!

Codeforces Round #170 begins soon, and I'll be the problem setter. I hope many people will be happy to solve all the problems.

**UPD:** The scoring is dynamic. The problems are sorted by increasing of estimated difficulty.

And the standard part: thanks to Gerald for his help with the problems, Seyaua and sdya for testing the contest, Delinur for translations, MikeMirzayanov for building the Codeforces platform.

Good luck!

**UPD:** Tutorial

i wish you good luck and have fun ;) =d>

It's also 11.30 here. I'm doing my internship, hope I will not get fired for sleeping at work -.-

http://codeforces.com/blog/entry/6777#comment-123735 are you the same guy ?

it may be one of the way to get positive votes.

Wow, so I'm not the only one? :')

Let's do our best, then.

I hope it will be a good contest! I just have a question, why do Seyaua and sdya have different name, but their image are same??? (i know their family name are same! maybe they are brother!)

They are twins

really fantastic for me!! thanks a lot!!

yes we are twins...

Y U NO stop acting like a potato?

Why did you add potato?

http://lmgtfy.com/?q=potatohead

How can I get positive votes in blogs? Please, help me!!!

Always if you say 'LIKE ME' people will Dislike, because everyone want to harm))

Score distribution is still unavailable :(

4 problems with Score 3k :v Nice contest!

what is wrong with testcase 4 of 2C ???

Perhaps a scenario in which nobody speaks any language?

The result is 5 :)

[sorry ! I just wrote it when no answer was available].

all the vertices have degree 0 so everyone should learn a language !!

maybe like this one

this should be 2 not one

All of the employees know nothing.

last 15mins I have problems with connection to codeforces.

is this only with me or with all?

had no problems

Very FAST system testing @ Div 2!

I've challenged this solution twice during contest time but it returned correct answer

Submission: 3209935

But it failed on similar test case! admins please clarify?

Here is one of my test case:

`100 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100 1 100`

HEY you scrolled your browser only to give him negative votes! :P

HAHA it's more interesting that ppl didn't get lazy votedowning XDXD

now I read problem B can someone explayn why length of answer<=2???

Because not all combinations of 1 or 2 letters can appear at the same time.

Actually It's <=3

No, it's not.

Ah, I thought the length of string is <50! What an epic fail!

in 30 names with length 20 maximum number of consecutive pair elements is 30*19 and number of strings with length 2 is 26^2 30*19<26^2 so length 2 Is enough :)

not good contest! :|

Hard problems but very interesting!

but in this contest the speed of coding was too important to be helpful for coders!

for me, I enjoyed solving div1 B.

anyway I think speed of coding is important part of a good programmer.

The contest was very hard but the system testing was too fast!

Lost 2nd position because of 10 (instead of 1000000). :( It is REALLY disappointing. I was too nervous I think. T_T

That was really fast system testing!

Short editorial for problems I know how to solve (sorry for possible errors):

DIV1-A. Connect persons with common language, then output is max(0, #connected components — 1) + #persons without any language knowledge

DIV1-B. [extracted from rng_58 source code] For case m = 3, n >= 5 there's no solution. m = 3, n = 3/4 one can construct big triangle and a point near one of the points of the triangle. For other cases (m > 3) one can construct (as rng_58 did I think) "function X^2" for one convex polygon (points (i, i * i + LARGE_DELTA)), and "function -X^2" for the rest of the points (poiints (i, -i * i — LARGE_DELTA).

DIV1-C. It can be considered as nim game. For every row/column with coordinates [1 .. maxCoordinate — 1] count the number of "free" unit segments ("free" = not covered by any move played). Let that number be countRow_r for row r, or countCol_c for column c. Then nim sum would be NIM_SUM = (XOR_SUM countRow_r) XOR (XOR_SUM countCol_c). So by the theory of nim game first player wins if NIM_SUM != 0, otherwise second wins. Then we have to find a move which makes NIM_SUM equal to zero, and by the theory of nim games that move exists.

DIV1-E. Construct graph with two nodes u_in, u_out per one node u originally given in the input. Attach the "source" to u_in with capacity 2 and cost 0, attach u_out to the "target" with capacity 1 and cost 0. Then attach u_in to v_out with capacity 1 and cost DISTANCE(u, v) when v can be a child of u (ie. v.y < u.y). Then run min-cost-max-flow and if the flow is n — 1 you can construct the graph and output it minimum cost, otherwise no solution exists.

"number of free segments >= NIM_SUM. It can be proved that such row/column exists."

Not necessarily. You only have to find one such that ("Y" xor NIM_SUM) <= "Y". The other condition would work for some cases but it's not guaranteed to always hold, unlike this one.

http://en.wikipedia.org/wiki/Nim

Thanks, that was my error. I corrected it.

supplement .. .

DIV1-D is a knapsack problem, actually is a

dependency 0-1 knapsack problem, But the dependence is very weak. So we prefer to use agrouping 0-1 knapsack problemmodel to solve this. The expect score is trivial, so let us focus on the penalty. You can found the penalty system in the problem is a little bit different against the reality, that is once we start solving on those large point, we'll never back to solve a small point. This declare is obviosly true.Then, for two large point u, v, let us denoted by (t, f) for time and fail probability.

Simplificate on the formula, Then we could found a large point u is in front of v, iff

Once the principal contradiction is grasped, all problems will be readily solved.

As we want to minimize the penalty, it'll be a wise idea that we use the second dimension of the dp array, record the

maximum expected saveof the penalty.My solution is correct!!!!!! :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@ this failed on system test: http://codeforces.com/contest/278/submission/3214079 and then just added this lines for debug and when i submitted Accepted :/ http://codeforces.com/contest/278/submission/3219530

difference is only :

why it has different answer?

Seyaua

Gerald

You have undefiined behavior in line

`add(s,root[toindex].c[s[strindex]],++strindex);`

arguments can be calculated in any order. For example it can beProbably this one happened. It can depend on compiler and OS.

Also the same compiler on the same OS can reorder the parameters if it finds that to its advantage.

typedef struct node{ int c[255]; node() { for(int i = 0; i < 255; i++) c[i] = 0; } } node;

nooo i initialize all the nodes, none of them mustn't be undefined..... strindex is always less then s.size(); every s[i] is less then 255, c[255];

and it means that if(root[toindex].c[s[strindex]] == 0) is false

and

int ind = root[toindex].c[s[strindex]];

if(ind == 0) that's true :/

`add(s,root[toindex].c[s[strindex]],++strindex);`

may be done as`++strindex,add(s,root[toindex].c[s[strindex]],strindex);`

and may be done as`add(s,root[toindex].c[s[strindex]],strindex),++strindex,;`

One of them is correct, and one not.

fucking compilers :@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@

The problem Standard was A , B , C , E , E :D

Screencast

In div-1 1st prob:pretest 4 could have been avoided to increase successful hacking attempts.

Agree with you!!! the more hacks contest have, the more enjoyable it is!

Контест будет рейтинговым ?

А почему бы ему не быть рейтинговым?

When will the rating update ? If there any problem, please update this blog.

In problem Games, I get WA on test 17. In the test one of the cuts is "2 4 2 3", while the jury's answer is 2 0 2 5. How could it be right?

What's the problem?

If the part 2 3 2 4 was already cut, how can we cut 2 0 2 5? Won't we repeat the edge 2 3 2 4?

As long as you touch some uncut parts, it's fine. (I asked this question during contest time)

Please note that the paper doesn't move during the cuts and you can cut along previus cuts but you have to cut at least one more unit line.

Thanks to both of you :)

I did the same mistake :( I believe this problem should have better definition of cutting even with a figure showing different situations.

Could someone comment on possible strategies for div1-b checker ?

Fit m vertices evenly on a circle with radius R1. Fit the other n — m ones evenly on a circle with radius R2 < R1. This can always be done, except when m = 3 and n > 4, I don't know the reason for this yet though.

You can also create a distribution like this:

http://s16.postimage.org/83zarzh2d/design.png

This will guarantee that you cannot form a polygon whith more than 4 vertices selected from both the first and the second set of points. So, if you have M>3 or if M=3 and N<=4 then the given strategy will provide a good solution.

Thanks for the solution, but I was asking about how the checker would have evaluated the answers. I would like to know what logic did checker apply on the output points so as to verify that maximum convexity is m. (a naive approach of selecting m+1 points and checking will be too time consuming and I am not able to think of a better checker)

My guess about the checker is to run Convex Hull algorithm(O(nlgn)) on your points and see if the output is m or not.

I am sorry I misunderstood your question. My guess for how the checker works for this problem is that it sorts the output points clockwise or anti-clockwise, and then it used a dynamic programming algorithm to find the maximum convexity of the points. If the maximum convexity is equal to M, and there are no 3 points situated on a straight line (which could be verified in N^3 complexity, given that N is no bigger than 200) then the solution is considered correct.

As for the Convex Hull algorithm, I do not believe this algorithm would have found the maximum convexity of a set of points (consider a hexagon inside a square, the convex hull algorithm would say that the maximum convexity is 4, which is not correct) .

You also need to make sure you don't have 3 points at the same line, like here: http://s24.postimage.org/oynvny78l/design2.png I wrote same solution but made this bug during the contest. I took a random distance out of my head between those two simmetric figures, but, as usual, if it is possible to make a bug I will make it:)

My guess about the checker is to run Convex Hull algorithm(O(nlgn)) on your points and see if the output is m or not.

[Edit: sorry I meant to reply to pareshverma91]

First of all, check that no three points lie on the same straight line.

Then iterate over all points, and assume that the

i-th point is the leftmost point of largest convex polygon. Sort all the points to the right ofiby the angle relative to thei-th point.Calculate the following DP: z[t][j] = the maximal size of polygon, where the first point is

i, the last point isj, and the next to last ist(jis always greater thantby the relative angle). We can connect pointsiandjto finish the polygon of z[t][j] points. Or we can find the next pointkto continue building the polygon.kmust be greater thanjby relative angle, and triple (t,j,k) must have positive orientation. This solution isO(n^{4}) in total, but actually it'sC(n, 4). And you can improve the DP to make itO(n^{3}). Code: http://pastebin.com/Ubf25Qq8Fast System test is awesome, hopping rating update be as fast as it .... every contest.

In problem div1-C, the sentence "that is the knife has to touch the part of the paper that is not cut before." is ambiguous. One could understand, as in my case, that the knife can only touch the part of the paper that is not cut before. My submitted solution in contest time was written according to this interpretation. Please, try to be clearer the next time.

I find it clear. In your interpretation, it'd be "cannot touch the part that was cut before" — exactly to remove the possibility of this ambiguity. But if you're not sure, you can still ask an official question — they're answered pretty fast.

I also asked the same question during the contest. Maybe it should have been better to make a public clarification since lots of people asked about it.

The same here ; /. In fact it's our fault, but that's not a good thing when many contestans got the description wrong :d.

I made the same mistake too :(

I think for this kind of ambiguous, one of the best solution is to have it in samples to resolve it.

Samples are not used for testing, but are used for better understand the statement and resolve the ambiguous.

The current samples are already very good that resolved the ambiguous of "it is not guaranteed that the cuts were obtained during any correct game".

Hope it can be better next time.

Why my solution in problem C div2 getting "Ошибка исполнения на тесте 10"?I think everything is OK...but i can't understand why it is giving TLE...PLS help...Here is my code:3214342

You don't get TLE (Time Limit Exceeded), but Runtime Error. Download the test, run in your environment, debug.

Edit: Aha, you can't download the test. But repeat the last full line 30 times and you should get runtime error locally. I did with your prog.

thx for help...but my prog giving true result in my computer...but in codeforces it's giving runtime error...but i don't know why?...

This is the problematic line:

int n,i,j,k,l,f,d,c,ans,cnt,s,t[MN],m;

Don't declare all the letters in advance. You used global variable L, where you should have a local L. Probably your compiler optimized the code incorrectly, not expecting that the value of L could change inside the loop. Actually it is changed inside recurent calls to dfs. Incorrect optimization surprisingly gave expected behavior in your environment. I bet you don't use gcc, do you? What's your compiler?

thx a lot for helping...i accepted it...problem was "l" i think...i took it from global and it got accepted...

Will the editorial be public?

in problem

div 1 C"You are given an n × m piece of paper" "(0 ≤ xbi, xei ≤ n, 0 ≤ ybi, yei ≤ m)" how can be both correct? if 0<=xbi<=n and 0<=ybi<=m than we are given n+1 x m+1 piece of paper no?Also made a screencast: link

Hi,

Is it please possible to have as many rounds in the weekends as possible? For ex, the next div2 round is on monday and i don't see why it was not scheduled on sunday. For people from western europe the 7:30pm from russia is really bad during work days.

Thanks a lot!