Привет, Codeforces!
В Sep/08/2021 17:35 (Moscow time) состоится Educational Codeforces Round 113 (Rated for Div. 2).
Продолжается серия образовательных раундов в рамках инициативы Harbour.Space University! Подробности о сотрудничестве Harbour.Space University и Codeforces можно прочитать в посте.
Этот раунд будет рейтинговым для участников с рейтингом менее 2100. Соревнование будет проводиться по немного расширенным правилам ICPC. Штраф за каждую неверную посылку до посылки, являющейся полным решением, равен 10 минутам. После окончания раунда будет период времени длительностью в 12 часов, в течение которого вы можете попробовать взломать абсолютно любое решение (в том числе свое). Причем исходный код будет предоставлен не только для чтения, но и для копирования.
Вам будет предложено 6 или 7 задач на 2 часа. Мы надеемся, что вам они покажутся интересными.
Задачи вместе со мной придумывали и готовили Адилбек adedalic Далабаев, Владимир vovuh Петров, Иван BledDest Андросов и Максим Neon Мещеряков. Также большое спасибо Михаилу MikeMirzayanov Мирзаянову за системы Polygon и Codeforces.
Удачи в раунде! Успешных решений!
Поздравляем победителей:
| Место | Участник | Задач решено | Штраф |
|---|---|---|---|
| 1 | Geothermal | 6 | 183 |
| 2 | qpEDop_MuXauJloBu4 | 6 | 216 |
| 3 | hanbyeol_ | 6 | 219 |
| 4 | tute7627 | 6 | 221 |
| 5 | fastmath | 6 | 287 |
Было сделано 69 успешных и 304 неудачных взломов.
И, наконец, поздравляем людей, отправивших первое полное решение по задаче:
| Задача | Участник | Штраф |
|---|---|---|
| A | Geothermal | 0:00 |
| B | Geothermal | 0:04 |
| C | Geothermal | 0:07 |
| D | jayeshaw | 0:18 |
| E | tzc_wk | 0:28 |
| F | jiangly | 0:30 |
UPD: Разбор опубликован
Hoping for a great contest!
Weak pretest of F even do not have cases of disconnected :(
So this is the reason why it was a "good contest" lol
There were disconnected graphs but no ones with a lot of edges. I personally think it was decent enough for pretests.
To be honest, from your solution I'd say it should've been pretty fair for you to assume that it passes only if the tests are weak. Maybe I don't know the estimates on the number or the sparsity of hamiltonian paths in connected graphs, but you do. In that case I'd love to hear why that solution can be fast enough.
It is such interesting. I also don't know why my code can run so fast :D .But it seems to be slow when it doesn't exist a solution (disconnected or do not have a vaild path).I judged them before my programm and can AC now.
There is a lower bound on the minimum possible non-zero number of hamiltonian paths for some fixed n and m. It seems to be somewhere around $$$10^5$$$ for 12 45-48. I guess you are abusing this fact implicitly.
Maybe you'll be able to pass any test within given constraints with more optimizations.
Feel free to tinker with my generator to make your solution (or my tests :P) stronger. It finds connected graphs with the smallest number of hamiltonian paths, spitting out every improvement (or same answer but not too often) into folder "tests". I run it with "./gen n m k 1e5 0.999", these temperature and cool down rate seem to get you nice graphs fast enough.
Thank you all the people who have put in time and efforts in making this contest for us. Upvoted!
what are the score distribution for the individual problems ?? Btw, looking forward to a great contest ahead!!!
+1
What are the score distributions for individual problems?? Looking forward to a great contest!!
bruh its icpc style, every problem carries the same score.
OK DWIGHT!! THANNKS FOR REMINDING :)
Looking forward to losing my newbie virginity to this contest !
Never thought u to be a saint, I believe that u r a slut , haha
Is it just me or half of the trickiest problems am not able to solve during practice are always authored by BledDest.?:)
Looking forward to it!
Same here bro!T_T
Ok, new contest, new story, just gotta give virtual rounds of all contests by this author and that's enough practice. Wait...
This will definitely be another brilliant contest!
Our friends at Harbour.Space don't have any messages for us this time?
Always like Educational Rounds :D
In fact,Educational Rounds is good for our rating :)
To be educated in educational round..
Tbh, Atcoder ABC's are more educational nowadays.
bro you said Atcoder two times. ABC = Atcoder Beginner Contest. Atcoder ABC = Atcoder Atcoder Beginner Contest.
He meant problems A, B, C
Wow so knowledge, much smart.
In my experience with educational rounds, the only 'educational thing' with them is that they are not educational :/
Nowadays participating in ABC contests is helpful for CF edu rounds lol
After a long time, an educational round is going to be held. I hope the problem set will be interesting and contest will enjoy the round.
shinzou WO Sasageyo...!!
What is freedom?
What is love?
Mikasa.... :)
Freedom is an action governed by nothing but your own free will.
what is the lie, what is the truth, what to believe
The truth is whatever lie you choose to believe...
And the truth is that neither of us were able to solve problem C... I choose to believe that if I had some extra time... maybe I could have solved it...
PS: This is what I chose to believe, It's not the truth.. the truth is I couldn't have been able to solve it even if I would have dedicated my complete day on it... but I chose to believe that I could have provided that I just had 1 more hour for it.
factorial and mod disasterrrrrr
They are the true enemy of mankind... They must be annihilated as soon as possible so that the human race may be able to continue for eternity.
This doesn't seem Educational at all. :( Not at all for Div-2 also
Div-2 C :
I too am crying due to the 3rd question... :_)
1st problem : combinatorics
2nd problem : modulo
Meanwhile me :
WA on test 4
AC
I am really tired ... was unable to solve problem C even after struggling for 1.5 hrs straight.
Me after this contest:
Change my organization to "Fool of Combinatorics and Number Theory"
Count me in bro... :_)
the first testcase in C makes the solution obvious
But you also need to be careful with other special situation!
How to solve C?
Let maxi be the index of the maximum element in a, then one of the following conditions must hold for a permutation to be bad.
This logic is easy to come up with...I feel the tough part was to calculate bad permutations using combinatorics
the tough part is to not mess up the calculation and mod correctly
The answer will only depend on the largest number, second largest number, and their respective frequencies. I'll denote largest number as $$$max$$$ and second largest number as $$$secmax$$$. If the count of $$$max$$$ is greater than $$$1$$$, then the answer will $$$factorial(n)$$$ (all possible permutations), because all permutations will be nice in this case. If the difference between $$$max$$$ and $$$secmax$$$ is greater than $$$1$$$, then the answer will be $$$0$$$ (since no permutation can be nice in this case).Now the only case remaining is when $$$max=secmax+1$$$ and count of $$$max$$$ equals $$$1$$$. Here, a permutation will not be nice only if $$$max$$$ is behind all the $$$secmax$$$ in the permutation. So the number of not nice permutations will be $$$nCr(n,(countmax+countsecmax))*factorial(n-countmax-countsecmax)*factorial(countsecmax)$$$. The final answer will be $$$factorial(n)$$$ — ($$$no.$$$ $$$of$$$ $$$not$$$ $$$nice$$$ $$$permutations$$$), which we calculated above.
Could you explain the formula for the number of the "not nice"-permutations?
I just realized that I complicated the formula a bit. Basically, think of the permutation consisting of $$$n$$$ empty spaces. First we need to fill the empty spaces with all the numbers which are smaller than $$$max$$$ and $$$secmax$$$. There are $$$nCr(n,(countmax+countsecmax))$$$ ways to fill the permutation with the smaller numbers and $$$factorial(n-countmax-countsecmax)$$$ ways for the smaller numbers to permute. Now we only have to worry about the no. of permutations of all $$$max$$$ and $$$secmax$$$ in the rest of empty spaces. Since there is only 1 $$$max$$$ and it will be placed in the last of the remaining spaces, we only have to find the number of ways to arrange all $$$secmax$$$, which is $$$factorial(countsecmax)$$$.
Thanks alot for explanation.
I am not able to understand that we have secmax whose count is "countsecmax" ,they all are same value wise, then why are we multiplying factorial(countsecmax) in invalid case.
Lets say we have 333 , so to arrange them we only have 1 way right?
The permutation they have asked for is for the indexes (1 to n) and not the values of the permutation themselves.
Problems were hard.
How to solve D
I missed the registration, but my guess is
prefix sums a pair is convenient only if one point lies on vertical and other one on horizontal OR if both points are on vertical then there's atleast one horizontal line between them OR if both points are on horizontal then there's atleast one vertical line between them. sort the points and check.
Don't downvote if I'm wrong or I cry :(
Just separate the points into two parts one where the x of the point matches with any of the x of vertical roads and other part where the y of the point matches with the y of any horizontal road. these two parts may or may not be disjoint as it is also possible that point's x as well as y matches with any vertical and horizontal road then this point will be the part of both parts.
Now solve the answers for both the parts separately ->
for 1st part Sort it using a comparater which sorts first according to y and then according to x. Now just iterate one by one on the points since the points are sorted using the above comparater so the points will be divided into groups which lie on the same horizontal line(same y) and this group is also sorted according to x also. Now we can see that the vertical roads divides the x axis into some segments. (x0,x1) (x1,x2) (x2,x3) ........
for calculating the answer we will maintain one array f of size (n-1) where ith element represents the number of points that lie in the ith segment and whose y is also less than the current y(on which we are currently at in the iteration).
f[i]=number of points which lie in the segment (x[i],x[i+1]) end points not included.
for finding the segment-number of a point (a,b) we can easily find it using binary search(using lower_bound in c++)
now let us assume we are at a point (a,b) so to find out the pairs that this point will make with other points that are already visited in the iteration we can make use of the array f.
first we find the segment to which the point (a,b) lies and then the bad pairs which it makes is equal to f[segment-number]. because f[segment-number] stores the number of points that lie in that segment in the previous horizontal line (y<b). This can be easily observed that bad pairs are the points which strictly lie inside same segment(end points not included) and which do not lie on the same line.
Now when we move to the next horizontal line (y>b) then we need to add the point (a,b) to its respective segment(increment value of f[segment-number]) so that it can contribute the points which lie on the horizontal line above it.
what we can do is we can maintain a cnt variable which stores the number of points which lie on the same horizontal line and in the same segment of x axis.When we move to next segment then we can just update the value of f[prev-segment-number]+=cnt.
for 2nd part-
Sort it using a comparater which sorts first according to x and then according to y. It's exactly same the difference is just the change of axis now we will iterate vertical line by line and in increasing order of x.Now the y axis is divided into segments.
Link to my code- https://codeforces.net/contest/1569/submission/128325617
Thanx
adedalic vovuh BledDest I recently discovered this youtube channel https://www.youtube.com/watch?v=ScJlgbUDMq4, where solutions of the ongoing contest are being shared. I was not able to solve any problem in this contest since I m a newbie but I also don't go for these unethical ways to increase my rating. Can anything be done against this form of cheating?
These guys now even seem to be crowd-sourcing solutions.
yep, I would be really happy if something could be done against these people
A very heavy meme :
I might go -200 today , I am not losing hopes
My soln 128273615 of F should be hackable. I just have an early exit in case a particular assignment of colors finds a palindromic path. It reduces the time taken from 35s (locally) to 1s (on present test cases). 128279840 takes 30s — 40s locally on a complete graph.
Update: Hacked by pikmike. Accepted submissions would now get TLE on tc 103 during system testing.
Update 2: 128290681 should still be hackable.
Solved C literally a minute after the contest ended damn
If it makes you feel better I forgot take mod of the final answer.
I forgot to use LL for D, and got two WA at testcase 6. After contest finshed I just realized...
Could anyone give me a hint for problem B ?
I thought about using backtracking but could not implement it.
Just try for individual competitions... using brute force suppose there are two players i and j, if any of them is aiming for 1, you can simply draw the match '=', if both are aiming for 2, think... if A has won in any of the previous matches... declare B and the winner and A as the looser, else B as the winner....
In the end just check if all of the players were able to achieve their goals or not... the problem is solved...
This is my submission... ignore everything above //MARK :- SOLUTION=====...
I hope this will help... ;)
128236197
First of all separate all the players who are satisfied with not losing a single match from those who need to win at least one as games need to be won or lost only in the case of the latter.
Now, a valid solution can only exist if the number of unique pairs that can be formed between the players of the second type is greater than the number of players of the second type.
Why?
Because the pairs represent unique games; and we need at least n unique games between n players so that each player can win at least one. These wins can then be assigned in a very simple manner (1-2, 2-3, ..., n-1).
could problem C be solved using combinatorics? i tried below solution but i got wrong answer
----updates---
I got AC. after I use modular inversion when divide it. solution: https://codeforces.net/contest/1569/submission/128287672
in the last case, basically its the number of ways to put the maximum element in any spot while there exists atleast one or more nextMax on it's right side
you can see my submission here https://codeforces.net/contest/1569/submission/128280479
thanks for the sharing. but could you elaborate more? I cannot understand left and right in your solution. or could you provide a related thread for it? Thanks in advance.
Yeah sure, so basically for instance in the last test case n = 6 and there's 3 NextMax so NextMaxCnt = 3 and so we have 2 elements that's less than NextMax, right? if we put the Max(which is 4) at any spot from 1 to 3 there's gonna always be a nextMax on it's right side. So the answer is premutation of the 5 spots (all spots except spot of the Max). now from spot 4 to 6, the answer would be the number of ways to have atleast one nextMax or more on the right side of the Max. There's many ways to calculate this but i calculated it by totalnumber of ways to arrange 5 spots subtracted by number of ways to have NO nextMax on the right side of the max. In my case left is just number of ways to order the left remaining spots on the left and right is the number of ways to have NON nextMax values on the right.
Apologies if my explanation isn't the best.
Thanks for the explanation it helps a lot!
if you still didnt understand it lmk. But basically the idea is to calculate the number of ways to have atleast one or more nextMax on the right side of the Max given that the max can be at any spot. There's many ways to calculate that i assume
Nice problem E. I came up with some backtracking optimizations but couldn't complete it on time :D
Nice set of problems, got the logic for D but found it implementation heavy, it took all my time, and couldn't make code for it.
In E, is it fast enough to do 2^28 * (some big constant) ?
It looked way too slow to me so I didn't code it, but the idea was to brute-force the first three levels of the tournament, bringing the number of contestants from 32 -> 16 -> 8 -> 4, and for the final four to have precomputed in O(32^4*2^4) all the numbers that can be achieved, for every possible quadruple of people playing. (I can see the hash of the first three levels, and substract it from H to get the required hash of the last levels).
How to do E?
For k=5 you just can solve for k=4 (2^15) and get the solution with meet-in-the-middle (2^8).
Oh, so for the "upper" part of the tree and the "lower" part of the tree, and you combine them in the final game where the total winner is determined? Or how do you split it
If you know winners of first phase(16 matches), 16 teams will remain and it's same as k=4 (You can determine places with O(2^(2^k-1)) bruteforce). To determine winners, you can split first 8 matches, and last 8 matches, and combine the results with meet-in-the-middle.
Ok I'm too dumb to understand I'll wait for the editorial
Edit: Ok I understand now, thanks. The 2^8 is, for four possibilities of the first 2^16, who will win, and weather he will win once or twice. And same for the second 2^16, teams from [16,32], who will win and will the winner win again or not.
I tried to reduce the possibilities of backtracking by fixing the sum of eliminated people for every stages. I believe that will be enough to pass the tests in 4 seconds.
C is just abbreviation for crying
It's pretty hard for C, lots of combinatorics
Solved A , but why does a 2 pointer approach to solving it give TLE ?
No fast IO?
I put fast IO and still TLE
never use endl when printing. use '\n' instead.
? Couldn't it be solved in $$$\mathcal O(n)$$$?
Here's the approach:
First, obviously, if all the characters in the string are 'a' or 'b', there must be no solution. Otherwise, there must be a position $$$x$$$ that makes $$$a_x\neq a_{x+1}$$$, scan this string directly to find the position $$$x$$$. The answer is $$$x,x+1$$$.
UPD: AC Submission 128343804
Did this problem really worth time of CM?
All those who cheated in this round I hope you all die due to Covid-19 :).Peace!
I guess codeforces has a good system to detect cheaters
Woah bro, chill, there are way worse people who are still alive than those who cheat in online contests.
when the editorial will come out?
Hi everyone, thanks for the contest I can't seem to figure out what I have done wrong in problem B. If anyone can provide with a test case so I can understand I would greatly appreciate it. Here's my submission: 128271618
Thanks all!
This fails: 1 5 22222
Hey thanks man, just tried it.
I get that it fails, but I can't yet understand why? Do you happen to know?
Thank you
This really took lot of time to debug. The reason you are getting wrong answer is that because in your solution same two players are having a match twice. I'll explain your mistake with this test case 1 5 22222
Explanation: your set initially contains [0,1,2,3,4], after this when you start running the outer loop, these indexes are having a match together 0 4, 1 3, 2 1, 3 2, 4 0
Now since you had a condition that if a player has already played with the same player than next = -1, so in final iteration your next is -1 , because 0 and 4 have already played. And why this is happening is because you are using a set and then erasing, instead you could just use an array or vector and played adjacent players , and last player with anyone except second last. Hoe you got your mistake and this helped!
In problem C, I found the maximum number in the array and if it exists more than once, the answer should be n!. Because they will go to the end of the discussion together. But if there exists only once, We should put at least one maxi-1 in front of this maximum. - If maxi-1 is not in the array we should print 0 - Else we will permutate other numbers:
We will replace other numbers except for maxi and maxi-1 after we have replaced them. Maxi and maxi-1 can be in number_of(maxi-1)! ways. after we have multiplicated them. We will print n! — this.
When the editorials will be published?
And tasks were pretty good.
This is the first contest in which I am able to solve problem B
I made submission of Problem D in contest it gives TLE here.
But After contest is over I submit same solution with no change it is working fine here .
Why this is happening?
I wonder if my TLE solution rerun after hacking is over?
The AC solution is way too close to time limit and +/- 50 ms is expected natural behaviour imo which depends on judging machine. So there are lot chances it might still tle after systest
I have coded the 1st question(That is equal no of 'a's and 'b's) thinking that even finding "ab" is sufficient as they haven't mentioned that the substring should be largest . can anyone please tell me whether I had taken it right because actually I got wrong for that question.
Yeah, it's right, but make sure you're also searching for "ba".
In problen D I tried to calculate count for points between consecutive 2 x-axis-parallel lines, which were grouped by their y-axis-parallel lines. The same works on y-axis. However the answer might always be little different to the Jurys answer. Any situation I missed or over-counted?
128278666
If a point is on the intersection, you should not count it, it adds 0 to the solution. If a point is on an X line, don't count it in solving for Ys, and vice versa.
My sol had taken them into accout, so I think it may be some sneaky bugs.. Anyway, thanks!
That Problem C was simply wow! I did not have this much fun facing a problem in many days. Thank you!
yeah, I also really enjoyed it!
Solution for problem C: First sort array $$$p$$$. If $$$p[n] > p[n-1]+1$$$ then there is no solution. If $$$p[n] == p[n-1]$$$ then every permutation is a solution. The only case remaining is $$$p[n] = p[n-1] + 1$$$, note that a permutation is a solution in this case, if and only if, $$$n$$$ comes before at least one element equal to $$$p[n-1]$$$. It is easier to count the complement and subtract from $$$n!$$$. So let's count number of permutations where $$$n$$$ comes after every element equal to $$$p[n-1]$$$. Let $$$freq$$$ = count of elements equal to $$$p[n-1]$$$. Suppose element $$$n$$$ is at position $$$i$$$ in permutation. Note that $$$i>freq$$$ is necessary. We must choose $$$freq$$$ positions in prefix $$$[1..i-1]$$$ (binomial coefficient $$$i-1$$$ choose $$$freq$$$) to place all elements equal to $$$p[n-1]$$$ and also permute them between these positions. Remaining elements can go in any remaining position. Thus $$$ans$$$ is equal to the sum for all $$$freq < i < n+1$$$ of $$$i-1$$$ choose $$$freq$$$ multiplied by $$$freq! * (n-freq-1)!$$$. Note we can group all factors $$$freq! * (n-freq-1)!$$$ outside the sum. The sum of $$$i-1$$$ choose $$$freq$$$ for all $$$freq < i < n+1$$$ is equal to $$$n$$$ choose $$$freq+1$$$ (Hockey Stick Formula).
The third case where p[n] = p[n-1] + 1 can be simplified. Let freq = count of all elements = p[n-1]. Then answer simply is (freq*fact[n])/(freq + 1)
Please correct me if i am wrong ( may be with an example )
You are correct. We can simplify the answer = $$$\frac{n!}{(freq+1)! * (n-freq-1)!}*freq!*(n-freq-1)!$$$ = $$$\frac{n!}{freq+1}$$$ When we subtract this from $$$n!$$$ we get exactly what you wrote!!
What is the intended solution for D? Are we supposed to do 6-8 binary searches to find the number of elements in some ranges ?
Observations on Problem D: I could not get AC, but I hope the ideas below can help someone. Note that person $$$i$$$ and person $$$j$$$ form an incovenient pair, if and only if, they are on roads of the same type (vertical or horizontal) AND there is a road of the other type between them. Therefore, if person $$$i$$$ stands on both a vertical AND a horizontal road then this person cannot be in an inconvinient pair. We split set of people in $$$2$$$: people in vertical road $$$vert$$$ (sorted by $$$y$$$) and people in horizontal road $$$hori$$$ (sorted by $$$x$$$). We solve for each set separately and sum answers. We consider people in $$$vert$$$ one by one. Suppose we are considering person $$$i$$$. We keep a pointer indicating highest line below $$$i$$$. We also keep a queue of people already considered AND above this line. We keep a frequency array for $$$x$$$ coordinate of people in queue. In each iteration we update line by moving pointer to the right AND pop elements is queue below line. We add $$$queue.size() - freq[i.x]$$$ to answer. Set $$$hori$$$ can be solved in the same way.
You don't need to use queue. You can get an AC by every Time Binary searching as well.
I guess the ideia is the same, both solutions explore Monotonicity. The only difference is in complexity analysis. Using pointers and queue we get $$$O(k*log(k) + k + n + m)$$$ solution because we sort each array but answer each person in amortized $$$O(1)$$$. Using binary search gives $$$O(k*log(k) + k*log(n) + k*log(m) + n + m)$$$ because we sort each array ($$$vert$$$ and $$$hori$$$) and perform binary search for each person in both. Both are ok for time limit.
Yess you are right.
Finally got Accepted on problem D after reading this comment (plus ~2 hours of coding/debug), thanks a lot.
I don't understand why my solution for problem B fails. For 4 2212 (failing 24th test) on codeforces my solution gives
YES
X+==
-X==
==X=
===X
However, on my pc, ideone, and random other compiler my program gives correct output
YES
X+=-
-X=+
==X=
+-=X
What have I done wrong???
Solution for problem B: I will explain a possible construction of solution matrix. If a person wants to not lose any game, then we set all this person's game as DRAW. We store people who want to win at least one game in vector $$$must_win$$$. If $$$must_win.size() > 0$$$ AND $$$must_win.size() < 3$$$ note that solution does not exist. However if $$$must_win.size() > 2$$$ consider array as cyclical and let person $$$must_win[i]$$$ win against person $$$must_win[i+1]$$$. All conditions are satisfied by this construction.
I did exactly that! Except a bit of different way: i marked all 1st type persons as draw between each other, then I gave victory to 2nd type person as soon as possible (and assigning defeat in the correct place, of course), any later game between 2nd types in matrix above the main diagonal is a defeat, below — win. Resulting in a nice right solution. But I dunno why in codeforces last 2nd type person somehow treated as first.
I looked at your code and I think I know what your mistake is. You need to reset your matrix for each test case. A character '+' or '-' from previous test case can interfere with your current test case!!
When you create an array (not a vector) inside your main function, it can be filled with some weird values (its contents are undefined). So, when you try to compare $$$b[j][i]$$$ with some other values, the result of comparison may vary between different systems or even different launches on the same system.
Can anybody come up with a case where my 128251114 for B fails?
Should be:
1 5 12221
Answer says first row has a minus. However, first item is a '1'. There should be no minus on the first row (1 means zero losses).
When would the editorials be live?
After hacking is finished.
Thank You so much for the information.
It was mentioned that this contest is rated...but it is not. I was unrated and still. Please, tell me if there is a problem. Thank you.
You will be rated when the hacking is complete and final standings are published.
In about 12 hours.
You'll be rated once hacking is finished
Thank you. I have earned the rating. However, I want also to ask about my contribution. It is now -1. What does that mean. Thank you.
Video Editorial for Problem C: Jury Meeting
Video Tutorial for Problem C: Jury Meeting
Can anyone tell me why I'm getting RUNTIME error on TEST CASE — 3 My_B_Code
try to use char arr[N+1][N+1] instead of string arr[N+1].
change: string arr[n+1] ; to: //string arr[n+1] ; vector<vector> arr(n+1, vector(n+1));
Can you pls explain why so ??
string arr[n+1] is a 1-D array of string, which is like a 2-D array of characters. However, each string's length is not specified. You are accessing arr as if it were 2-D array of characters: arr[i][j]. Not specifying each string's length is the problem. It works ok only when n is small. When n is bigger, it is not ok.
This code below is similar to the issue, but a bit easier to understand:
Thanks Buddy !
Can problem C be solved in O(1)?
It is obvious that the time complexity of the input is $$$O(n)$$$ .
I meant the solution itself without regard to input, like an $$$O(1)$$$ formula
If you get an algorithm which can solve it in $$$O(1)$$$ time without regard to input , that means you can get the answer without using the input numbers (if you use the input numbers , the time of iteration of the input numbers is greater than $$$O(1)$$$) . So why we input these numbers ?
Can you get the meanings ?
lol, you're right... Confused C with something else, My bad.
There is an O(1) formula but it happens only after you spend 2N time (2 loops of size n each.) More specifically the answer is
n! — (n — cnt — 1)! * cnt! * nC(cnt + 1) where cnt is the number of juries with the second largest number of tasks to tell.
You can refer to my video and the pinned comment for more clarity on the same.
Video Editorial for C
Code demonstrating the O(1) idea
that's great, here is the same idea, but more simplified.
after sorting the array, if last two elements are same, then our answer is n!, means all permutations are nice.
otherwise we can just subtract number of not nice permutations, which is eventually n! / (cnt+1), where cnt is count of second largest element.
so our answer becomes n! — n! / (cnt+1).
Here is my python submission
I see that many of the contestants who have a few wrong submissions before their first correct one have got no penalty. Can someone kindly clarify?
I see a lot of contestants haven't received any penalty for wrong submissions before their first correct one! Can somebody kindly clarify?
MikeMirzayanov adedalic vovuh BledDest Neon
Submissions which fail on the 1st test case don't incur any penalty.
Thanks for your reply! That's advantageous for some but really disadvantageous for many. For example I managed to check if my code passes the sample testcases locally but one of my friend made 3 wrong submissions which didn't pass those. He is ranked better than me.
This is how it is (and should be).
The first test case acts as an example on which you can test your code (and the compiler of your choice, if there are multiple versions).
The question of it being an undue advantage to some users just doesn't arise...
Can anyone please explain why in Problem D sample case 2 does not count 4 and 5 points as inconvenient? Is there anything I am missing here?
Why is education more difficult than ordinary div2 ？
If I am not able to solve C in the next round (probable), it will be a hat-trick.
Hey, why this contest is not rated, even though it is written it will be rated for the participants with rating lower than 2100. Can please anyone explain this? As I am new to the codeforces and this was my first contest..
Be patient, it takes time for the ratings to update.
I guess the open hack is over. But the contest rating has not been updated yet and the editorials as well.
Please be patient, it takes time to update the rating after checking and removing plagiarism
fuck the rubbish contest
Keep calm bro.
The C Problem is such a rubbish,isn't it???
Where's the editorials?
The editorials are somehow a bit slow on "Educational" Rounds . Maybe they want us to think more and be better "Educated" :)
Don't vote me back or I will be sad :(
It may be just a joke :)
Is everyone else rating changed after the contest? My is still not changed and also contest is not being reflected in my rating graph.
Man, this is not your first educational contest, so I am pretty sure you already know how they work. Is it really fun to ask such questions repeatedly? I am also sure that if you scroll a bit before commenting yourself, you will find a similar question, or two.
Lol...it's my first educational round contest
You literally participated in 2 in a row.
Update : I just misunderstood the contest.Sorry to everyone. :(
Where did you hear that?
Maybe the rating changes are yet to be done...
I hope so.
before rating change it shows like this in every contest :)
It will be nice.I admit I am a newbie here.
I realize I just said something stupid.How can I delete it? :(
Come on man, don't lie. I am about to become expert for the first time.
I'm looking forward to be an expert again.
Man,no one will believe in such a fucking Chinese like you!
WTF man , did he do something ?
YES,he lied to us all!
Inb4 you get banned
My solution for problem C is just a formula- if(count(max-1)!=1){ print(fact[n]); } else{ int cnt=count(max-1); int ans=fact[n]*cnt/(cnt+1); print(ans); }
Is this a rated contest?
Please read the comments above :)
A 2 letter Or 3 letter word would be a great answer :)
A scroll up with the mouse will be much better ig :))
YES
When rank is rated :(( ?? I look forward a better rank through this contest hmu
To not keep you waiting, the ratings are updated preliminarily. In a few hours/days, I will remove cheaters and update the ratings again!
The comment every newbie was waiting for lmao.
Wishing +ve delta for everyone :')
Can someone give some strong test cases for D? I thought of every test case I could and stil couldn't figure out the bug in my code.
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).
Contrary to all the comments complaining about problem C, I found solving problem C was very enjoyable. I felt it was a good Combinatorics problem, especially for newbies like me.
When I read the statement I instantly realized that the largest element would always be the last to remain, and the same thing for the second largest element. Thus I only need to pay attention to these two. I then tried permutating the 2 elements to see what would happen if the second largest was before the largest, the largest was before the second largest, etc. I later deduced that:
The first 2 cases could be solved simply by using $$$std::map$$$ or sorting. I did struggle with the last case at first since I couldn't come up with any formula to count, but then I found out I could solve it by counting the opposite case when the permutation was not nice. Let's call the largest element $$$x$$$ and the second largest one $$$y$$$. To start with, I fixed the position of the $$$x$$$, so it looked something like this:
_ _ _ $$$x$$$ _ _
In order to make the array not nice, in the last 2 slots, we should choose any elements other than $$$y$$$. It means that we need to choose 2 numbers from the set of numbers not including $$$y$$$, or $$$P(k, 2)$$$ with $$$k$$$ is the size of the set of numbers excluding $$$y$$$. We can calculate $$$k$$$ by subtracting the number of elements in the array (which is $$$n$$$) by the number of $$$y$$$ and then subtracting it by $$$1$$$ (the element $$$x$$$ itself). But that's not all, we can continue to permutate the first 3 slots, thus multiplying the answer by $$$3!$$$. So the general formula for $$$x$$$ at any position $$$i$$$ is:
With $n - i + 1$ is the amount of slots after $$$x$$$ and $$$n - i$$$ is the amount of slots before $$$x$$$. Little note that when $$$n - i + 1$$$ is larger than $$$k$$$, $$$P(k, n - i + 1)$$$ is $$$0$$$ instead. I prebuilt a factorial array so I could calculate $$$(n - i)!$$$ in $$$O(1)$$$, then I used fast exponentation for the modular inverse needed to calculate $$$P(k, n - i + 1)$$$, making each position $$$O(logN)$$$. Finally I iterated every position from 1 to $$$n$$$, so the total complexity is $$$O(N*logN)$$$.
Unluckily I didn't solve this problem quick enough, so I wasn't able to make a submission before the end of the contest. Still feel pretty bad now :(((
I have earned the rating. However, I want also to ask about my contribution. It is now -1. What does that mean. Thank you.
Well, that means that you are asking questions that were disliked by the community. The contribution is somehow calculated using the numbers of upvotes and downvotes your comments have.
I got it. Thank you
For some reason, it showed plag for a certain question in this contest, they cancelled the contest for me. I'm not that very much concerned about that but are there any further measures?
The comment is hidden due to the large number of negative reviews about it, click here to view it
Its the second time this happened today.