Hello Codeforces!

On April 04, 17:05 MSK Educational Codeforces Round 41 will start.

Series of Educational Rounds continue being held as Harbour.Space University initiative! You can read the details about the cooperation between Harbour.Space University and Codeforces in the blog post.

This round will be **rated for Div. 2**. It will be held on extented ACM ICPC rules. After the end of the contest you will have one day to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given **7 problems** and **2 hours** to solve them.

The problems were prepared by Roman Ajosteen Glazov, Adilbek adedalic Dalabaev and me.

We'd like to thank Mikhail PikMike Piklayev and Ivan BledDest Androsov for the help in preparing the round.

Good luck to all participants!

**UPD** Editorial

**UPD2**

Congratulations to the winners:

Rank | Competitor | Problems Solved | Penalty |
---|---|---|---|

1 | dotorya | 7 | 176 |

2 | Um_nik | 7 | 190 |

3 | jtnydv25 | 7 | 532 |

4 | Benq | 6 | 126 |

5 | fanache99 | 6 | 135 |

Congratulations to the best hackers:

Rank | Competitor | Hack Count |
---|---|---|

1 | halyavin | 178:-40 |

2 | algmyr | 113:-1 |

3 | applese | 24 |

4 | pajenegod | 24:-11 |

5 | Black.Monster | 14:-1 |

518 successful hacks and 491 unsuccessful hacks were made in total!

And finally people who were the first to solve each problem:

Problem | Competitor | Penalty |
---|---|---|

A | bazsi700 | 0:01 |

B | MrDindows | 0:03 |

C | dotorya | 0:07 |

D | EMOAIRX | 0:06 |

E | aneesh2312 | 0:16 |

F | dotorya | 0:43 |

G | jtnydv25 | 0:12 |

First!

In codeforces we do not try to claim the first comment as in youtube

We usually try to get higher on ranks :P

Of course, there are exceptions to every rule.

gotem

Also thank you MikeMirzayanov for platforms Codeforces and Polygon?

Wait A & B & C solutions in arabic videos after the Educational

C solution of yesterday contest https://www.youtube.com/watch?v=bvDYHy9ESnY

A solution of yesterday contest https://www.youtube.com/watch?v=CClZZPYJmaI&index=3

Wait us , Thank you.

nice :))

Good luck to all participants!

I hope that all the problems are mathematical.

why?

Because you can't solve mathematics.

I think rated educational rounds are not a very good idea it's unfair that a person solved C&D will be just like who solved A&B :( hacking is unfair in this case .. it should be a full testing system rounds.

You won't have such problems if you'll solve 7 problem. :thinking:

--- 'The greatest enemy of knowledge is not ignorance, it is illusion of knowledge'

That's like saying ACM ICPC is unfair because of it's certain rules (which are used in many contest).

There person who solved C & D instead of A & B (assuming a and b are easier) should just use a different strategy than normal contests.

In ICPC, problems are not sorted according to difficulty. The third and fourth problem aren't necessarily harder than the first two problems.

I believe that the person who can solve C&D can also solve A&B very fast. So, there is nothing to worry.

it's time to change your thinking, and also no one cares what you think.

My favorite sentense -- Watch Tufurama season 3 episode 7 online

full hd freeMen's dream. Not about Tufurama of course.

IT HAS very little Time for me... else i solved all problem ... it make me depressed :(

You can solve them after the contest, but it would be unrated

i can do not participate ... out of contest solving with relaxation ;). its better

Hope

highhacks.Any hints on problem D test case 10?

Are you using float or double in your solution?

Yes, is that a problem?

I was failing test 9 with doubles, but I changed my approach to stay away from floating points and got Accepted so that could be one reason.

Dude I was like how can you answer this question with "Yes". I was thinking like "Are you a male or female?" lol

How to solve problem D

Look at first 3 points. If they are collinear then find those points that don't belong to that line and check if they are collinear. If yes, answer is yes, otherwise no.

If 3 points are not collinear, then you need to pick 2 points (out of these 3) that will maybe belong to the same line. There are 3 combinations, and for each one check if it possible to partition that way(same way as above)

Thanks for replying. But how to check if N points are collinear

see my solution man ! http://codeforces.com/contest/961/submission/36961018 cw function

Check if first second and i-th are collinear

It's a geometry problem. If you want to know if two vector is parallel, you could check if their det is equal to zero. Now we got three point, we can check the det between vector(p1, p2) and vector(p1, p3). Do that with other points you will get the answer:)

