Привет, Codeforces!
4 апреля в 17:05 по Москве начнётся Educational Codeforces Round 41.
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для Div. 2. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. После окончания раунда будет период времени длительностью в один день, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной готовили Роман Roms Глазов и Адилбек adedalic Далабаев.
Также мы хотим поблагодарить Михаила awoo Пикляева и Ивана BledDest Андросова за помощь в подготовке раунда.
Удачи в раунде! Успешных решений!
UPD Разбор
UPD2
Поздравляем победителей:
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 |
Поздравляем лучших взломщиков:
Rank | Competitor | Hack Count |
---|---|---|
1 | halyavin | 178:-40 |
2 | algmyr | 113:-1 |
3 | applese | 24 |
4 | pajenegod | 24:-11 |
5 | _HossamYehia_ | 14:-1 |
Было сделано 518 успешных взломов и 491 неудачный взлом!
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
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 |
Accepted better than pretest passed. :D :D :D
Accepted better than pretest passed :D :D :D
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.
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 free
Men'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 high hacks.
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
Check if first second and i-th are collinear
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.me/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.
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 YES
You 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 must be inside the fixed line or in the other line.
If any of the fixed lines succeeded, then YES
Else, NO
Hi, 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
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 is fk, then note that fk - 1 < = fk + 2. So, for finding fk - 1 start from length fk + 2, coming down and find the largest length r such that length r prefix is the same as length r suffix. Complexity can be proved to be O(n), using a KMP like analysis.
If you don't mind, can you please elaborate a little more. Thanks!
у кого нибудь было WA 9 в D??
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 aij is an indication variable for both
Number of ways to partition such that i and j are 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
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(ai, 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.me/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
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...
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 all tests. 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..
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.me/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.
WHEN WILL THE EDITORIALS BE AVAILABLE FOR THE QUESTIONS ?
After SysT
lol~ I'm gonna be BULE thanks to halyavin
cheaters Al-Merreikh && _Mugiwara_ in problem E :O :O :O :O
disqualify !! vovuh MikeMirzayanov
.
Can 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 :)
Why are the ratings not being updated?
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.
Why is this unrated?
Could you please tell me how long I can get my rank ? This is my second competition!I am so excited!
I'm reloading my profile page since last night for new rating.If last round was unrated,why not they are updating for the same.
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?
Haha, 961B - Lecture Sleep has one of the funniest problem statements I've seen!