Hello coders! I hope that you are enjoying the New Year as much as me. To make its beginning even greater, Codeforces is going to host a contest and I will be an author of all tasks. Hello 2019 will take place on Friday.
Using the opportunity, I want to thank to:
- Lewin and mnbvmar for testing the round.
- mnbvmar for indescribably helpful discussions about problems.
- cdkrot and KAN for round coordination and help with preparation.
- MikeMirzayanov for such great platforms (you know which ones :P).
The round will consist of 8 problems and you will be given two and a half three hours to solve them. Yes, the round will be rated.
There will be no interactive problems, but if you want you can read this document anyway, it's always good to learn new things.
Good luck and see you during the contest!
UPD1: Editorial
UPD2: I'll be on the Discord channel after the contest, so you will be able to ask me about the problems.
UPD3: You're probably wondering what the statements will be about. I hope that it will be another great year for Codeforces. As it's the community that creates it, I decided to write statements about the people who already have or had their part in Codeforces' history. As I wanted to be objective, the statements will be about 8 people who triumphed the most times in CF rounds. Using the opportunity, I want to invite these 8 people to take part in the contest. Let's say that the first person who will guess the set in the comments wins some free contribution. Good luck!
UPD4: The round will be 3 hours long.
UPD5: The drain will be adjusted and the scoring will be 500-1000-1500-2000-2750-3000-3500-4000.
UPD6: The round is over, congratulations to the winners!
And to the first-to-solvers!
- A: Errichto
- B: dorijanlendvaj
- C: Um_nik
- D: rng_58 (his personal task!)
- E: LHiC
- F: tourist
- G: V--o_o--V (his personal task!)
- H: ecnerwala
UPD7: Editorial
You accidentally uploaded the ediotiral, but i am honest and don't look there
Well, thanks for that, but you shouldn't worry so much :P
you changed your handle from numb. So many quora links are gonna be dead now
I have seen a new name in my friend list and wondering about who is this guy... Finally I understood...
If you change your handle the links refered to the lastwill redirect to the new profile page
Nice editorial tho.
I can neither confirm nor deny that editorial without Radewoosh's approval
lol
That editorial, haha, so funny!
I hope that you won't die laughing ;_;
this.handle+" 2019!";
Thanks for fast editorial.
I really hope noone is enjoying the New Year as much as you.
For their own health.
Can you please reupload the editorial? It is not available in my country and now I feel at disadvantage.
Unofficial Editorial
tfw youtube blocks education... Sad day for science.
Since you like numbers you'll enjoy this https://youtu.be/BipvGD-LCjU
that's so funny, thanks for that!!
One of the best editorials ever seen. Nice one.. Haha:P
Why aren't you blue anymore? Also, what is the blog gonna look like when you upload the real editorial?
too excited about the first contest in this year and as well as a contest by Radewoosh.
Awesome editorial! :P
-
By the way, why isn't the Rating of the problems in Goodbye 2018 shown yet?
could you explain in more detail div2a? including official solutions also helps.
Nice editorial :P
LOL HAHABA SHIT JOKE=))))
Me: Oh, an editorial... let's to see!
(wild video appears...)
Me:
Your editorial sucks! The video isn't available in my country!
clicked on the Editorial
Really Radewoosh? Thanks for being the first one doing that to me in 2019 :D
The most unique editorial I have ever seen. Hoping for a nice contest now (paradoxical I guess, waiting for the contest after editorial)
Also, Thanks a lot for suggesting us to learn about new things :)
Looking forward to it, hopefully I will finally become green again :P
Not gonna lie, I thought I badly missed the contest..
Until I swiped left my mobile screen..
I've been looking forward to a round prepared by a single expert, but, however..
wulalalala is it rated?
what is the rating of the contest ?
If the question is, Is it rated? then answer is YES. or, if the question is Rated for which division? then answer is Everyone who will attend the contest.
Fastest editorial in my codeforces history. Thanks Radewoosh
Well-written editorial ^^ but I think you forgot to link the statements that go with it :\
Hello
I've already read so many editorials that I know this gXcQ by heart.
Fastest editorial ever!!! Also that's one of my favorite songs to cheer me up too.
Is it just me, or does Radewoosh look really similar to Rick? o.O
Radewoosh vs Rick
I thought you were thinking of Rick Sanchez and was like no, Rick is more similar to Um_nik...
Or maybe LanceTheDragonTrainer.
Rick Astley
Never gonna give you uuuup! I like this editorial :)
How to solve D ?
You can view the editorial linked in the blog for the answer
Exceptional Editorial :P
Wow, early editorial. When are you gonna update the ratings?!.
Goodbye 2017;Hello 2018.:D
Hi Internet Explorer
Ping : 999
I'm gonna listen to this editorial everyday
Thanks for the video editorial , really educational !
Just hope, everyone has high ratings with this new year. Tough competition though :P
OMG, Radewoosh contribution +200. That`s so much!
Fuck U Radewoosh.My New Year Resolution was not to Open Youtube(Personal Reason).And Bcoz of u it is broken now.
You should have blocked youtube then.
this will get me out of master :^D
Everyone says that he hopes to be green, gray and other color. I hope to become Double Legendary Grandmaster SuperJava
Is it rated??
"Yes, the round will be rated"
Sorry cant read can u give it to me in voice mesage
ArepitaDePernil will never tell a lie and hurt you!!
Hope to reach green this contest :)
it would be cool if pressing the downvote button would also redirect u to smth funny
Lets see if this post gets more upvotes than Hello 2018. Radewoosh you are my favorite.
I think that the set of people will be: tourist Petr Radewoosh Um_nik rng_58 OO0OOO00O0OOO0O0…O PikMike Vovuh
Errichto has never won a round, sorry :/
Challenge in UPD3 is pretty simple using Codeforces API but I'm too lazy so let me guess. Let me spare them these mentions: Petr, tourist, Radewoosh, OO0OOO00O0OOO0O00OOO0OO, Um_nik, rng_58, V--o_o--V, YuukaKazami
Looks almost correct :P
You forgot Swistakk :)))
He won once, I doubt it's enough to be in top-8
I wonder what is the number of participants who won at least one rated(for div1) contest. Too lazy to check using API and/or by opening results, of course.
UPD3 challenge: tourist, Radewoosh, OO0OOO00O0OOO0O00OOO0OO, Um_nik, V--o_o--V, LHiC, Petr, encerwala
Not this time :C
UPD2: I'll be on the Discord channel after the contest, so you will be able to ask me about the problems
I can't enter the server ((
Egor it was very tricky from you to hide on 158th place in overall standings with these 11 wins of yours :P
Petr tourist Radewoosh jqdai0815 Um_nik rng_58 V--o_o--V Egor — be aware that Radewoosh invites you to take part in this contest :)
And we have a winner!
Seems cool, he's just after tourist and Petr, not sure about OO0OOO00O0OOO0O00OOO0OO, but all in all, 11 is too much!!!
I'm not saying that V--o_o--V is not cool, but among his 8 wins 2 are schoolboys competitions and 3 are VKCup rounds, so 5 wins with huge restrictions on participants.
V--o_o--V showing Um_nik who's the boss.
I'm not saying that V--o_o--V is not cool
Smooth on Um_nik's part to write this. Otherwise this comment will not have aged well at all. :D
why are you so happy? you don't care who's the boss or not
You lost, V--o_o--V win
what about you? tell us how you lose the rounds always to thousands people
Radewoosh invites himself to take part in his own contest? :thinking:
includes unofficial participation
gimme some of the left over contribution
Anyone wants to create Codeforces version of this?
Something like this?
Link
Thank you, looks nice :)
Maybe we shouldn't mix d1/combined matches and d2/d3/unrated matches?
Only reason I failed last several rounds is to deceive everyone in anticipation of this
I just want to tag dreamoon_love_AA sorry_dreamoon :P.
In UPD 3 , I think they are (in sorted order from number of contests winning)
1 — tourist
2 — Petr
3 — OO0OOO00O0OOO0O00OOO0OO
4 — rng_58
5 — Egor
6 — Um_nik
7 — V--o_o--V
8 — Radewoosh
9 — YuukaKazami
and since you said that you invite first 8 to take part in contest...so I think that maybe you mean 9th which is YuukaKazami
Unfortunately there are two persons on 9th place, so I'm also inviting myself to take part (and I will, but from the other side :P).
And sorry, but our contributionboy was faster.
I cant understand the editorial, anybody can explain with more details? :D
It sure will be the best 2019 contest so far.
i don't think so
I don't believe in him, I bet it will be the worst one so far.
We have a winner here :P
Change the start time to 20:19 ! :D
Taking part in a contest begins at 22:35(UTC+8) is usual for me now, but if it lasts for 3 hours...
I hope there won't be solutions in the problems.
Even Problems In an Odd Year will Make My Day !!!
One of the Best Editorial ever.
Thanks for the Motivation.
Another Editorial if you wanna take a look.
finally.. someone generous. Three hours !
Really enjoyed this editorial.
If you can't see the editorial, you can try this. It's the same video.
The 8 people will not includes OO0OOO00O0OOO0O00OOO0OO because it's too hard to write.
QAQ
Outrageous editorial!
Why those stupid early contest times for this and Goodbye 2018? I'm not a shut-in with nothing to do except programming contests at any time!
Actually it's a little too late for Asian. It's hard to meet everyone's need. So it's better to enjoy those you can participate in and stop complaining about everything.
Yeah, which is what two consecutive big rounds with the same starting time don't do. If you look at the contest list, the last 8 rounds including this one (some div1) had an early starting time.
There are countless things I'm not complaining about, so how about you don't try to dismiss a valid point? Which rounds can I enjoy if it's been almost a month since one didn't start in the early afternoon?
PM 11:30 to AM 02:30 in my country 8ㅅ8
AM 00:35 to AM 3:35 in my)
cheer up!
Adjusted drain, please. Nobody wants their C-D to be worth more than G-H.
@ MikeMirzayanov, cdkrot, KAN
Pls pls pls!!! It lasts 3 hours (not 2.5), so it is even more important!
it is adjusted
I Have a Farsi exam tomorrow, I know Im going to fail but F*** that, I waited a year for this.
Very exclusive tutorial.Following the tutorial most of the contestant including me become legendary grandmaster without participating any contest :D
Never gonna give you up =))
Score distribution? Updated Now
Good luck to all! Wish you to see lot of "Happy New Year!" verdict!
Before start, delayed by 10 mins :|
впрочем ничего нового
why delay 10 min ?
Finally my time travel machine worked, I moved everyone 10 minutes in the past
10 minutes delay means now I will skip the last 30 minutes of the round, not a good thing :(
PING : 600000ms
I'm confused because the contest was suddenly delayed a few seconds before the start of the competition.
JEBAITED XD
Is it another DDOS attack???
Maybe expecting more participation, I guess.
What an Anti-Climax (Delayed by 10 mins)
There should be a notification when a contest is delayed. We press OK and suddenly get shocked to see delay :/
Radewoosh, You want to crack the 12K record?
UDP5 : 10 min delay.
(UDP5 -> UPD6)
Trying to get 12k registrants and beat Goodbye 2018 with that delay? haha
I think the delay was for beating the record for the most registered people in a contest.
About +600 participants. Good luck :)
It's great idea from you to put a link to your song in the blog, nice advertisement man
Starting new year with 10 minutes delayed contest, it gonna be legen wait for it dary year.
Task C
wtf, almost the same problem indeed!
Yes, it was common for a lot of us.... :p
What is TC4 of Prob C?
This was a useless question...
Radewoosh unbalanced contest
no sh*t
еее говноконтест)))00))))))))))))000(()0(
Why does E have only 1 correct submission? Overkill or wrong official solution?
For Div-2 Coders, it was a 1/2 hour contest.
very funny statements
The test case 2 of D is killing me for past 1 hour. For some reason, I can't seem to figure it out (in fact n=6, k=3 provides me with the given output). However, as there has been nobody raising that issue, the only explanation is that I have forgotten all my maths.
It was strange for me too The problem with me in this problem that I didn’t even understand what is the statement Also no explanation for the output of the second test . When i asked the author he repeated the statement for me I thought it is only my problem
Well I had the same problem at the beginning The problem is that you take into account the number of divisors of a divisor of N to calculate the probability for each k
Oh Damn! I really forgot all my maths. Thanks for clarifying.
oh god I understood C wrongly wasted 1 hour until I read it again it's way easier than what I was trying to solve :/
I will never read problems quickly again
MeToo
[DELETED]
Maybe, one day, Science will be able to answer why div2 coders like me keep on refereshing the standing page for 2+1/2 hours, even when they are done with the problems in 1/2 hour (-_-)
The strange thing that my rank keeps increasing if that i didn’t solve a problem after the first 40 min
Yeahhh!!!
without taking part in the contest how did you solve A, B, C?
i dont know how many times i saw this in 2018...
hope to not see this in 2019 anymore
Please make me expert :|
UPD: I became! <3
How to solve D?
Does D uses the fact that number of divisors are number of ways to select powers of its prime factorization?
Well given that N is up to 10^15, you can check the divisors of N in O( sqrt(N) )
Hello 2̶0̶1̶9̶ depression.
People being unable to solve D (at any points during contest time) be like:
And I got the first and third case. Won't really blame (for a master, this performance of mine was way disappointing), but still, my point still stands. This contest is too unbalanced.
I know, most Div.1+Div.2 combined recently look quite similar that way, but still, this one took the gap to the highest magnitude. Like, a single mistake is a suicidal sign.
I got them all. C statement was not clear and wasted a lot of submissions on it.
It may include misinterpreting the problem.
Well, that would be the worst of any start of a year.
I did that too (╥_╥)
In E is just greedy O(n logn sqrt(n)) passing?
If by greedy you mean remove the longest monotonic subsequence, then I got WA with this approach. It is known to achieve
, but I can only construct cases in which I need 
, so there is something missing.
I found that N = k2 + k + 1 needs f(N) ≥ k + 1 and that f(6) = 3, so this is obviously not the exact bound, but it's very close to the other bound from Erdos-Szekeres.
Solution is either greedily pick largest subsequence or split the whole sequence into the minimum amount of increasing or decreasing sequences.
me.
After A, B and C.
For me, Hacking phase begin!!
problem D , what maximum number of divisors n can have ? and if less than 1e3 can we use dp ?
Maximum number of divisors of a 15-digit number is 26880: https://oeis.org/A066150
86642131736160025880 divisors
it is around 27k for 866421317361600
How to solve F?
ok fellas, how do we solve D?
There's a straightforeward dp solution. Compute all dp[i][j] = expected value if starting value is i and you have j turns. (i are all potential divisors of n).
However this is too slow. You can speed it up, by realizing that this function is multiplicative. Therefore you compute dp[p^e][k] for each prime factor p of n and multiply the results.
How to find prime factors of n? I mean n is big and I couldn't find out whether n is prime or n is pq for some p and q being prime numbers.
n isn't that big. In my case I simply computed all primes <= 4*10^7 using a sieve (which runs in <0.1 sec), and tried dividing n with all primes. But I also expect that a simple for loop until sqrt(n) will also be fast enough.
:(. I thought maybe 4 * 10^7 does not fit. Thanks.
Can you elaborate a bit on proofs of this function being multiplicative? I don't really getting it mathematically.
Expected value of product of two independent random variables A and B is the product of their expected values.
Proof for discrete A, B:
(Here a and b are values that A and B can get.) P(A = a, B = b) = P(A = a)P(B = b) from definition of independence.
At every step the power of every prime changes independently, since if our current number is y = x * pa
, then the number of divisors of y where the power of p is a given value <= a is always just the number of divisors of x. Since all these probabilities are equal, they do not depend from x.Let A_{p,k} be a random variable indicating the value of the power of p after k steps. Our answer is
since as we just saw Ap, k's are all independent
sigh I'm just bad to not being able to draft this out.
Thanks for the help, it's crystal clear to me! ;)
This is beautiful! Thanks!!!! This was a completely new fact to learn.
You can do a induction over k.
For n = a·b and
, and D(x) being the number of divisors of x.
We have:
Because of the induction hypothesis we know that
Therefore:
This is exactly what I was searching for. Thank you so much!
You mean: "dp(d1·d2, k - 1) = dp(d1, k-1)·dp(d2, k-1)." in the line after: "Because of the induction hypothesis we know that", correct?
Yes
It's also possible to prove it by noticing that performing one step on n is equivalent to calculate s / c where s is the sum of divisors and c is the number of divisors. These functions are known to be multiplicative. From there, you can use induction.
What's the intended complexity of E/G?
I have O(Nsqrt(N)log(N)) in E (I hope it passes with some pruning) and a heavy O(NKlogK) in G (most probably it's too slow).
I'm really curious about E. What's the threshold for f()?
f(n) = 1 for [1, 2], 2 for [3, 5], [6, 9], [10, 14], [15, 20], and so on.
How to decompose a seqeunce of, for example, length [55, 65], into 10 parts? If the length of LIS is at least 11, remove it and repeat the process. Otherwise let dp[i] be the length of the LIS that ends at position i. Since there are at most 10 distinct values of dp[i] in this case we can decompose it into 10 parts (If we only look at elements with dp[i] = c for some constant c, this is decreasing.)
Yup. And we can consider the permutations of the following form:
(concatenated decreasing sequences of lengths 1, 2, ...,
k). It's possible to prove that this permutation needsksubsequences in any partition.We have
in E. We came up with plenty of LIS implementations and even the slowest ones fit in a second or so.
G can be solved in O(NK).
So what was the intended solution? Because greedily picking the longest sequence seems to be O(N1.5logN) but gives WA.
Apparently my LIS implementation is exceptionally slow then.
How to solve D? I could see that the expected value was a multiplicative function, but values for prime powers were not having a nice form either.
The expected value of f(n, k) is the product of f(aipi, k), where ai is a prime factor of n and pi is the maximum value such that aipi is the factor of n.
Yes, that is same as saying f is multiplicative. But how to compute f(a_i^p_i,k)?
Consider the naive DP approach to the original question. Denote dp[i][j] as the expected value when i replacements are done and the current value be j.
Then
for all t that is a factor of j, and n is the number of factors of j.
The base case is dp[k][t] = t.
Just use the same approach for each set of prime products, and of course you are not to use the values as indices.
You can just DP the values for prime powers
You mean using the recurrence, (a+2)f(p^(a+1),k) — (a+1)*f(p^a,k) = f(p^(a+1),k-1)? Wouldn't that be too slow?
EDIT: fix one-off in indexing
Let DP[i][j] = f(pi, j). We can init DP[i][0] = pi. Then, For all j from 1 to k,
Calculating the values is trivial in O(nk) by precalculating the mod. inverses, and looping i up, keeping track of the sum.
Our answer for this prime is just DP[n][k].
I think you mean DP[s][j-1] on the right. It is the same as I have written. (i+2)*dp[i+1][j] — (i+1)*dp[i][j] = dp[i+1][j-1], if we keep track of the sum in your formula.
Ok I see it may not be slow, since n has atmost log(n) prime factors, this will be done in less than log(n)*k*O(1) iterations
Problem D, if n = 6 and k = 2 then why does 1 has 9 ways? I could just figure out 4 ways:
Probability for all of them is different!
You are not taking in account the probabilities.
6 6 1 — 1/4 * 1/4 = 1/16
6 1 1 — 1/4 * 1 = 1/4
6 3 1 — 1/4 * 1/2 = 1/8
6 2 1 — 1/4 * 1/2 = 1/8
Sum = 9/16
Oh, i forgot about the probality. Thank you
For n=6 and k=2, 1 has only 4 ways.
The system testing that's still pending but running at the same time and gives failed systest on A for everyone seems broken.
UPD: Now it gives AC, but the rest is still wrong.
UPD2: Now it's ok, but it said "system testing, standings frozen" for a while.
сложно быть туристом — не занял первое место получай минусы :)
Could someone please explain/provide a hint for solving D.
Great Hint: In this problem E(XY) = E(X)E(Y), gcd(X, Y) = 1.
Not sure if this will get AC because I didn't manage to get it working in time but here goes:
get divisors of n by looping from 1 to sqrt(n) (O(n^1/3) can be used for number of divisors) O(10^8)
build directed graph with divisors as vertices and edges going from a number to its divisors O(10^10)
use DP to calculate probabilities O(10^4*10^10)??
never expected that bitset.count() is so fast. is it supposed to be O(N/128) or its constant is low like everything else in stl?
I thought it's supposed to be O(1)
In GCC it's O(N) (proof).
Depends on flags. With -Ofast -march=native, it's O(1): godbolt
Bitset .count()'s "complexity" then of course is n / 64 * O(__builtin_popcount()) = O(n / 64) (probably even faster due to vectorization)
I am not care about contribution, but it's anyway annoying to get downvotes for the correct answer for non-trivial question. Dear green's and lower, do you understand that with such behavior you demotivate people to give answers for questions and to share their experience? Imagine that once your question can be ignored because of that and you will be left alone with your problems.
What was wrong with the solutions to G that failed on test #4?
Was it possible to do D without using the prime decomposition of N ? With a DP over its divisors
But when you know divisors, you know the prime decomposition too.
I meant without the optimisation involving the prime decomposition but I just saw its impossible I'm still wondering why the fonction is multiplicative
Cool C and F. Awesome intro-statement for Um_nik problem.
B bad for beginners, E with bad limits — it's terrible that many people come up with
and thought it would be too slow (or: limits wouldn't be so tight then). G is quite standard, and H is tedious to implement.
7/10, the contest could be better, but it was fine.
why is B bad for beginners?
Implementation, zero thinking. And then there is a jump to much harder to solve problem C.
It's very hard to choose good easy problems. I try to avoid bitmasks (or similar) for example, because some people might not know them. More or less, I remember times when I started programming and I try to invent such problems that are solvable by thinking for such a kid. In my easy problems, one of the best ones was: Given a graph with N, M <= 2000, count triangles (triples of pairwise connected vertices).
Are you saying that it's too straightforward? Or that you need some knowledge to solve it?
In my programming contest experience, iterating over subsets of a set (for example, using recursion or building the subsets iteratively) was one of the first things necessary for me to learn.
Explicit bitmask is not required though: one can do the knapsack DP.
Or O(2^n) recursion
How do you solve F? I figured bitsets would easily do queries 1,2,4 but spent over an hour unsuccessfully trying to work out a bitset solution that works with query 3.
I stored bitset "is the number of elements divisible by x odd". The third operation is then just bitwise and.
Yeah, bitsets work.
Set bit i of set j to 1, if there is an odd amount of elements in the set divisible by i. Then join is xor, multiplication is and.
I think E is very cool (Though I agree that constraints should be lowered. I see no bad polynomial solutions).
Is G really standard? For me O(NK2) or KlogK with FFT was quite standard, but then got stuck for like an hour to improve it (and still I have no idea).
I don't like H neither, sorry.
For G, I think you can improve the NK2 to NK + N / K * K2 by simply computing a subtree dp only up to the subtree size.
Well, in E there are some heuristics which use randomization. After guessing the function you can erase random LIS or LDS and if you've ended with too many sequences — repeat. I wanted to cut it.
For G, you can get AC with O(NK2) solution. Example: 47935104.
Polynomials multiplication is good for SIMD optimizations. And compiler can do all the work for you, if your code would be simple enough :)
Check https://godbolt.org/z/2r_bdG for nice comparison of source and assembly codes. You may notice, that lines 95 and 90 (most nested part of source code) are assembled into operations with 256-bit registers (ymmD).
Yeah, but I don't like it when knowing how to write a fast solution to a contest problem, or knowing that some solution is fast, depends on knowledge of hardware features like SIMD or cache. It can even break problems where the author doesn't realise that some bruteforce can be very fast.
E in
? Radewoosh, go fuck yourself with such limitations.
I would spend less time on this problem if I would code it right after coming up with solution.
Hahaha, I really agree with you on expected complexity, however I think it would be great if he followed the footsteps of your iconic comment https://codeforces.me/blog/entry/49932?#comment-339270 and replied "Also, I've consciously chosen TL to fail people like Um_nik" or ""I would spend less time on this problem if I would code it right after coming up with solution." — that's exactly why you didn't get it accepted" :D
Goddamn, did you remember that comment for like 2 years? holy sheet.
You would be surprised how my mind is capacious when it comes to anything related to competitive programming. We just really liked this comment so it stuck in our minds — probably many of you remember gags like sorry_dreamoon or notorious coincidence even though they were long ago as well.
How do you solve C? I tried my solution many times but it kept failing on test case 4.
have u handled strings like )((( ?
what is hack for problem B?
For example 6 179 179 179 179 2 6
I hacked with
and with
The answer to both should be YES.
how can we reach 0 in first test case?
170 + 160 + 150 — 120 = 360 = 0
MikeMirzayanov During this contest I was unable to hack in Qutebrowser (version 1.1.1 based on Chromium 56.0.2924.122) and in Firefox (version 64.0). I was able to view the code, but when clicking Hack the input field for the hack didn't load and I only saw a spinning wheel. Only with my third browser, Chromium (version 71.0.3578.80), it worked.
I'm sorry if this is not the right place to do it, but during the contest there was a participant in my room who obfuscated his code (as you can see here: 47912509). I couldn't find any report button so here I am. Is there anything that can be done? Thanks in advance!
In problem C, what's the answer for the case:
4
(()
)
((
))
The pairs 1 — 2 and 3 — 4 form the same bracket sequence (()). So the answer is 1 or 2?
1 — 2 does not form a bracket sequence.
I fixed, sorry
If second string is ")" answer is 1. If second string is "))" answer is 2. You don't care if some pairs form the same bracket sequence.
"The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair"
Reading this i think that each bracket (form by a pair) has to be unique. In this way the problem became significantly harde.
When it says "each bracket sequence occurs in at most one pair" does not mean that the result should appear once. Means that you can pick every element and add it to one unique pair and not to multiples.
Ans:2 we need the highest number of pairs of correct sequence. No need for finding unique sequence of the pairs.
Problem D :
dp[n][k] = (1/x)*dp[divisor_1][k-1]
+ (1/x)*dp[divisor_2][k-1]
+ ..... + (1/x)*dp[divisor_x][k-1].
Here x = number of divisor of n.
dp[n][k] will be like this for example : dp[4][1] = {1*(1/4) , 2*(1/4) , 4*(1/4)}. and so on.
PS : Here one optimization is instead of taking divisor as dp state we can take divisor count as first dp state as only number of divisor matters for expectation.
For example 4 will have 3 divisor and so does 9.
dp[4][1] = {1*(1/3), 2*(1/3), 4*(1/3)}
dp[9][1] = {1*(1/3), 3*(1/3), 9*(1/3)}
We only need to count dp[3][k] -> here 3 is count of the divisor and not number it self.
for F its my solution of F 47939459 get MLE, but any other AC solution's memory (bitset <7001> bs[1e5+1]) just like my solution, whats wrong with my solution?
I assume you mean problem F (not G).
Your
int gc[7001][7001];takes ~186.97 MiB, andbitset <7001> bs[100001]takes ~83.54 MiB (these figures are not exact). Summing up, they take ~270.52 MiB. Sorry to hear that.Tnx
20 minutes delay on a problem --> 1000 positions in the standings. Gotta love this difficulty distribution.
When you solve A,B,C and your C get runtime because your vector size is 1e5, but need 5e5
Exactly.
Can someone help me with the Problem C? my submission1 failed, I changed unordered_map to map, and instead of for(auto x: m), I used an iterator to loop, The solution is accepted. I couldn't figure out what was the issue I had?
Submission1
Submission2
int b = m[-1*x.first]; This one potentially changes the map (if key -1*x.first wasn't in the map). Which breaks iteration over it (if it's unordered_map).
Spend 2 hours debugging same issue :(
Thanks, I created a blog for this before checking your reply, btw it (unordered map) was passing with clang++17 diagnostics. Do you have any idea why is it so?
Well, I don't think clang++17 diagnostics (or any automatic tool) can catch all possible bugs in the code.
My screencast will be available here: https://youtu.be/UxtEMlc0sHM , including getting problem H correct 30 seconds after the end of the contest (just checked in upsolving), which would be just enough for the first place :) Oh well.
quality is 360 , couldn't see anything .. blurred . increase the quality to 480 or 720 Petr
Wait for the video to render...
So why THe function Expectation of D is Multiplicative ?
E(XY)=E(X)E(Y) if X, Y are independent random variables.
I know it's a multiplicative fuction (by brute force),but how to prove ?
See good formal proof above.
What happened to CF-Predictor?
Probably too many F5's.
Apparently it runs in a free heroku instance, so it might have reached its maximum traffic allowance or something like that.
Yeah I too thought of the same, thanks :)
That was a nice contest but i love that editorial.
and where is real editorials ?)
Probably the worst combined round in Codeforces history, imbalanced and not interesting problems, didnt expect it from Radewoosh
At least problems E and F had really nice solutions, G and H looks interesting. Maybe balance wasn't the best, but it's really hard to balance contest correctly and it happens in 80% of contests.
Sorry, but I can't find "hack it!" button on anyone's solution. What it might be? Tried already in Chrome and Edge.
Have you locked your solution first?
how to solve c?
There are 3 cases. The first one is when both of sequences are valid. They are valid, if stack is empty in the end(read about correct bracket sequence). To solve other two cases we have to calculate count of needed brackets in our invalid sequence. For example: (()( to "close" it we need two brackets like ")". Lets define it as need_right. It was the second case. The last one is need_left, i.e. count of brackets needed to "close" for example, this guy )(), need only one from left. It is easy to notice, it's impossible to make our sequence correct, if there is a sequence, that needs brackets from both sides, like )(. So, just push these values into two vectors, sort them and get your answer.
real editorial would be nice
Plot twist: that is the real editorial.
How to solve problems A-H: Never Give [the problem] Up
problem F: bitset pleeeease
LOL
Hi. Can someone explain problem B? Is it well-known algorithm that everyone used?
notice that n <= 15 if n = 15 you will have 2^15 combinations which is small. You can thus try all combinations (at each step, you can either rotate clockwise(add to the current angle) or counterclockwise(subtract from the current angle)). This is very similar to subset sum problem but here you don't have to use DP because n is small. That screams recursion.
Recursive solution: https://pastebin.com/k6AwE2ur .
It could be also solved without recursion like this: iterate over all 2^n combinations like this:
For each mask, iterate over all elements in the array. The current mask describes the state. For example if mask's binary notation is 10111 means that try this combination: *rotate clockwise the 1st,3rd,4th, and 5th elements(clockwise) (positions with 1s). *rotate the second angle counterclockwise (positions with 0). At each state, compute the final angle(adding when bit is 1 subtracting when 0) and check if final angle % 360 = 0.
iterative solution: https://pastebin.com/F9y9vM75
In problem D, how 15/8(mod 10^9+7) = 875000008 can anyone explain to me how to calculate this? thanks
According to Euler's theorem if p is prime and n is not a multiple of p then n^(p-1) = 1 [p] Thus n^-1=n^(p-2) and here 10^9+7 is a prime number
Can we now have the actual editorial please?
Where did my rating go?
Radewoosh?
What happend
how to solve B.i am new at programming.please help
Just think in trying all versions (if you turn wheel by a[i] to the right (ans+a[i]) or to the left (ans-a[i]) ). Then check if any of final answers is divisible by 360 (because then it is on 0). Complexity is O(2^n) and on worst case n=15, so it passes time limit.
more details please..brother
check my submission and try to figure out what am I doing.
Does anyone here have successfully solved problem C??? I'm just a kiddo and I am new to coding please help meee I just can't have the faintest notio of it. T.T thanks if u can help
You can divide all the brackets sequence into 4 cases
For case 4 it's obvious that you can not make a 'pair' out of it because it needs at least 2 more sequence to complete it.
For case 1 it must match with another case 1 sequence (Perfect+Perfect)
For case 2 and 3 we just need to match the sequences that X = Y
How to find the answer I'll left as exercise :p
PS. Just a reminder(I think you know this already). To find the case you cannot just take number of '(' — number of ')'. For example, ')(' is not case 1 , but a case 4 because it lack 1 opening and have 1 excess. '(()' is case 3 with Y=1. '())' is case 2 with X=1.
[DELETED]
D/E is very cool. Thank you!
Suddenly screencast
After some searching on codeforces, I found who are Gennady, Petr, Makoto, Egor, Alex, Vladislav and Mateusz. But who on earth is Yuhao on problem C?
jqdai0815
A round with two editorials emmm
Please remove the UPD1 editorial now as the contest is already over and so is the fun of the click-bait. Now it just creates confusion.
Why are there two editorials and first one directs me to some singing guy?
В задаче D что значит "число 58 — сид этого генератора"?
What does this info in task D "as he always uses 58 as his generator seed" mean???
I got WR in problem C with this code using unordered_map 47928656 but I got AC After the contest using map in the same code 47970451 . what the different between them ?? Radewoosh MikeMirzayanov...
I'm not really sure about it, but it seems that modifying the unordered map while iterating it is a bad idea and can lead to the undefined behavior.
Why? Here:
mp[it.first] = mp[it.first*-1] = 0;you can accidentally insert new keys to the hashmap (which can happen e.g. when key5exists in the map, but-5does not). This can lead to the rehashing of the hashmap (the hashmap rebuilds from scratch if the number of elements in it is too large compared to its current capacity). Yet, the range loop in fact takes an iterator to the hashmap and advances it over and over again. Now the hashmap can be somewhere else in memory, and you're trying to iterate over the hashmap (which might be already gone...)Same story can happen with vectors: https://ideone.com/ds4Rkp. (WTF, why are there zeroes in the output?)
I wrote a tutorial of problem G. https://codeforces.me/blog/entry/64367