see my solution.

If n<=4, the answer is YES.

Else, let's check about first 5 points.

If there are no 3 points set on the same line, the answer is NO.

The points set are exist,you have to use the line because you can use only 2 lines.

Then, you remove some points that on the line and check the left points are on the same line or not.

If I permute the first 4 points, and check collinearity for all the others with at least one of the two pairs( lines) I can make out of the four, I recieve W.A veredict, can any one tell my why is that so?

my source code = http://codeforces.com/contest/961/submission/36973072

pseudocode =

while(permute(1,2,3,4)) for(int i = 5 ;i <= n;i++){ if ( !(check (1 , 2, p[i] ) || check ( 3, 4, p[i]) )){ found =1 ; } if ( found ) puts("YES"); } puts("NO");

Because the first 4 points may be in the same line while the rest may be in another one.

Take for instance

The answer should be yes, but I think you are printing no.

Thanks, u're correct!

Maybe you have to check all 2 points set of 4 points.

for(i=0;i<4;i++){ for(j=i+1;j<4;j++){

//Check using line v[i],v[j]

} }

It seems right, but again you'll need to check the collinearity of the 4 points, if they are collinear, you just have to check if the remaining points are also collinear.

However if these 4 points aren't collinear then ,as you said we'll check all 2 point sets, which is 6 combinations. Then the remaining points have to lie on the lines in any of the combinations.

Correct me if I'm wrong

That's also right.

If the 4 points are on the same line,the line is included in the test.

If n < 4, then

YESYou will try to fix a line and see if all the remaining points lie on the same line.

There are just 3 possible lines that can be formed with 3 different points:

To discover the other line, just take the first 2 points that does not lie in the fixed line.

For each line, go through all the remaining points, they

mustbe inside the fixed line or in the other line.If any of the fixed lines succeeded, then

YESElse,

NOHi, for the last problem, I notice the answer is :

.

I use fft to calculate

S(i,j). However, I get TLE.Is there a faster way ?

You can get a row from fft right not column,Can we??

I was trying some combinatorial argument but I am going wrong somewhere. Can some one help me.First thing is ingore a[i]'s. later we can multiply with sum of a[i].

Using the formula mentioned in above comment and also that we can run i from 0 instead of 1.

My argument is that we are choosing (k-1) nonempty teams from n people(need not be all people) and selecting a captain among remaining people.

So inverse idea is selecting a captain first in n ways and then selecting (k-1) teams from n-1 people(need not be all people ). Now this part is S(n,k). So answer is n*S(n,k)

https://en.wikipedia.org/wiki/Stirling_numbers_of_the_second_kind#Generating_functions

How are you Teja Vardhan Reddy ?

It seems to me, that in formula you are missing size of component in which captain is chosen.

Heyy

i was size of component which translates to choosing captain with my understanding.

Okay, so what I do is this:

To calculate in how many subsets of size j an element can be we use the formula: SS=choose(n-1,j-1)*X where X is the number of partitions of size k-1 of the rest of the elements. Well, let's think of a partition as kind of placing a divider between the elements, we have n-j elements, every divider creates 1 new set and we need k-1 sets so we put k-2 dividers, thus X = choose(n-j-1,k-2).

This approach gets WA on test 7 Could anyone tell me what is wrong with this solution?

Thinking of partitions as kind of placing a dividers between elements is incorrect because in fixed partition subsets doesn't form continous subsegments in general case.

Ohh yes, that went over my head. Thank you for explaining!

Are Hashing and Binary Search the correct approach for problem F or there exist a deterministic solution?

I don't see the way with binary search.

You can precompute the prefix hash values for the given string and its reverse. And then all we have to do is iterate for all the i-string and apply binary search on the answer for the ith value because using hashing we will be able to check the 2 parts are equal or not in O(1).

I think it's wrong. If x is pre-suf it's not mean that x[0,x.size()-2] is too.

Oh yes, I apologize!! I got the mistake. So, do you know the correct approach for the problem ??

No, I dont.

For F, if answer for

k- substring isf_{k}, then note thatf_{k - 1}< =f_{k}+ 2. So, for findingf_{k - 1}start from lengthf_{k}+ 2, coming down and find the largest lengthrsuch that lengthrprefix is the same as lengthrsuffix. Complexity can be proved to beO(n), using a KMP like analysis.If you don't mind, can you please elaborate a little more. Thanks!

What is the idea behind G?

I got that the answer is

