Привет, Codeforces!
В Dec/28/2018 17:35 (Moscow time) состоится Educational Codeforces Round 57 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ACM ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Роман Roms Глазов, Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Soroush Tabesh Soroush.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | chuochuo | 7 | 222 |
| 2 | Traxex_ | 7 | 270 |
| 3 | quailty | 7 | 281 |
| 4 | hitman623 | 7 | 285 |
| 5 | E.Space | 7 | 316 |
Было сделано 69 успешных и 296 неудачных взломов. Пожалуй, в этот раз обойдемся без таблицы, слишком уж она нерепрезентативна)
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | irkstepanov | 0:00 |
| B | ChiIIi | 0:03 |
| C | Qing_Yang | 0:06 |
| D | aleex | 0:07 |
| E | chuochuo | 0:57 |
| F | isaf27 | 0:19 |
| G | 300iq | 0:06 |
UPD: Разбор опубликован
ggguys i cant wait! !=) X) :)
Second last chance to reach my 2018 rating goals lol.
hello gays i live in a very wealthy part of the austro hungarian empire and i am wondering if the contest will be worthy of my royal time i request you inform my intelligence on whether the contest will be rated or not
you can read the first line it cleary says that is rated for div2 participants/
king_tsar Is this you? lol
looks more or less like me :)
However,I love Educational round.
YESSS...a div2 round for candidates ;)
I hope it would be a great educational
Hope I can become hahalmao555huehuekkkxixi after the contest.
Today I'll become a Christmas mandarin orange.
Good luck! :)
Nickname?
when you learn grammar!
It is "when will you learn grammar!"
No that requires a question mark
XD
One interesting thing in this contest is that both the description and problem name of problem G greatly resembles Problem D in XVIII Open Cup, GP of Urals. But the solution differs a lot, and actually, the solution to that Open Cup problem is more similar to Problem E of this contest. That's why I think the problem difficulty of E,F and G in this contest should be rearranged, with G being extremely trivial once you know FFT, F being some simple calculation once you know the linearity of expectation, and E needs some combinatorics knowledge(like counting in a multiset and inclusion-exclusion principle). And the number of accepted solutions seems to prove me right.
Problem F reduces (at least I reduced) to calculating this sum in small complexity:
Any hints to calculate this?
LOL, LMAO, ROFL. No, it's not solved like that.
Normal solution: there are three kinds of inversions:
LOL, LMAO, ROFL. No, it's not answered like that.
My question is about calculating the sum not how to solve the problem. Anyways, thanks for the solution :P
This is a valid method of calculating the sum in reasonable complexity though, given that it reduces to the same thing (differing by some easy-to-calculate value). You're just counting the same thing in different ways and equating them.
I think you have already figured out how to solve this problem, my reply is too late. :P I was trapped in the same calculation as you. However, after peeking others' solutions, I found it better to calculate the expectation alone, rather than calculate P and Q separately. This problem enlightened me a new angle to calculate expectations. When it is the case that P is hard to calculate, we may try to calculate the expectation directly. Good luck!
First idea and very overkill is next: let
and 
, then your sum is coefficient of zm of a convolution A × B or something like this (if you calculating with modules). Convolution 
FFT.
If you write A and B in closed form as follows:
A = x·z·(1 + z)x - 1
B = (1 + z)y
and then multiply them, then coefficient of zm in A × B = x·z·(1 + z)x + y - 1 would be simply x·C(x + y - 1, m - 1).
Does anyone know why my nlogn solution is timing out?
https://mirror.codeforces.com/contest/1096/submission/47665224
It might be because my distance is linear...but I also tried with Fenwick tree, and still.timeout
It's guaranteed that rating of this topic will never exceed 998244353 (by absolute value).
(OK, it's not really)
number 998244353 everywhere
How to solve G? Is it some sort of bruteforce on small strings + DP? Couldn't figure out the details in time.
Trivial when you know how to accelerate polynomial multiplication using Fast Fourier Transform.
Can you elaborate a bit? Specifically, what are the polynomials you're building and then multiplying? Thanks!
Let polynomial f(x) = a0 + a1x + ... + a9x9, where ai = 1 if i is an available digit and 0 otherwise. Then the answer is sum over the square of every term of f(x)n / 2.
Ah, yeah, that's really obvious once pointed out. Thanks again!
Finally someone wrote a answer that can be understood by every one...
Thanks a lot chuochuo
F is easier than D
How to solve B?
Count length of prefix and suffix such that all characters in the prefix/suffix are equal.
if prefix == n, answer is n * (n+1) /2
if first char == last char, answer is (prefix+1) * (suffix+1)
else the answer is 1 + prefix + suffix
Edit: first case won't happen
https://mirror.codeforces.com/contest/1096/submission/47648603 is it not correct then?
It is wrong due to overflow of int ans. Replace itwith long long, it will be accepte.
I think the first case won't be used, as its given in the question that there are at least 2 distinct characters.
Ah yes good point
can u tell me how u derive the 2nd case?
First char == last char means you have a string that looks something like aaabcaaa
Any way that you split the string will work if it excludes the 'bc'. Consider this:
Choose two bars, one of left of bc, one on right — that represents a substring that you remove. Note that there are p+1=4 bars on each side, p being number of a's on each side. Because you are taking one from each side, the answer is (prefix + 1) * (suffix + 1)
How do you derive the last case?
Say you have this:
Each bar to the left of the "cc" represents a substring that you can remove (from the bar to the right). Each bar to the right is a substring from the bar to the left.
[user:goloins] can you please tell the answer to "aabee" ??/according to conditions mentioned by you answer should be 5 but it is coming 7!!! I may be wrong..hopefully you can point out my mistake
The answer should be 5. The resulting strings are "", "a", "aa", "e", "ee"
is this eduround 998244353?
What was wrong with C? I messed it up :(
It showed me Wrong answer on test 1
But it was correct
Am I the only one who stupidly thought B answer is x*(x+1)/2
I'll take that as a yes
Is D f(i,j) = min ans for prefix i such that starting j letters of hard are taken.
i don't know, but my solution is this rsrs.
Yeah, that dp should work.
I could be missing something obvious but I don't understand why that dp works ? Could you please explain ?
EDIT: Maybe I just dont understand what "starting j letters of hard are taken" means here. Could someone just elaborate on that ?
Minimum cost we can obtain from prefix till index i such that the resultant subsequence contains first j characters from string "hard" in order. Then you can do DP : 47674309
I got WA on test case 4 for problem D, does anyone know what could be wrong 47654263
Me too :( 47654227
Test 4 catches a lot of bugs; from a quick scan of your code, it seems like you made the assumption that the solution must be removing all the occurrences of one letter. This isn't the case. Consider if the string is "harard", where the first a and the last r are very cheap to remove, but everything else is very expensive. Removing those two letters would be the solution.
The general problem is solved using DP.
Thanks! I indeed made that flawed assumption.
Thank you very much for that test case. I also made that assumption but there was no way of figuring that out from test case 4.
the solution for C for god sake?
Multiple of pi(180) which is multiple of alpha angle. Also check that internal angle obtained is greater than or equal to alpha angle.
for every side length k from 3 to 360:
smallest angle = 360/(k*2) biggest angle = 180-360/k
every angle in between is a multiple of the smallest angle. If the angle you're being asked is between the smallest and biggest angle and it is a multiple of the smallest angle, then the answer is k.
please tell the proof regarding "every angle in between is a multiple of smallest angle"
Imagine the polygon as a circle with points on it.
The inscribed angle theorem relates length of curve to the angle. https://www.mathsisfun.com/geometry/circle-theorems.html
The smallest angle represents the arclength between two adjacent points, and every possible angle represents the arclength of some integer * the smallest possible arclength.
thanks buddy :)
no problem bro :)
essentially any regular n sided shape can be placed inside a circle. any angle is the sum of the different smallest triangles that divide up the shape around an arbitrary point. circle geometry states that because some of the angles subtend equal arcs/segments then the smallest angles must also be equal, and hence any angle formed must be a multiple of the smallest angle
edit: ok you responded by the time i send this.
How did u came to the conclusion that all angles in between are multiple of smallest angle?
Math, dude.
I've solved it and here is a link to my solution: https://mirror.codeforces.com/contest/1096/submission/47665926
You may want to read below to understand it.
EXPLANATION:
It's a property from grade 10 (high school) maths.
If you draw a circumscribed circle around the regular polygon, the angle subtended (by any two vertices/arc) at the centre of the polygon will always be double of angle subtended anywhere on the circle.
Here is a youtube link if you want the proof: https://www.youtube.com/watch?v=MyzGVbCHh5M
============ Steps ===========
1) The input needs us to find a suitable "n" for a given query angle "q". What we do is find suitable "n" for angle subtended at the centre of the circle. which is 2* q.
2) But how do we find "n" ?
Total angle subtended at the centre of a circle by any two vertices can be a max of 360 (to be precise, some decimal value < 360). Hence if you have "n" vertices, you can "distribute" this 360 between the vertices.
What I mean by that is that if there are 10 vertices, then every 2 adjacent vertices will subtend 360/10 (=36) at the centre.
To find "n", we need to use a loop , eg: for(n = 3; n <= 360; ++n) Start from n = 3, so that you can get minimum "n" once below condition is satisfied. On finding it, break from the loop.
// NOTE: For this problem, "360/n" must also be an integer. Hence you must // ignore values of "n" if "360 % n != 0"
if( (2*q) % (360/n) == 0 ) {
}
This condition means that if our required subtended angle (2*q) is a multiple of the minimum possible subtended angle for a given "n", then we have found "n" (there is an edge case, see Note below)
=======
FINAL NOTE: There is an edge case in the sample input and output given in the problem statement, the 4th input (178) has output 180, and not 90. this is hard to explain in words but much easier to understand visually. I have commented about this in my solution (linked above) as well. Please see that comment and try drawing it out if you don't follow.
I can't believe I missed the central/peripheral angle thing.
What's test case 3 in C?
Did someone get AC on G with FFT (not NTT)?
Not even with TNT man.
that problem is really hard.
neal did it 47640712
I did it. To avoid precision error, I used the well-known technique that decomposes each integer into two parts. Calculate both on the real and imaginary part to reduce some factors. Basically, it's the template that tourist uses, very well-implemented and works with arbitrary modulos.
These guys are really good :D
Is it that you didn't read problem F and G, or just that you're too weak to learn how to solve them?
well well, look who is a Legendary grandmaster and who is a Specialist now
This user is hoax and the person who hacks his solution needs to be reported or taken down !! https://mirror.codeforces.com/profile/problem_destroyer420 Returns 0 for a particular n and voila hack from another id !
Mind your own GOD DAMN business!!!
Prove that the two accounts have something in common. Basically all you do now is accusing 2 innocent people without any proof. Go learn some programming, green boi
I guess u r subscribed to T Series. Get out of my sight
C had a nice corner case and D was a nice problem in general. Enjoyed the problems, although it seems difficulty for tail end of problems was slightly mis-estimated.
What's the corner case on C?
When
, n should be doubled.
That's because there must be a vertex between a and c.
can u help me with solution for C?
awoo
https://mirror.codeforces.com/contest/1096/submission/47652681
What is wrong with this? In my compiler it shows correct!
The output is just different... if your compiler is not giving the same answer you should make sure they are consistent but I feel it may just be you not looking closlely
Please check in yours. Then you will see
Ok, I got 18 on my compiler too. We must both be using a compiler not like codeforces. The only difference I can think of is the way division happens, with your code, a slight difference could cause floating point errors. If you don't use any doubles you may be able to get the right answer (and it is better to not use doubles anyways, it will likely break on later test cases even with your compiler)
I don't care cf compiler. Make me expert MikeMirzayanov!
You should take care of precision errors. int(x) is a bad way to round a double, since if you get 0.9999999 instead of 1.00000, int(x) returns 1.
what is the best way to round-off whenever needed? Is (int)(floor(x)) always fine?
Firstly, it's always better to work with integral datatypes if it is possible.
And secondly, (int)(floor(x)) is bad because of the same reasons. Typically (int)(x + EPS) works well, where EPS is somewhere around 10 - 9, provided that x is non-negative.
Thanks :)
Maybe your code isn't so robust. Please avoid using doubles if possible. Actually, I think it more important for you to learn how to solve it without doubles. Good luck at Goodbye 2018! Wish you expert next time.
Fake hack: applese hacked __123456__'s submission to problem A. It has a special if for failing on purpose:
https://mirror.codeforces.com/contest/1096/submission/47640777
I got WA on test 4 for problem B, does anyone know what could be wrong 47654945
Integer overflow in line 36.
thanks,but i am a little confuse that why it would be overflow,i think the fr and en should be lower than 2*10^5.
But fr*en will be 10^10 which will overflow
How to solve D?
I assumed that it is optimal to delete only one type of character. Is this assumption incorrect?
DP[i][j] = minimum cost to delete the first 'j' characters of "hard" from prefix i.
That assumption is incorrect.
On problem G. I used Divide and Conquer + polynomial multiplication ,but get TLE However, if someone had used dft & fastpow & idft , he would have AC
My IQ is not enough to figure out the second way(it's 23:30 in China), but these two ways have the same time complexity O(nlogn)
Although I think it is ok not to let me pass, but I'm very sad. With this problem I would become Orange(my current rating is 2097)
TAT
It's just the issue with constant. Well-implemented FFT can pass,too.
D&C + polynomail multiplication is
.
Or did you use some special version of D&C?
No. With the equation
, you can see that 
. Same complexity with polynomial inverse/exponentiation/logarithm and some other operations.
In D&C it's
, if it's implemented just like ''divide the segment into two, solve recursively and then combine answers with polynomial multiplication''.
Yes. But here we are exponentiating a polynomial, and we only need to calculate one half, and the other half is the same, and thus the 2 factor is gone. You can implement it use fast exponentiation just like exponentiating integers. Time complexity is
.
Yes. It's one of model solutions. But Ez3qwq's solution lacks this optimization, so it's TL.
Okay.
I think I know why I TLE
My brain is completely offline Ahhhhhhhh
Problem F is similar to SRM 470 Division 1 — Level Two
I want to check if my code is wrong, so I hack myself.
I write a program in python3 to hack problem C:
but system said "Validator 'val.exe' returns exit code 3 [FAIL Unexpected end of file — token expected (stdin, line 181)]", can somebody help me to solve this problem?
Print 179 instead of 180
range(1,180) is only 179 numbers, since the last value is exclusive. You promised 180 test cases.
I think all cases are included in pretest 3.
For problem G, could someone provide an explanation of how to deal with MOD in fft?
Refer to NTT Ahmed- Link: https://mirror.codeforces.com/blog/entry/48798 You can also deal with MOD in FFT:(See trick number 17) https://mirror.codeforces.com/blog/entry/48417
Thanks a lot, I'll definitely read them.
How can someone hack problem C if they have included all possible values of angle in pretest #3?
For example when someone has an "if (time(0) > x) exit(0);" and time(0) is now greater than x while it was smaller during contest, the solution will fail when a hack is performed now. Example given: https://mirror.codeforces.com/contest/1088/submission/46594591 . Although it's totally useless to have this in your code, it's a possible way to hack C now.
To problemsetters, G is definitely a cool problem. However, do you really think it is suitable for contests rated for Div2? This problem could be easily solved by just copying FFT templates. I think this not fair to the newcomers who has problem solving skills but didn't know much algorithm yet. I think putting these kind of problems in the problemset will cause the rating to be less accurate.
Even though ERs sound like regular Div2 and behave like regular Div2, we (authors) still believe that it's not a regular Div2. That's why we allow ourselves more freedom in using "well-known" ideas (but still trying hard to find a balance).
Of course, it will lead to some disturbance of ratings, but it's a thing we should deal with.
On the other hand, if newcomers wouldn't confront new for themselves but famous in community tasks, they will not learn them. And I think, ER is a perfect place to meet with such tasks.
I agree. If it wasn't for educational rounds, this task would not fit anywhere on Codeforces. It's too easy for Div 1 D/E, and putting it in a regular div2 round seems strictly worse than putting it in a educational round.
In problem A, in the output format it is clearly stated that the answer in the i-th line should correspond to the i-th query but I just saw a submission who has printed l and 2*l in seperate lines but the verdict is ok. Is it actually fine to print it on seperate lines?
It be like that sometimes.
please stop making contests
How to solve F ? Or atleast is there a way to find total number of inversions among all the n! permutations
It's just
. Use the linearity of expectations.
Ok. I now googled and Got it for no of inversions for n!. Any how thanks for replying. But how is that n! * n * (n-1) / 4 ? Can you plz show me the proof or method of deriving it ?
For a single random permutation, 0 inversions is the best case, n*(n-1)/2 is the worst case. Due to symmetry (you can remap i -> n-i+1), the expected value is n*(n-1)/4
For every permutation, you can take it along with its reverse permutation. Every possible inversion happens in either the permutation or its reverse. This implies that the average number of inversions is n * (n — 1) / 4.
how to do C?
Handle ang = 179 separately, n= 360;
(This is because for every angle less than 179, we can attain it using a polygon with no. of sides n <=180)
For other values of ang:
Start with no. of sides s = min(3, ceil(360/(180-ang)))[This checks if the minimum angle possible in the polygon is greater than or equal to ang ] This was derived from, angle of a regular n-gon = (n-2)*180/n;
Now we need to satisfy,
i*ang == j*180; (for some s<=i<=180, and j<i)
(Idea behind this is: ang/180 == j/i; ie "ratio of ang to the total angle of a triangle" should be equal to the "ratio of no of sides opposite of ang to the total no. of sides of the polygon") This can be done by brute-forcing on i and j;
Thus complexity is O(n^3).
Here's my submission.
Let t = gcd(180, ang). Result will be - 1 if ang = 180,
if 
, otherwise 
When you have no idea for C, so you decide to build regular polygons and check all angles between them until you've precomputed the answer for all angles...
Peace on You All :D
I Have a question in "D" Problem .. Why my Greedy Solution is Wrong ?Here
The Idea Is ,
If i delete all character ( 'h' , 'a' , 'r', or 'd' ) it will be impossible to get subsequence = "hard" is that right ? but this is not the all answer the rest is coming
this is how i choose characters to delete character "d" i delete if there is a subsequence = "har" before .
character "r" i delete if there is a subsequence = "ha" before and i will walk to last "d" i choose to delete .
character "a" i delete if there is a character = "h" before and i will walk to last "r" i choose to delete .
character "h" i delete and i will walk to last "a" i choose to delete .
and i will print the Minimum of all that . Why This is Wrong !
I think my solution is similar to yours, however, I find the greedy solution will not work for the following case: "harard", [100, 1, 100, 100, 1, 100]. The minimum cost is 2 when you remove 'a' at 2 and 'r' at 5, and the result string is 'hrad'. It takes me a long time to figure out this, I'm still working on understanding the DP solution after checking the accepted code from others...
Thank you :D
In problem C, that line
print −1 if there is no such nmade me question myself a several times.I have no idea how to solve C , can anyone help how to solve ?
Please refer to this :)
so much math ._.
I think ideally, an accepted problem C cannot be hacked nor fail main tests. As the pre-test 3 checks all possible
1<=ang<=179.In what complexity should E be solved? My O(N*S*2) solution doesn't pass.
can someone explain intuition behind D? i tried some people's solutions and coded them but i still don't fully understand them.
Intuition: Kind of modification of the classic 0-1 knapsack DP problem.
For more clarity please look into my top-down implementation of the same.
thanks!
Glad it helped :)
i don't know why the answer of task 178 is 180, but not 90 on problem C!!!
It is true that you can form angles in increments of 2 with a polygon of size 90. However, the max angle you can form is 176 ((n-2)*180/n).
Build a regular 90-gon and try to find out yourself lmao.
when will you provide tutorials
what meme around number 998244353?
Needed for NTT, one of the solutions for problem G. Specifically, NTT needs that your prime modulo be off the form n*2^k +1. That mod fits. Presumably, they used it through the whole contest to not give too much away.
Can anyone explain the logic of D?
dp[i][j] is minimum ambiguity when we are at prefix j of string "hard". So,we are at state (i,j) and in next index (prefix j+1) comes, we have two choice, either to remove that letter or continue without removing(increasing prefix) and in next index any other letter arrives,we will be in same state. hence transition will be if(next index is next character after j) dp(i,j)=min(dp(i+1,j+1),dp(i+1,j)+a[i+1]) else dp(i,j)=(dp(i+1,j)).
when will be the editorial released?
How to take random result in problem A ???
just print(ans, ans*2)..that's enough since it is the best case and the problemsetter said that it is guaranteed that the answer exist
Can you explain the algorithm of C??
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).
Auto comment: topic has been updated by awoo (previous revision, new revision, compare).