Hello everyone!
I am glad to invite you to Codeforces Round #604, which will take place on 05.12.2019 17:35 (Московское время). The round will be rated for both divisions.
Exactly 300 Codeforces rounds passed since my first one (Round 304). I have learned a lot of things here and have much fun in participating in the competitions. Now, I want to contribute to this community by proposing some problems. I hope that you will find something interesting in solving them.
The contest is prepared by me, laoriu, I_love_Hoang_Yen, coordinator isaf27 and CF admin MikeMirzayanov. As usually, we must specially thank to below people who make contest possible:
- MikeMirzayanov for the powerful Polygon and Codeforces system.
- isaf27 for coordinating the round.
- Um_nik, arsijo, _overrated_, kocko, UselessDev for testing the round.
There will be roughly 6 problems in each division. Scoring will be announced later.
GL & HF! See you on the scoreboard.
UPD 1: Scoring
- D1: 500 1000 1500 (1000+1000) 2250 3000.
- D2: 500 1000 1500 2000 2000 2500.
UPD 2: Thanks for participating! Congratulations to the winners!
Top 5 Div1:
- jqdai0815 (unexpected solve all problems quickly)
- tourist
- Radewoosh
- tzuyu_chou
- ksun48
Top 5 Div2:
UPD 3: Sorry for delay, this is editorial.
roughly means subtasks ??
Ask codeforces contest style now. I'm also not fan of it.
Let's talk more about this. You don't have decisive word on this matter? Then who decides it?
As far as I know it is MikeMirzayanov
This is fucked up
Definitely)
Seeing as you haven't been a CF problemsetter, I automatically doubt your knowledge is accurate.
Yes, I haven’t been problemsetter but I have tested many rounds recently.
Fair 'nuff.
Please, don't use the $$$+$$$ sign when you don't mean mixed round, it kinda confusees
Fixed, I just copy old one, didn't notice that. Thanks.
Most problems are nice, recommend to participate :)
That means I won't be able to solve most problems :(
Seems too much motivation for a guy asking others not to demotivate people(for those who dunno the context, see the below comment)
I am really excited then!
Thanks, Alexey, you haven't lied! (Не обманул)
I guess this will be an easy contest for me to achieve my goal of becoming violet.
Your goal is blue not violet.
Please don't demotivate anyone!
Just joke, he is my friend :)
Am I beautiful?
Congrats for +1xx rating. Your dream comebacks now!
Congrats your dream becomes true after years :)
one more amazing contest :))
yeah,i bought some rating from chemthan
It must be difficult and contains a lot of math-based problems =))
I hope you won't call it mathforces
you downvote you gray
mathforces > hackforces > implementationforces/speedforces > bruteforces > 404ces
oh, so many force here. Anyway, may the force be with you guys <3
Mathforces in a nutshell
what does GL and HF mean?
good luck and have fun -_-
Me reading them: what does good luck and have fun mean? good luck and have fun -_-
The writers did awesome job this time — very interesting problems!
I really enjoyed testing this round and I highly recommend to everyone to participate tomorrow.
if i do bad it's automatically because mathforces not because i am bad
Technically how many problems need to be solved to become purple or orange?
At the worst case, you need to solve everything in order to become purple or orange.
Usually, you need to consistently be among the first few hundred placed people in div2 in order to get purple.
You got him wrong, he meant "Please add me to your friends and see me in top ten"
For purple : A + B + C fast enough, Easy D fast
For orange : A + B + C + medium D fast enough, + easy E
at least 4
Have a good round!
As far as I understand there will be sub-tasks in the round, for me personally this discourages any desire to enjoy the round. Because on CodeForces you can simply not solve a more complex subtask, and at this time people who write a simpler solution will bypass you. Yes, I understand that it may be that the subtask is also solved in a non-trivial way, then such a unit has the right to exist, but as I understand it now, it is necessary to add a subtask rather than an interesting division
with all due respect to the author of the round, this most likely refers to the latest trend
Subtask 1's solutions usually are simplified versions of Subtask 2 ones. Like you replace one advanced data structure from the harder subtask with a simpler data structure and then boom you get subtask 1. So don't mind solving easier subtasks because they probably give you hints on harder subtasks.
You probably didn’t follow my thought, if this is a cool subtask, then of course, but now it’s like a TREND and there is a chance that the subtask is solved simply
why my contribution went from 41 to 31 by itself :/ anyone knows ?
Focus on your rating instead of contributions
it's not that I care that much about contribution but that's weird
It's called decay. Older blogs and comments give a smaller part of the contribution.
It means your rating goes from 1441 to 1431 -_-
And me pupil again
Why no registration possible?
My mood is not beautiful.
constructforces :v
.
Hard to focus on tasks while thinking about this
Neir:Automata <3
How to solve div.1 E ?
Minimise sum of squared outdegrees, I guess.
Basically, any triple of vertices is either a cycle or there's one vertex with edges into the remaining two (while neither of them has edges to the other two, obviously). The number of triples with cycles is the total number of triples minus the number of such pairs of edges, which is $$$N(N-1)(N-2)/6 - \sum outdeg_i(outdeg_i-1)/2$$$.
Nice D2 1000
My summary of the contest: Phew.
For me contest was hard, but problems were interesting. How to solve div2D(div1B)?
Notice that because of $$$|A_i - A_{i-1}| = 1$$$ condition, consecutive numbers can't have the same parity and hence $$$|cnt(even) - cnt(odd)| \le 1$$$
Next step is to handle 2 more cases $$$\text{assuming 0-indexing}$$$:
N is odd: if $$$cnt(even) - cnt(odd) = 1$$$, fill even positions with 0s then 2s and odd positions with 1s then 3s and vice versa when $$$cnt(odd) - cnt(even) = 1$$$
N is even: try starting with both evens and odds
Check if the array satisfies the conditions and print if it does
Thanks!It helped!
Actually it can be solved in greedy approach.(in case nobody mentioned it before) the answer can start with either the smallest number or the second smallest number, try both of them. When filling a new digit $$$a_{i}$$$ , it could be either $$$a_{i-1}-1$$$ or $$$a_{i-1}+1$$$, try $$$a_{i-1}-1$$$ first, if you don't have more $$$a_{i-1}-1$$$ then try $$$a_{i-1}+1$$$, if you dont have it neither, then stop.
Hopefully you can understand it cuz my english is not good enough.
Thanks!
1.Take a deque. 2.insert 0 if a>0 or insert 1 if b>0 or insert 2 or 3 using the previous condition for each number. 3.Now you have a head and a tail in the deque. 4.Then you continue pushing the remaining element.if its absolute difference with the tail element is one then push the element in the back of the deque. If it cannot be pushed to the back check whether it can be pushed in front. 5.if you have a+b+c+d>0 and you dont have any opportunity to push a new element you can break and print no.Otherwise the answer will be Yes and print the deque.
How to solve probability question?
Expected days ( x )= sum of p[i]*number_of_days_passed
x= (1-p[0])*(1+x) + p[0]*(1-p[1])*(2+x) + .... + p[0]*..p[n-2]*(1-p[n-1])*(n+x) + p[0]*p[1]*..*p[n-1]*n
solve the equation for x under modulo, p[i] being the probability ( after dividing by 100 )
The meme of your account photo is so compatible with the picture.
EXACTLY THE SAME PROBLEM WITH E Sadly, I didn't know before contest ended..
This problem too had almost the same idea. Too sad, I couldn't participate today :(
much much earlier one in CN Winter Camp 2007.
Congrats on a #1 finish :D
Try to sound chinese
wxhtxdytxdy
So, what is a "normal" way to implement B?
(I did something very horrible: assume the string is of the form $$$(2)^e (3\, 2)^f (3\, 2\, 1)^g (2\, 1)^h (2\, 1\, 0)^i (1\, 0)^j (1)^k$$$; try values of $$$e, k, i$$$ and deduce the rest from those. Then handle special annoying cases.)
I implemented it by trying all possible values of first number. Then, if the last number is 2, always prioritize going to 3 over 1 and if the last number is 1, always prioritize going to 0 over 2.
I am happy I did the same way! :D
Came out with the idea. Just slight late and couldn't implement.
can you please give proof of correctness of your solution? why does prioritizing works here? I got accepted by your method but still don't know why it's correct :(
Divide numbers into 2 groups (0, 2) and (1, 3). We can see that all numbers in each group will be put at either odd or even positions only. So we only have 4 possible adjacent pairs: (0, 1), (0, 3), (2, 1) and (2, 3). The only invalid pair here is (0, 3) so our strategy would be keep them as far as possible. Hence, we can arrange group (0, 2) like this: 0 0 ... 0 2 2 ... 2 (put all 0s to the left). For (1, 3) it is: 1 1 ... 1 3 3 ... 3 (put all 3s to the right). The first number can be either 0 or 1 and you can fill the following one using above strategy. Then just check if it is a valid sequence.
My solution is like:
Try to see what the finally path look like: First it will be ...->odd->even->odd->..., i.e. alternating parity. Also 0 and 3 can not be adjacent. So just put 0 as early as possible and 3 as late as possible, and fill in the rest of the positions.
Upd: There are actually two cases. If you have a sequence starting with an odd number, you should put 3 as early as possible and 0 as late as possible; otherwise, it is just what I mentioned above. Sorry for the confusion.
Do you accomodate for strings like 101012121232323212101 ? [3,8,7,3]
You don't need to put these 3-s in the middle: you can do something like 101010121212121232323.
I tried this, did not work.
What do you mean, didn't work? You don't think the string above is a
3 8 7 3?I think your solution probably just has an implementation bug somewhere or you're missing some cases. It's definitely not necessary to put the 3-s in the middle like that in any case.
I implemented it in a very simple way:
You must match 0 with 1, and so you do until you run out of 0 (otherwise it's impossible since you can't match the extra 0)
Now you have "a first block" that looks like [0101...0]
Do the same but for 3 and 2, you have "a second block" that looks like [323...3]
Now you must merge both blocks with "a third block" that looks like [121...2]
If you have an extra 1, you can plug it in into the first block. Same for an extra 2 but to the second block
So the solution ends up being
[extra 1][first block][third block][second block][extra 2]
What if you have 2 extra 1s?
If you have more than a single extra 1, that means you couldn't match it neither with a 0 (otherwise this extra 1 wouldn't exist, as it would have been plugged into the first block) nor with a 2 (otherwise it would have been plugged into the third block). So the answer is no
Same if you have more than a single extra 2
Won't it fail for 101012121232323212101 ? [3,8,7,3]
My solution will work as follows
[first block] := [01010]
[second block] := [32323]
[third block] := [1212121212]
extra 1s = 1
extra 2s = 0
So the answer is:
[1][01010][1212121212][32323]
Without brackets:
101010121212121232323
it is not simple way for the second problem of the contest
You can implement it in a few lines
I have very strange solution. Let's denote how many times x goes exactly before y as c(x, y). And assume path will go from s to t. So we have 4 equations: c(1, 0) — c(0, 1) = (t == 0) — (s == 0) c(0, 1) + c(2, 1) — c(1, 0) — c(1, 2) = (t == 1) — (s == 1) same for 2 & 3... and another 4: c(1, 0) + (s == 0) = a c(0, 1) + c(2, 1) + (s == 1) = b c(1, 2) + c(3, 2) + (s == 2) = c c(2, 3) + c(4, 3) + (s == 3) = d
For fixed s and t it is system of linear equations, take any 6 of them, solve with Gaussian elimination. So we know how many times we have each pair of elements adjacent, let's make c(x, y) edges from x to y in new graph. now we need Euler path in this graph if it exists. Check it with well known dfs in 10^5.
Now just try all 4 x 4 pairs for s and t
Say no to greedy solutions)
I wonder if this solution is intended or not, I just went through all permutations of [0,1,2,3] and tried to find the answer if we use numbers in that order: https://mirror.codeforces.com/contest/1265/submission/66375662
Is there any efficient way I can increase my implementation ability? I got stucked in implementing A, C resulting to be unable to solve D(still implementation difficulty). I get stucked when I get multiple conditions and specially corner cases.
It's alright to get stuck,you'll now solve the problems you were stuck on and won't get stuck in the future. :D
Implementation is probably the easiest skill to improve because it's literally just practice. You can look at other people's solutions to see if there is a cleaner high-level idea that you are missing (and a lot of these carry over to other implementation problems as well), but in general just doing a lot of implementation problems makes you much better at it.
For A the key observation is that you can substitute all ? by any of the three chars what is fitting there, ie simply check the previous and the next index.
C and D simply anoying. There is surely some greedy, but that kind of problem is just search for corner cases.
It's not common, but I actually think the nice insight in Div2D is one that lets you eliminate the corner cases (it's mentioned above, where you just try all possible starting values and force an order after that).
C was simple. Take gold less and it's done. This idea needed a 30 minutes of coding. Can you imagine? I am dealing with the problem of implementing a solution quicker
I tried. Giving as less gold as possible. Then as less silber as possible. Then as much bronze as possible.
Sound fairly simple greedy, did not work for some reason.
This solution works, you must have a bug. You can check my submission if you have any problems debuging yours. 66332463
66352986 check this out for D, no corner cases at all.
Was not able to find the interesing problems in this contest, div2. A, B was more or less simple.
C, D anoying, I assume there is some greedy, but thats trial and error programming, at least for me. How can one find a proved solution ?
E is boring math and F way out of sight.
Wow!
yeah no, C D are not trial and error programming. Obvious greedy is obvious. Ain't the contest's fault if you don't know how to do greedy.
Div. 2 A and B were always intended as obstacles for starters. They were not intended to be complex for people who have already been blue.
C and D were greedy, yes, but you can easily prove their solutions. It was not even remotely hard to prove a greedy solution for C/D. Obvious greedy is obvious. If you don't like trial-and-error style of programming, then C can be solved with basic DSU, and, well, the math behind D can be easily proven with some analysis. I'm sure that such solutions wouldn't be too heavy in the implementation, and still satisfy what you called as "interesting".
Okay, let's admit that E is too easy for an average div.2 E — but the math behind it was a nice practice for everybody, and encourages blue/cyan competitors to try out probabilities problem. F was hard, yes, but it was intended as a challenge for the best (among blues, at least). Most div.2 F is often 2100+ — what did you expected? E 1500, F 1600, and you need to solve all 6 problems to be in top 1000?
Overall, the round does have some problems — E being a bit too easy, D's tricky 16th test case — but it was nowhere abysmal as you described. It's not the contest's fault when you sucks in the contest, and the contest wouldn't care either.
D1 was a nice subtask this time.
The depth can be calculated as follows: Pick some position, count number of ( on the left side, count number of ) on the right side, answer minimum of those. But there could be multiple positions giving the maximum depth. The observation we need is that there always exists a unique position where the count on the left side equals the count on the right side, and further at that position the count is always maximal.
To show this, find any position where the minimum is maximal, and move the position left (if there are more ('s) or right (if there are more )'s) until there is an equal amount of both. At that position both counts are equal, and the position where both counts are equal is unique (moving left either adds 1 to the number of )'s or decrements 1 from the number of ('s, and similarly for right.
So we can calculate for every position, for every count, the number of ways to have exactly that many ('s on the left side and exactly that many )'s on the right side, then multiply this by the count and add it to the answer. This is easy to do in $$$\mathcal{O}(n^{2})$$$, but I did not figure out how it could be done in $$$\mathcal{O}(n)$$$ for the second subtask.
It was a useful subtask, but still not very interesting. It's just some DP(number of ways such that the i-th character is the d-th opening bracket) and DP(number of ways such that we have at least d closing brackets among the last i characters).
At least D2 offers "hmm, how do I solve this?" rather than "yeah I'll obviously do this".
A unique maximal position existing wasn't immediately obvious for me, that took longer to figure out than writing the implementation, so for at least the subtask was interesting.
When the depth is at least $$$D$$$, we need $$$D$$$ opening brackets before $$$D$$$ closing ones, so for a fixed sequence, we just want to find the $$$D$$$-th opening bracket and check if there are at least $$$D$$$ closing ones after it. That was my way of thinking.
Is anything random in Div1.E intended to fail?
For me it looks that they are trying to hack all greedy solutions now :)
It would be great if someone knows counter-testcase for greedy, just to stip waiting :D
Well, some heuristic solutions passed and some failed, classic
Okay contest. div2D was quite interesting.
Irritating for me. Corner after corner
How to solve Div2 B? Really stucked with it.
You iterate $$$\mathrm{i}$$$ from $$$\mathrm{1}$$$ to $$$\mathrm{n}$$$, update $$$\mathrm{left}$$$ (leftmost position of all previous iterations) and $$$\mathrm{right}$$$ (rightmost position of all previous iterations) with position of $$$\mathrm{i}$$$, and $$$\mathrm{i}$$$ is beautiful if $$$\mathrm{right-left+1=i}$$$
That is a really beautiful solution. Thanks for it. :) My solution during contest was much messier.
I would just like to explain the intuition that I derived out of your solution: Since, we know that if there is a range possible for some $$$i$$$, it must only contain all elements $$$\le i$$$. So, at every step, we ensure that we are maintaining the smallest range $$$[l, r]$$$ s.t. all elements $$$\le i$$$ are contained in it, and just check to see whether it contains some other elements or not. If it does, the answer is $$$0$$$, otherwise $$$1$$$.
Make an array of pairs of (number,index) and sort this array by number. Now for each prefix (1-i) of this array, we only need to check if all indices of this prefix form a subarray in the original array. If they do, then answer for i is 1,else 0.
To check that, let S be the sum of the indices of prefix (1-i). And let M be minimum index in all these indices. Then (S- M*i) should be the sum of first i whole numbers (i.e sum(0-(i-1)) =(i*(i-1))/2.
Keep index of all numbers in map, now start with i=1 to i=m use a set and result string initially which is initially empty
for each m insert m in set, now take the first and last value from set, if this is equal to size of set then append '1' else append '0' to the result string
division 2 be like everybody do 3 questions and forget about the contest.
yes , you are right .
Can Div. 1C/2E be solved by segment tree and merging its left and right equation?
Sure. When you know the formula for expected value, the rest is fairly standard "compute function over interval". It also works for a more general version of this problem where $$$P_i$$$ can be updated too.
Oh wait, my wip solution actually works when the Pi can be updated too. I was overthinking on how to merge 2 intervals, where you have to store 2 value for each end. Turns out you just need a function to compute each interval value and can lazily update the checkpoint. Guess I'm still far away from being a master :<
Probably, but that's a bit overkill for the problem. You really just need prefix computations of certain sums (in particular the product of the first i probabilities and then prefix sums on the product of the first i probabilities). Then you can answer any segment in log time by calculating the numerator and denominator independently and using modular inverse.
It was a very cool contest, especially considering that Div1B has so weak pretests, that solution from contestant, that didn't understand the statement, pass all of them.
whaaaat?
There were sooo many WA16 and several WA6 as well, and until I checked all cases thoroughly I got WA...
I thought that all abs(s[i]-s[i+1]) should be equal to each other, not equal to 1. And my solution passed all pretests. There are no tests like 0 2 0 0 or 2 0 2 0.
I participated after 1 month and totally disappointed that....i couldn't do what was my minimum expectation -_-
You will improve don't worry :)
How to solve div.1 C?
I can only solve its easier version div.2 E with a simple probability dp...
I couldn't finish impl it on time.
but this should work, if you can get E(i,j)=from ckpoint i to ckpoint j. in O(1). since each update just change adj-ckpoint.
you need to preprocess prefix sum of $$$P_i= p_1*..*p_i$$$, $$$S_i = \sum P_i$$$, $$$T_i = \sum P_i*i$$$
since $$$E(i,j) = j-i + [dT_{i-1,j-1} - (i-1)*dS_{i-1,j-1} - (dT_{i,j} - i*dS_{i,j})] / P_j$$$.
Thanks very much, I get your main idea.
But I failed to understand your formula.
According to yogeshk972 's comment, $$$E$$$ equals expected days from $$$1$$$ to $$$n+1$$$.
Prework the suffix product of $$$p$$$, and the suffix sum of $$$\prod_{j=i}^n 1/p_j$$$, since we can get $$$E(i,j)$$$ in $$$O(1)$$$.
damn it, you're right. The formula could much simpler as yours. perhaps that's why I didn't finish impl it on time:(.
my formula is just directly calc all positive, and all negative. yes you can get much simpler form $$$(i+1)*Pi - iP_i=P_i$$$.
Can you explain the simple DP approach?
$$$E(X) = (E(X-1) + 1) * \frac{1}{P_{i}}$$$
$$$E(0) = 0$$$
Where $$$E(X)$$$ is the expected amount of days to get a "you're beautiful" from the X'th mirror.
Intuition — To transition reach the i'th mirror, we first need to reach mirror i-1, which takes $$$E(i-1)$$$ days. After we get a yes from mirror i-1, we need one extra day (hence + 1) to get an answer from mirror i. Now we have a "cycle" of ($$$E(i-1) + 1$$$) days for the amount of days we expect until we have reached the i'th mirror and gotten an answer from it. Then it will take $$$\frac{1}{P_{i}}$$$ (geometric distribution) passes through the cycle until we expect the the i'th mirror to return "you're beautiful".
Final answer is $$$E(N)$$$
i have seen most of the solution involve this
power(p[1], mod — 2, mod) why are we raising it by mod-2
Because the modulus is prime, $$$a^{m-2} \equiv a^{-1} \pmod m$$$ via Fermat's little theorem (which is a special case of Euler's theorem). It's a popular way of obtaining the modular multiplicative inverse $$$a^{-1}$$$ where $$$a \cdot a^{-1} \equiv 1 \pmod m$$$, which is the easiest way to "divide" numbers in a modulo field.
Expected number is too complex in wikipedia.Can anyone explain it more simple?
Expected number of $$$x$$$ is summation of all possible values of $$$x$$$, each multiplied by its probability of occurrence. If $$$x$$$ is a continuous (not discrete) variable the summation is converted to integration.
Check the blogs of Errichto. :)
How to solve Div2 C? Really stucked with it.
take minimum gold, take silver until it"s greater than gold rest till n/2 is bronze. Also you can't take the contestants with minimum solve and can't divide contestant with equal solve between silver and bronze or bronze and no prize.
I used same idea. But it gives me WA.Can you please tell me what wrong in my approach?
Here is my Code
I think problem is with your global array a. You are not initializing it to zero for each test case.
I just want to say problem C has too long of a statement. So, statementforces?
Well, that was an interesting round. Thanks to the creators!
My dreams of reaching blue seems impossible now
Be calm see my profile I have struggled more than you but still I have not become an expert this site is more challenging.
Keep calm. And solve problem after the contest.
Did anyone else solve div2B using DSU, where the adjacent values in permutation to be considered an edge, and we join them one by one while processing for each i, and the number being beautiful when the number of roots in dsu being 1?
No need for that though
https://hastebin.com/vezonuxuve.cs
So I'm relatively new to this, and I was pretty stumped on Problem A, Div 2 (got a TLE). https://mirror.codeforces.com/contest/1265/problem/A
Looked over a correct solution and noticed that instead of creating and adding to a string like I did, they first converted the inputted string to a list, and went through and modified the list.
Is working with a list, and not creating any new variables like this, really that much faster? Is it something else? Or is there a roadblock in my code that I haven't mentioned yet? Would appreciate any help
From my point of view using a list does not give advantage in this problem. One hast to check the chars at position +1 and -1, both is a[i+-1], using a list or a string.
Всё было как всегда гораздо проще чем я думал :|
Слабые претесты на D. Сама задача тоже плохая.
DIV2 A DFS FTW!
Why do you need it? You can look at the front and back for questions and find the answer from this.
I'm just too lazy to think of a greedy solution.
needless to say, pretests are shit
So my B failed because of this dumb typo:
if (a + b == b + d)I decided to look at the pretests and found that out of 17 pretests, 11 have no answer and the remaining 6 have an odd total numbers. Don't know if it's intentional or not ¯\_(ツ)_/¯
No, it was not intended. It's just you are unlucky.
For Div2 ProblemD: It was said that "The only input line contains four non-negative integers a, b, c and d (0<a+b+c+d≤105)."
But I got wrong answer on testcase #16 which is: 0 0 1 2
I think 0 is non-negative.
Why the answer for DIV2, D for 10th pretest (1 3 40001 40000) is NO? Why can't we do this like: 1 0 1 2 3 ... 3 2?
it would be 1 zero and 2 ones but test case needs 1 zero and 3 ones.
OK, so why it couldn't be with one more one at the end of answer, I mean: 1 0 1 2 3 ... 3 2 1, now I think it would be correct...?
This test case will have an answer according to question. That can be either 1 0 1 2 1 2 3 2 3 .. or 1 0 1 2 3 .. 3 2 1.
So why the answer is "NO"?
The answer is "YES" but your output is "NO"
NO is your output. Correct answer is what you say. Read the detail of your submission carefully.
Answer would be YES 1 0 1 2 1 then (23) 40,000 times
Read the detail of your submission carefully.
OKK, right, so sorry.
so sad. D has weak pretest :((
Can someone please explain how do we get 112 as the answer in E second example? I was getting 100. Probably applying a wrong concept here!
66326596 Someone stole my code from ideone.com. It wasn't intentional but I used ideone.com with the default settings (public access to your code), Here is the link: https://ideone.com/pwlcr1 but I used the same link to write the answer for problem B in the Div 2 contest: 66336397 and as you can see it is the same as in the link.
UselessDev
how can I increase my ability to solve B C D type problem easily??
just improving my skill in data structure.... is it enough ??
This old comment might help: link
Nop , for solve those problems on CF is most important the experience , and always do upsolving reading the editorial and read betters codes of others contestants.
Finally I have a nice rating.
Nice
Nice
This is my 3rd contest on codeforces, and I am confused about the ratings change. In my first contest I was able to solve A only , my rating was 1370. In 2nd contest I was not able to solve any, my rating was 1255. In this contest I was able to solve A,B,C and my rating is 1314 ! lesser than the 1st contest even after solving more problems ?
How is this possible ?
Rating is determined based on the rest of the competition. Let me give a fake example. 9000 people participate in one contest and 8000 of them are able to get >1 problem right. Let's suppose there is another contest with equally good people and the same number of people in which only 3000 of them get >1 problem. Then, if you solve a problem in the first contest, it is not as impressive as if you solve a problem in the second contest. So your rating does that; it is based not exclusively on how many problems you solved but how many you solved relative to how many other people solved. For more detailed information, see here.
Here's an outline of how the rating system works. Contest rating != performance in only the last contest. It's a cumulative measure. It increases if you perform better than the expected performance (which depends on your rating before the contest began), and decreases (or stays constant) otherwise. Also, before the first contest, your base rating is taken as 1500, so think of the first contest as a change in rating from 1500 to 1370.
Thanks bighead, you live here free of a rent for whole year — Jin yang
I think problem c on div1 is be more beutiful if have one more query that change the Possibility
Nah it's pointless a bit more codin'. Doesn't make it any more "beautiful"
For anyone interested to know why the expected number of trials in mirror $$$j$$$ before going to mirror ($$$j+1$$$) is $$$\dfrac{1}{p_j}$$$ ($$$0<p_j\le 1$$$, will remove the subscript $$$j$$$ in the proof to reduce typing):
Let the expected value be $$$E$$$,
$$$E=\sum_{i=0}^{\infty} (i+1)*p*(1-p)^i$$$
$$$=p*\sum_{i=0}^{\infty} (i+1)*(1-p)^i$$$
Let $$$s = \sum_{i=0}^{\infty} (i+1)*(1-p)^i\, \textbf{(1)}$$$
Multiply both sides by $$$(1-p)$$$: $$$s(1-p) = \sum_{i=0}^{\infty} (i+1)*(1-p)^{i+1}\, \textbf{(2)}$$$
Subtract $$$\textbf{(2)}$$$ from $$$\textbf{(1)}$$$: $$$s(1-(1-p)) = 1 + \sum_{i=1}^{\infty} (1-p)^i = 1 + (1-p)\dfrac{1-(1-p)^{\infty}}{1-(1-p)}$$$ (using sum of geometric series)
$$$\therefore s = \dfrac{1}{p} + \dfrac{1-p}{p^2}$$$
$$$\therefore E = p(\dfrac{1}{p}+\dfrac{1-p}{p^2}) = 1 + \dfrac{1-p}{p} = \dfrac{1}{p}$$$
Can you please explain how to build the solution to Div2 E using this ?
I don't understand this , but you can see XLor comment https://mirror.codeforces.com/blog/entry/71916?#comment-562459 you can easily understand it.
This is essentially needed to solve $$$Div1C$$$. But you can solve $$$Div2E$$$ in an easier way.
90qvB
I was just proving why the expected number of trials in mirror $$$j$$$ is $$$\dfrac{1}{p_j}$$$.
This is how I solved $$$Div2E$$$:
Let $$$E(i)$$$ be the expected number of days we have to spend before going to mirror $$$i+1$$$ if we started at mirror $$$i$$$. If we calculated $$$E(i)$$$ for all $$$i$$$ from $$$1$$$ to $$$N$$$, the answer is just $$$\sum_{i=1}^N E(i)$$$. To calculate $$$E(i)$$$:
For $$$i=1$$$: $$$E(1) = \dfrac{1}{p_1}$$$ (because every trial at this mirror corresponds to one day).
For $$$i>1$$$: $$$E(i) = (\dfrac{1}{p_i}-1)*\sum_{j=1}^{i-1} E(j) + \dfrac{1}{p_i}$$$ (because every trial from the first $$$\dfrac{1}{p_i}-1$$$ trials corresponds to going back to mirror $$$1$$$, and we have to spend $$$\dfrac{1}{p_i}$$$ trials (days) in total at mirror $$$i$$$ itself.
Thanks a lot for the solution, never used Expectations this way. I solved it sometime back using the idea mentioned in this comment which appears slightly more intuitive. You may wish to look at it, in case haven't.
Thank you, your solution is even simpler.
I don't understand "expected number of trials in mirror $$$j$$$ is $$$\dfrac{1}{p_j}$$$".
Won't that be the case if with probability $$$1-p_j$$$ you started back at $$$j$$$. But here, we are going back to $$$1$$$ right?
I have read both your comments again and again, am I missing something obvious?
I feel like I finally understand. I am too used to thinking about it using the Law of Total Expectation, so sharing it for others who might be stuck too.
So, we have
$$$E(j) = E(j|B)*P(B) + E(j|not B) * P(not B)$$$
$$$E(j) = (1)*(p_j) + (E(j)+1)*(1-p_j)$$$
Here, B is the event that the $$$j$$$th mirror tells you that you are beautiful, and $$$E(j)$$$ denotes expected number of days until we reach mirror $$$j$$$.
Solving, gives the same thing, $$$E(j) = \dfrac{1}{p_j}$$$.
Yes, this is the case if we started back at $$$j$$$. And since we actually start at $$$1$$$, each of the $$$1^{st}$$$ ($$$\dfrac{1}{p_j}-1$$$) trials is followed by going back to $$$1$$$, and hence we add $$$\sum_{k=1}^{j-1} E(k)$$$ ($$$\dfrac{1}{p_j}-1$$$) times.
I meant that, we cannot calculate time spent at $$$j$$$ this way.
This first line you used,
$$$E=\sum_{i=0}^{\infty} (i+1)*p*(1-p)^i$$$
I still don't understand how the calculations are working out.
This, according to me, assumes that with probability $$$1-p$$$ we start again at $$$j$$$.
Also, in my own calculation above, when I use "expected number of days until we reach mirror $$$j$$$" it makes sense, but that means it's wrong, because then the answer would simply be $$$\dfrac{1}{p_n}$$$.
Yes this assumes that we will start again at the same mirror, as if this mirror was a checkpoint.
$$$E = 1 + (1 - p) \cdot E$$$ (We do one step and with probability (1 — p) we start over)
You could start from this as well =)
Thank you. I didn't express expected values before using this way, but it seems really great.
Generally, your explanation is the same as the expected value of Geometric distribution?
Yes it looks similar. Some example (as mentioned in the Wikipedia page) would be the expected number of dice throws until the number $$$1$$$ appears (here $$$p=\dfrac{1}{6}$$$, so the expected value is $$$6$$$).
For Div1 E，it can be showed that this problem is quite similar to a problem in Chinese Contest WinterCamp 2007，the code can be easily searched by Baidu or Google. for example,the following blog posted the code in 2018 https://www.cnblogs.com/zhoushuyu/p/9146420.html According to the rule about the Third Party code，i think i should not be unrated. MikeMirzayanov Please investigate this matter，Greatly thanks
I have the same problem, and I use the code from https://www.luogu.com.cn/problemnew/solution/P4249.
Actually I used the first solution code at https://www.luogu.com.cn/problemnew/solution/P4249, which was published in 2018. I don't think this breaks the third-party code rule according to http://mirror.codeforces.com/blog/entry/8790.
Hope the rating can come back..lol
Crazy match！ I only solved A in the first hour. Thanks to E, It's very similar to bzoj2597 I solved. It gived me hope.
Beautiful Sequence gives me a beautiful FST :(
For div1 C, by mistake I output n lines. And perfectly, The pretests satisfy n=q, so I get a perfect FST......
What does FST means, i'm curious :P
Failed System Test.
This is my solution for Div1 D1:
Let's first think about how to calculate the depth for a definite bracket sequence.
If the first element is
)or the last element is(, then it's useless and we can reduce the length of the sequence by one or two.Otherwise, the first element is
(and the last element is), so they form a match and we can increase the depth by one.So we can define
Unable to parse markup [type=CF_MATHJAX]
for calculating the sum depth of interval $$$s[x\ldots y]$$$:For the situation that $$$x\geq y$$$, the result is obviously $$$0$$$.
If $$$s_x$$$ is
)or $$$s_y$$$ is(, then $$$\operatorname{solve}(x, y)$$$ equals to $$$\operatorname{solve}(x+1, y)$$$ or $$$\operatorname{solve}(x, y-1)$$$.Otherwise there is ability to increase the depth of the interval $$$s[x\ldots y]$$$:
$$$s_x$$$ is
(and $$$s_y$$$ is): No matter how you determine the?between $$$s[x+1\ldots y-1]$$$, $$$s_x$$$ and $$$s_y$$$ always form a match to increase the depth by one, so $$$\operatorname{solve}(x, y)=\operatorname{solve}(x+1, y-1)+2^{k}$$$, where $$$k$$$ equals to the number of?in the interval $$$s[x+1\ldots y-1]$$$.Either $$$s_x$$$ or $$$s_y$$$ is
?: You can determine whether the?can be matched or not, and if matched, it's similar above, else we can just ignore the?.Both $$$s_x$$$ and $$$s_y$$$ are
?: If we determine $$$s_x$$$ to be(and $$$s_y$$$ to be), it's $$$\operatorname{solve}(x+1, y-1)+2^{k}$$$. If we determine $$$s_x$$$ to be)(and keep $$$s_y$$$ undetermined), it's $$$\operatorname{solve}(x+1, y)$$$, and $$$s_y$$$ to be(, it's $$$\operatorname{solve}(x, y-1)$$$. Note the situation that $$$s_x$$$ is)meanwhile $$$s_y$$$ is(will be calculated twice, so we need to subtract $$$\operatorname{solve}(x+1, y-1)$$$ from it.Then we can solve Div1 D1 in $$$O(n^2)$$$. But I had trouble optimizing it to $$$O(n\log n)$$$ or better. Can someone help?
Upd: My code for Div1 D1: 66373927
In problem D. Beautiful Sequence The only input line contains four non-negative integers a, b, c and d (0<a,b,c,d <= 10^5) It should be <=0 because it says non-negative integers and input actually contains 0. I tried the question after contest and had a wrong ans because I thought that a,b,c,d>0
The problem statement says $$$0 < a+b+c+d \leq 10^5$$$. I see why this could be misinterpreted, however it is not a mistake as it does not imply $$$0 < a, b, c, d$$$.
you are right. I misinterpreted. Thank you for pointing out
Is there any reason that my all the solutions were skipped???
Either you've shared your codes with somebody during contest or probably you'll be using online compiler like ideone in default mode public . And during the contest someone else have just copied and pasted your code and so you have been removed from this contest.
I coded E 10 minutes into the contest. When I was thinking of whether I should submit or not because it seems improbable for me to be able to solve E in 10 minutes, my PhD advisor called me and saved me the dilemma.
I just submitted and found out the solution was correct after all :(
The important part is you can solve it.
When will the editorial be published?
can anyone explain me how to solve div2-D/ div1-B ?
Form a graph with 0,1,2,3 as the nodes and edges from i to i+1 and i to i-1 for each i in [1,2] and the edges 0->1 and 3->2. Then perform a DFS from each node and check if all the frequency of occurrence of each node can be made zero. Whenever a node is visited, decrement its frequency. When the frequency of a node becomes 0, then you can't visit it. Also, the DFS should be modified, since from one node, you should visit only one of the adjacent nodes. The answer is the order in which the nodes are visited if the frequency of all the nodes are made 0.
https://mirror.codeforces.com/contest/1265/submission/66381723
I get the idea now!
easily passed div2c&e... pity went sleep early last night, or maybe rating++
My approach for problem Div.1D :
Given a string $$$s$$$, how to calculate its depth? It equals the number of positions where it reaches a depth for the first time. For a position $$$i$$$, suppose that there are $$$a$$$
(s in $$$s[1,i]$$$ and $$$b$$$)s in $$$s[i+1,|s|]$$$, then we count this position if and only if $$$s[i]=$$$(and $$$a\le b$$$. Example: for string(()()), we count positions $$$1,2$$$.When the string contains
?, things become harder. We iterate each position and find the number of string in which this position should be count. For a position $$$i$$$ that $$$s[i]=$$$((if $$$s[i]=$$$?, we assume it's(), $$$a$$$ and $$$b$$$ are the same as above, $$$c$$$ is the number of?s in $$$s[1,i]$$$, $$$d$$$ is the number of?s in $$$s[i+1,|s|]$$$. Then the answer for this position isBruteforce is $$$O(n^2)$$$. But we can find that
$$$c+d$$$ is a constant (or minus $$$1$$$ when $$$s[i]=$$$
?), thus the problem is solved in $$$O(n)$$$.In the second step $$$\sum_{i+a\leq j+b} \binom{c}{i}\binom{d}{b}$$$
shouldn't it be $$$\sum_{i+a\leq j+b} \binom{c}{i}\binom{d}{j}$$$ ?
Yes. Thanks. Now it's fixed.
share a simple way to get formula instead of math.
just let all ? be ( first. then $$$delta = b - k$$$, where $$$b=$$$#( before i, $$$k=$$$#) after i.
then any ? no matter before/after i, change to ). will make $$$delta$$$ $$$-1$$$. and we wanna goal that $$$delta <= 0$$$. then get the answer equal to prefix sum of binomial.
Elegant idea! Thanks for sharing!
Anyone want to explain their solution for Div1 E? I saw from other comments that it is a problem that has appeared before, but it seems like it's mostly appeared on Chinese contests so I can't read the solutions :(
Brief Outline: The problem is equivalent to minimizing the sum of squares of outdegree of each node. Create a min cost flow graph where each unassigned match corresponds to an auxillary node, connected with cap 1 cost 0 to source and cap 1 cost 0 to the two players. For each player, add edges of cap 1 with costs $$$2o+1, 2o+3, ...$$$ where $$$o$$$ is the current outdegree of the node.
Ah thanks, the sum of squares reduction was not at all obvious to me. Neat trick, in the end I guess it's just complement counting. The MCMF after that makes sense. It's a cool problem!
how do you solve div2 E
Let $$$E(i)$$$ represent the number of days to reach the $$$i^{th}$$$ mirror. Then we have:
$$$E(i) = E(i-1) + 1*(p_i/100) + E(i)*(1-p_i/100)$$$
Basically the equation means that if you reach the $$$(i-1)^{th}$$$ mirror, then with $$$p_i$$$ probability you reach the $$$i^{th}$$$ mirror the very next day, or you start over and reach it after the expected number of days to reach the $$$i^{th}$$$ mirror
You can rearrange the equation to get a formula for $$$E(i)$$$ in $$$p/q$$$ form and solve using modular arithmetic.
Base case is $$$E(1) = 1$$$ and final answer is $$$E[n+1]-1$$$
I use similar approach.
But i think (1−pi)/100 may be replaced with (1-pi/100)
My bad. You are right. I forgot while writing that $$$p_i$$$ is given as a ratio to 100. Edited
The constraints of div1.E is too small. Actually it can be solved in $$$\Theta(n^4/w)$$$ by optimizing the process of cost flow.
Please provide the editorials.
There is a hard version of Div.1 B (s_i can range in [1,20000]) from my own host contest in the past:
https://mirror.codeforces.com/group/gRkn7bDfsN/contest/210347/problem/D
Everybody can give it a try~
For div2 problem A: I am getting a segmentation fault which I am trying to debug but unfortunately was unable to debug. Can anyone help me find the error I have made?
Here is the link to code: Link
You have a typo in line 14 — it should be
j++, noti++.But it becomes confusing for me when I print t. How this typo assigning t to a garbage value? where he is not using t later in the while loop.
Where is editorial ?
Hi chemthan, we need an editorial, thanks!
Sorry for delay. We are busy now. Hope can do it asap.
Waiting for author's solutions to the problems...)
It's O(n). Why am I getting TLE. https://mirror.codeforces.com/contest/1264/submission/66382862
Your last while doesn't have any reason to stop
Oooo... got it. What a bug?
I get into problems during contest for these silly mistakes. And can't find what's wrong? How can I get rid of that?
Take a deep breath and tell yourself that you love debugging and there's nothing else you can't debug.
It's not a silly mistake, or at least I don't call it so. You learn not to make these mistakes after failing at them. Next time when you have TLE you probably will look for infinite loops first, and after couple of times you'll start paying more attention to them while you're coding.
Best way to not make these mistakes during the contest will be to make them during the practice!
Well I am so weak,Can somebody tell me how to do Div2 C?Thanks!
take minimum gold (all with maximum solve)
take silver until it's greater than gold
rest til n/2 is silver
while taking g,s,b make sure you are not violating rules 2,4,5
finally have a check if conditions are fulfilled with your g,s,b
How to solve Div2 prob B, my solution is getting TLE. What is wrong with it? Would someone please explain
I think your submission has complexity like t*n*n which is very large to complete in 1s even the sum of n from all test cases in the input doesn't exceed 2⋅10^5
What is the efficient solution
See the editorial I use the same approach
Waiting for the editorial....
At least let us know when the editorial will be published? I am bored and tired of checking.
May be they have some issues
https://mirror.codeforces.com/contest/1264/submission/66453921
Looking at the comments my idea is similar, we first calculate answer with no checkpoints (which works, since I pass Div2E), and afterwards if we add a checkpoint j in interval [i, k], we have to decrease the answer by prod(i, j — 1) * prod(j, k) and add val[j — 1], when we delete j we need to merge intervals [i, j — 1] and [j, k], we do the opposite (add products, subtract val). This fails on first checkpoint addition on big test, so I cannot research that manually. Any ideas what I did wrong?
I get the error message "You are not allowed to view the requested page" when trying to view the editorial. chemthan please take a look.
Either it has been updated or there is some problem on your end because I can see the ediotrial. https://mirror.codeforces.com/blog/entry/71995
And wow, 2-line code for F. :)