Where is the Stirling number of the second kind. How do you evaluate this?

, where

a_{ij}is an indication variable for bothNumber of ways to partition such that

iandjare in the same partition is (consider a new set where (i,j) is merged).It follows that the answer is

My solution: Look at one wi. If it is alone in the set there are S(n-1,k-1) ways of arranging the rest and the weight of wi is 1. Or wi isn't alone. Then first partition the rest there are S(n-1,k) ways of doing that. Then we place wi into one of those set and sum the sizes of these new sets. Together (sum wi)(S(n-1,k-1) + (n-1+k)S(n-1,k)).

Was there a more elegant and faster way of solving E, than with persistent segment trees?

I used a merge-sort tree,

For each season i calculate the number of seasons j in the range(1,min(A[i],n)) with episodes >= i

Sum all the queries for the final answer

good work.

Just process queries offline, use bit.

STL Policy based data structures

I am using a multiset and it is giving TLE in test case 7.

That's because complexity of

`distance`

is linear for multiset.I don't think it's possible to find number of integers >= r in multiset in logn complexity.

I just use a normal segment tree. For each season I store 1 if it contains more series than current threshold or 0 otherwise. I consequently update threshold from 0 to n-1 and so need n updates of the tree total. For each threshold i I ask the sum of the first min(a

_{i}, n) elements.I solved it with "wavelet tree". hope it passes the system test

Hi! I participated for the first time and my two solutions were accepted for Tetris and Lecture Sleep. Where can I find myself with some points earned for this modest but first attempt? I was registered both by FB and my own name. Thanks, Levi

You'll see ranking change after the 24 hours of hacking allowed.

Is hacking in this case attempts to find errors in jury solutions?

No, you can check other peoples solution and try to make them give a wrong answer. This everyone can hack anyone for 24 hours thing is only for Educational Rounds.

OK. And here I have some 825 points for another contest. Does this result appear somewhere? Influences rating or something?

I am just very new here. Thanks

No, you have to participate to the contest to have changes in your rating, which has a specific 2-hours period. You can solve the problems later like you did, they wont affect your rating.

I think that problem D is very similar to BAPC 2016 Preliminaries problem J..

i'm pretty sure i did a somewhat similar problem on codeforces earlier

Maybe this one: http://codeforces.com/contest/849/problem/B

Though it is quite different.

Can someone discribe test 10 of problem D?

maybe floating number problem

I guess that only two points occupy one of two lines. So if we choose to solve the problem by a random algorithm, it will be hard draw the second randomly in the right way. We should pick up two points those weren't be visited before to draw another straight line. And don't pick them up in a random way, either, or you will get TLE.

I knew that problem can be solved by Dirichlet's theorem — solution very nice.While I using if-else

The interesting submissions here from vammadur... put some "hack me" in every test?

Is possible it is another account of vamaddur?

in problem C, a valid chessboard is one which starts with 1st square of white colour right ? or it can start with either and just needs to be alternating.

Oh, f*ck. PS. But why no hacks on C. I checked and both solutions pass the tests.

Funny thing is my random test generator cannot find hack case for odd n. I think for odd n, it doesn't matter.

Can be either.

It doesn't matter because answers are the same. If [a b; c d] is optimal square placement for black lower left corner then [b a; d c] will be optimal square placement for white lower left corner.

Lucky me then....I just searched google for chessboard images and found white first everytime so...

Rated educational rounds are unfair.In this contest I solved B & C but couldn't solve A (couldn't figure out the problem statement correctly) on the other hand my friend solve A & B and he got higher rank than me. -_-

If you were both participating in ICPC. He would beat you, so...

Yeah now I get it. thank you.

Attention! !

What were your approaches for E? I just came up with a solution that followed the lines of: "for every i in N, check in the range [i + 1, a[i]] how many numbers are greater than i", but couldn't find a way to query this fast enough to pass the time limit. Is the idea correct, or what did you try?

I just solved it with segment tree of vectors.for every 'i' I checked how many numbers in the range 1 to min(a[i],n) are greater than or equal to i. 36978334

I used a pretty straight forward segment tree , no heavy data strucutre is really required , just processed the array in reverse order from n to 1 . My code if you need help -->36983745 , code i think is self explanatory but ask if needed.

Weren't there too many smurfs this round, rank 6 to rank 11 all first timers!!

I have a feeling these are fake accounts of Div1 coders. Isn't it illegal to do this? Correct me if I'm wrong. It is really sad that our ranks degrade due to this practice. What can be done?

Probably yes, and yes CF is not happy with multiple accounts.

Please add testcases also in editorial

Can somebody explain the concept of open hacking phase in an Educational Round? In Educational Round, during coding phase we get 'Accepted' and not 'Pretests passed'. What is the meaning of 'Accepted' — does it just mean pretests passed?

It means that you are asked to do the impossible — hack solution that passed

alltests. It is less impossible considering very small number of tests (authors need to reduce server load) in the first problems though.Thanks for the explanation. So you are the expert in doing the impossible.

Because there are no pretests in educational rounds. Those during the contest are the main tests, therefore you get Accepted instead of Pretests passed. However, the data sets are a bit weaker than usual rounds, so instead you're given 24 hours to hack any solutions.

i want hack an answer,because i found the code may be out of bound,but in some test cases,the code can pass ,what should i do?

Try copying the code and running it manually with your inputs..

Thank you, Codeforces!What a nice contest!

Can someone analyse problem E for me ?

Wtf bro? halyavin

Wtf bro? Charge your phone!

Task D. I use line equations ax+by+c=0 to handle vertical lines like others.

Method Contains check whether the point fits the line. In my VS2017 it's ok, but in test system it produces nonzero results.

eps 1e-7 (36991163) wrong at 38 with YES where should be NO: abs(3.725290e-009).

eps 1e-8 (36991294) wrong at 51 with YES where should be NO: abs(-6.984919e-009).

eps 1e-9 (36991945) wrong at 52 with NO where should be YES: abs(-1.036096e-008).

Where is my mistake?

Not using (64-bit) integer numbers for line calculations.

I use double Xc, Yc and Fc. Differences between coordinates (like x2-x1) can be 2e9 which fits 32-bit integer. Where should I use 64-bit integer?

Xc/Yc/Fc should be integers. Then you will need 64-bit integers in Contains.

Eventually I figured out: 37002478. Thank you :)

Can someone help me for D? This is my solution — http://codeforces.com/contest/961/submission/36994056 I get the first line which has 3 points on it and i get the second line by finding the first two points which do not lie on the first line. But i have no idea why i am not passing 24th, maybe i have missed something.

Why so?

Thank you! You are absolutely right. I can just make a random line through the point which is left. It is accepted now after i fixed this and another stupid mistake, but if it hadnt been for your comment, i wouldnt have found the second one.

Problem E is a version of this problem : http://www.spoj.com/problems/KQUERYO/ . Merge sort tree / segment tree with vector

WHEN WILL THE EDITORIALS BE AVAILABLE FOR THE QUESTIONS ?

After SysT

lol~ I'm gonna be BULE thanks to halyavin

cheaters Marcel_Ib && Mugiwara7 in problem E :O :O :O :O

disqualify !! Vovuh MikeMirzayanov

Let's Work Together To Make

CodeForceshave MoreIntegrityِAndHonesty<3Make

CodeForcesClean AgainCan someone explain, why in problem E this code got WA26, while this got accepted? Only difference is that in second code I set a[i] to n when a[i] > n, but it shouldn't change anything except doing a bit more operations add(x, -1) at the end of last for iteration.

May be because if a[i]>=N, you need to push i at ind[N]?

No, N is always greater than n so it doesn't change anything. But I found a mistake, I had add(x, -1) only when a[i] < N what doesn't make sense (it's because at the beginning I had for (x: ind[a[i]]) so I wanted a[i] be less than N), after removing this line it works :)

When rating update will happen for div 2 :(

Guess this is continuation of April Fools Contest XD

And no ranklist yet :P

Why was this round made unrated?

Dunno, I'm a dog. Woof

Where does it say the round is unrated? It clearly says it's rated (for Div 2) in the round description...

But it looks like there is no rating update for this round.

I'm sure there will be an update, don't worry, but it's probably just delayed as of now.

Thanks.

Could you please tell me how long I can get my rank ? This is my second competition！I am so excited!I think cf is a wonderful game !

A classic..

Is it rated?

Rated for div.2. Maybe some technical issues occur, rating updates are delayed.

All of us rn.

so funny

Finally, Ratings are out !!!

Codeforces, thanks for the rating)

After rating updates, many new accounts are removed from the final standing page. (So my rank has been increased a lot.)

Does codeforces use some special techniques to detect multiple-accounts?

I bet they don't use stupid techniques.

I didn't understand the problem E . Anyone please help me :) UPD : Got it