Hello everybody!
Congratulations to the platform Codeforces with an Anniversary 450th round!
We are glad to report that Codeforces Round #450 (Div.2) takes place on December 11 19:05 MSK. The round will be rated for Div.2 participants. Traditionally, we invite Div.1 participants to join out of competition. I hope stronger participants also will find interesting problems for themselves:)
The problems are created by me and Nikita slelaron Kostlivcev. We want to show our great appreciation to Nikolay KAN Kalinin for round coordination, mike_live and Arpa for testing the problems and of course Mike MikeMirzayanov Mirzayanov for great platforms Codeforces and Polygon.
You will have 5 problems to solve in 2 hours.
Scoring as usual: 500 — 1000 — 1500 — 2000 — 2500.
Good luck to all and enjoy the problems!
UPD: Contest is finished! I hope you enjoyed the round:)
UPD: Editorial. The problem E will be posted soon.
UPD: The problem E was posted.
Congratulations to the winners!!!
Div 1
Div 2
Jubilee for codeforces, the first for me)
Good luck :D
What's Jubilee?
Anniversary round.
Thanks. Changed in the post.
5 div2 contests and 1 div1 in 9 days? already best december gift
is it semi-rated ?
Actually that's interesting point. You can generalize it a little bit. I saw previously some comments whether it would be 0,25 rated, 0,1123 rated, etc. I would go even further. For example it could be 2 rated, which means that rating change would be doubled. It could even be -1 rated, which means the better you do, the worse rating gain.
It could be an x rated round with x being a real number. We could also count the expected value of rating ratio. I think currently it might be something around 0,75-0,8 rated round.
What if we add complex numbers too, so a contest can be z-rated. Therefore we’ll need to add another dimension to the rating graph.
And now there are even more possibilities by adding the "Educational" prefix to the previous ones.
Is there exists a real number
such that it is x-rated?
+18
And the fun part begins when participants can choose the value of x before the round. So its like a gamble you take before seeing the problem. Could be a fun little thing to do in codeforces.
But you can still look at the authors. :P
The setter must have seen all these values in the comments and hence comes div2 B.
he did not say "the scoring will be announced shortly before the start of the contest." This is a miracle xD
Five contest in ten day
NANI!
Typical Div 1 users: "I will just create a new account participate with it. So I can ruin other Div2 users."
Why would we do that? My skills have regressed so much that I can't even clear a div2 round ... (*sobbs in a corner)
5 contests in 9 days Indians be like:
)
Google translate has left me even more confused
"Bro if someone will choke me and chill, lots of fun will do the code for fores"
It means that if someone will tell me to chill and have fun then I will do Codeforces Rounds!
Been looking at red username for so long I thought Anniversary was a person
i am, although not red yet :(
Anniversary hmm...
Too bad the account was made 13 hours after the blog.
I only realized it wasn't a person when I clicked it.
Deleted
Hope you make progress and show yourselves!
For God's shake resolve servers' issues before the contest!
3 rated contests in a week, week of the FINAL EXAMS for God's sake...
Meanwhile in China we have the ICPC East Continent Final in the upcoming weekned, failing final exams here I coooommmmmeeeeee
It's to late for Chinese coders. I can only participate the next one. 555
Why the frequency of div1 contests so low? We want more div1 contests.
Because div2 users> div1 users.
it is hard to create hard div1D-div1F problems so just relax
May God bless the servers !
May God bless you too !! Hope so you will not become newbie as you seem again. I would suggest work on the problems rather than just complaining. Also in case of server doesn't work well it will anyway don't affect your performance because you are still not capable of solving even C problem in any contest :D
Trying to get upvotes lol -7 contribution xD
I said the truth. Why are you defending her? Is she is your sister or girlfriend? I wrote the truth because I usually got annoyed when someone who is not at all good in cp and just keeps on complaining about Codeforces which I personally feel is the best competitive programming site in the world.
maybe after writing this she became my girlfriend lol
Servers affect everyone, sometimes people will end up being higher than they would have if there was no server issue, and sometimes they will end up lower. Whether or not you are good does not change the randomness that affects you with server issues. You can be "bad" and still place lower than you should have.
Moral of the story: Codeforces is a good competitive programming site but you're a douche.
I m sorry if the truth hurts you as well !! Isn't better instead of finding mistakes like pragya_123 stupid girl is doing we should suggest how to improve the Codeforces and make mike and other Codeforces team motivated so that more learning can take place.
[deleted]
Nothing is perfect in this world! Yes, I'm not able to solve C problem. But, it was my general comment for all the coders who suffers sometimes due to slow server! If I'm trying to improve myself, so should codeforces too so that everyone can perform efficiently during contest!
Ohh really you are trying to improve yourself but i m sorry your graph shows the opposite. After 14 months you are a pupil and you say you are improving :( Anyways don't you get you are not made for competitive programming after so many failures you have? Rather you should try modelling or reporting who keeps on complaining.
Lets not pass personal comments
KAN+Anniversary=Kanniversary
Just In case what we all expect happens =)
Reminds me of Lucy
Hello darkness my old friend..
I dedicate my success in today's round to my two senpais: FLEA and babin! Btw I hope babin didn't cheat today!
What the... video
There is one thing i have to say: You guys have made the BEST round ever! Your statements are the BEST!
OMG D is so easy!! I wish I didn't waste my time attempting to hack. :(
Okay, maybe not as easy as I thought. we can't just do "distribute k sweets among i students" because we also need to make sure gcd doesn't become some multiple of x.
What is test 3 in C?
Test cases in C : 6
2 3 4 1 5 6
6
1 3 2 4 5 6
2
2 1
Probably: 2 2 1 Not sure though, ans = 1
Ahh, thanks :)
write brute force find sequence google it find sequence on OEIS with formulae == DIV2 D
Link?
https://oeis.org/A000740
doesn't to_string() works on codeforces ??
if for B you will get precision error, i think to_string() works on cf
Is the answer to question D-Unusual Sequences simply 2^(floor(y/x)-1)-1??
https://oeis.org/A000740
How do I use this?
There is code on python below ("Prog")
I tried the same thing but I got WA
Really cool problemset. Hope more like it are coming!
How to do D? Got it down to finding all sequences of numbers that sum to y/x with gcd 1.
Yeah, even I got it that far then I didn't know how to proceed
DIV2 D https://ideone.com/PvYJio This is the link to my DP code. Just got 1 minute late in the contest.The DP code itself is self-explanatory.
I'm not sure I understand lines 105 to 115. How do I show that the number of sequences summing to x with gcd != 1 is the sum of solve(i) for each divisor i of x?
Exactly what Alei said.
For finding number of sequences summing to x with gcd != 1: You can substract sum of solve(i) { Sum of number of sequences summing to x with gcd = n/i where i is a divisor of x } from power(2,x-1) { Total number of sequences summing to x }
Time complexity of your solution?
Inclusion-exclusion:
add the number of ways when the numbers are multiple of g.
remove the ways when the numbers are multiple of g multiplied by a prime
add the ways when the numbers are multiple of g multiplied by two distinct primes
... and so on
What is the idea behind B & C ? :(
B: Java BigDecimal with "a lot" of extra decimal places, then just string.indexOf(c). That pass the system pretests.
System Test Pending
I said pretests.
For B, you could actually code it like you'd do long division in real life. Store the digits of the quotient in a vector. Whenever an intermediate dividend is attained twice, break the loop, possibly using a set. Then just check if c exists in the vector. If it does, just print the position(1-indexed) and if it doesn't print -1.
For C maintain a map/dictionary/hashset with int, bool with values for if the number is a record before removing any number. Then take max(p[0], p[1) as maxsofar and the other as secondmax. Now iterate through all numbers. If they are bigger than the secondmax then that means you only need to remove the maxsofar element to make that element a record. Store the frequencies of what number must be removed in a map. Then just check the max value of frequency and in case of a clash, the minimum of the two. You'll also need to subtract one of the frequency for a particular element if it was previously a record because in removing that number you'll also reducing a pre-existing record.
The problems and the statements were excellent. Although to me E seemed a bit easier than usual.
Good job :)
You can find D here https://oeis.org/A000740 Is it okay?
Yes
Can anyone explain how to solve problem C?
sorry my poor englishh, you can compute current records, if i'th element less than only one element on previous all elements, you can push vector <pair<int, int>> these elements, first is p[i], second is only one element that (p[i] < p[j] && j < i) p[j], if i'th element equal this vector's second element current_ans + number of vector's elements (v[i].second == p[i]) then, if i'th element also record element current_ans — 1, you can finish this problem.
Is the first element considered as record?
yes
A somewhat different(maybe) approach:
For each element find number of elements less than it and before it in the permutation. Get all elements such that there is exactly one element before it that violates the condition of this element being a record. Say we store them in
cNow for each element find all elements greater than itc. Observe that we can get number of records inO(1)for each element being dropped.Note: All of the above computation can be easily done by a merge sort tree
thanks for very short conditions))
semi rated meaning ? sorry I am new !
It's only rated for Div.2 users
This was the best codeforces contest so far.
In my opinion problem B,C,D,E were from almost same difficulty level. So the order one attempts the problems matters a lot in the standings. This is certainly not good for the contest.
In my opinion problem B,C,D,E were from almost same difficulty level.Please tell me it is joke.
When did you reach on problem C , I mean what was the time ?
What do you mean? B was easy problem, but I stuck on it, so I read C and googled solution of B (fortunately, found). C was quite standard problem, it was easy to get idea fast.
What's the point of googling the answers though
you can see standing on this round
if you tell me about it during contest, i would solve D, E.
Problem E can be solved with FFT?
yes with fft we can find from what all positions there is a possibility of t being there. the idea is for finding at pos i we need ((s[i+j]-t[j])^2)*(s[i+j]) summation over j from 0 to m-1 to be equal to zero assuming value for character '?' to be zero and rest some positive value. This we can find for all i using convolutions(which can be solved by fft).
NOTE: We are not using any special knowledge about t here.
E can be solved without FFT, bcs of t="abababa..."
we need FFT when t is arbitrary string
Yes, the idea was finding the number of wildcard matching in strings, which can easily be solved using FFT. I was trying the same, fell short of time. After this was a simple DP solution.
For fft, technique try to find the following sum,
. The places, it is 0 are the places where the string T can match string S, from position i. Expand the expression, which is simply prefix sums and one convulution using FFT. Using FFT in this problem, we can do it for general strings as DP is independent of it.
This is actually what is explained in above comments too.
http://mirror.codeforces.com/blog/entry/49613?#comment-335977 this can be used to solve it for any pattern (not limited to "ababababa...")
Nice background for coding :P
In problem D, I forgot that the answer is 1 but no 0 when x=y...sad story:(
is that corner case?, if yes too sad
My friend and I always wrong answer on test 3... And when x=y our answers are same to 0 :(
it is not corner case.
system testing too slow :(
How many iterations do we need to prove our "-1" answer in B? I did 1e5, it passed final testing, but I saw div. 1 users did more, just for precautions?
I couldn't find any answer greater than 50. You can prove a bound O(B) using the pidgeonhole principle on the number of steps until finding a cycle.
Nice problems! Thanks!
nice problems, can't wait the editorial. short statements <3 ++respect
Update: I'm sorry for such a comment. I understood.
LOL problem setter,poor test case on problem "B"-div-2.
if input is 22 4 5
answer should be 1.
but I have found -1 from many accpeted code.
How how how????????????
And why should the answer be 1 and not -1 can you please explain?
4/22 is a repeating fraction and 5 never comes in the sequence. Please have a look once before posting
sry.
input 22 4 5
I have found -1 from many accepted code
Read the constraints.
a<b is a constraint.
Ummm.. Answer is definitely -1
4/22 = 0.(18)
5 cannot be found.
sry, 22 4 5 input
Because they guarantee a < b
uffffffffffffffffff...
I got it..
Sorry for the comment......
They've stated a < b. Read the statement before making a comment about setters.
tests of problem C were weak some incorrect solutions passed system tests. For example simple test 2 2 1
There was no repeating numbers in the sequence, so your example is invalid.
From the statements: a < b.
Hey mike, talking about problem C
If n <= 2 output is always 1
How to solve C?
You basically keep current maximum and second maximum on the array as you iterate. Removing maximum element will add record
if(a[i] > maximum2 && a[i] < maximum). The rest is easy from here.Could you please clarify a bit more. I had thought something like this during the contest but my doubt is this.
Suppose we have
1 2 5 4 3Now when a[i]=4 we have a[i]<maximum and a[i]>maximum2 so removing this should add a record. Well it does make 4 a record but how is the number of records maximized? In1 2 5 4 3we have two records 2,5 and in1 2 4 3we still have 2 records. So the number isn't really maximised is it? And since the question says that we need print the smallest number which maximises the total (which we cant in this question) shouldn't we print 3 as its the smallest but the number of records are still 2?In my opinion, I think it should print 3……emmm...what is Judy's answer?
Thats why I said in my comment, you have cnt array which tells change, and you set cnt[i] to -1 if i is initialy record (not index i, but value i of course). So here you would have cnt[5] = -1. Later , cnt[5] gets increased only once, because only 4 will become record, so cnt[5] =0. Since cnt[1] = 0, solution will be 1, not 3 or 5 as you said. So we dont look who makes most new records, we only look for change in records. Thats why answer will not be 5, but 1, since cnt[1] = 0 ( it is 0 because 1 is not initial record, we only set cnt[i] to -1 if it is initial record). Hope this helped.
I implemented a solution which is n log n
We will keep an array V, such that V[i]=the amount of new record numbers created if i is deleted. Then for each element Ki, we ask, is there only one number smaller than it in the range [0,i-1] if so, to that position in V we add 1 since by deleting that number we add 1 new record number (namely Ki) after, we Iterate through V again and if i was a record number we subtract 1 from V[i] since deleting would remove 1 record number.
Finally we find x so that v[x] is maximum and print x
i became purple for the 8th time
9 9 5 8 6 3 2 4 1 7
for the given case how the answer be 9?
here if we remove 1 then the permutation will be 9 5 8 6 3 2 4 7 and we get the maximum record which is 3 (2, 4, 7) isn't it?. then shouldn't the answer 1?
No, if we remove 1 the record numbers are (9) and removing 9 they are (5,8)
that's mean the record always starts with the 1st element?
there is no "record" to keep, being a record number is a property defined in the problem statement, read it again
For problem C, the pretest 3 is:
5
4 3 5 1 2
Accepted output is: 1
My program gave output: 3
I didn't understand why the output is 1. Probably I have misunderstood the problem.
For this input, I thought that if 3 removed then there would be 2 records: 4 and 5 ( because after removal of 3 the sequence would be- 4 5 1 2, the increasing sequence is 4 5 and then 1 is less than 5,so sequence breaks here)
But if 1 would be removed then there would be only one record: 4 ( because 3 is greater than 4, so the increasing sequence would break here)
Where I had misunderstood? Thanks in advance.
The sequence will be 4 3 5 2 .. 4 (larger than 3) and 5(larger than 3 and 4) are records.
since 1 < 3 then the answer will be 1
The problem isn't asking for the longest increasing subsequence, it's asking for the number of indices such that a[i] is larger than a[j] for all 1 <=j < i
How 4 is a record? def says 1<=j<i?
The first number in the sequence is always a record since it's already larger than all the previous numbers(in this case none).
Thanks Understood now.
Hi!
In problem D, I found a correct solution that should be TLE.
If I run the code in this accepted submission: http://mirror.codeforces.com/contest/900/submission/33138278 , against case "1 999999527", it lasts like 15 seconds.
It really surprised me that it got Accepted.
Why the answer is 1 in prob. C,why not 4? 5 4 3 5 1 2
Something is wrong with the input. The numbers are permutation of the first n numbers.
Also in the question it was mentioned that we need to print the smallest of all the elements which when removing gives us the maximum number of records
The input is
The Prob.C says that "a1, a2, ..., ak the element ai is a record if for every integer j (1 ≤ j < i) the following holds: aj < ai." And if I delete number 1 , then it is "4 3 5 2", only a1...a1 is ok But if I delete number 4 , then it is "3 5 1 2",the a1...a2 is ok? If I misunderstand the meaning , please tell me ,thank you
The way i've interpreted the problem, which I'm not entirely sure is correct is something like this.
When we have
4 3 5 1 2there is only 1 record 5 as for only this i we have a[j]<a[i] for all 1<=j<i.If we remove 4 then we'll have
3 5 1 2now too the number of records will be one because 5 is the only record. In fact if we remove any number other than 5 then the number of records would be one. As we need to remove the smallest number for which the number of records are maximised (which is one in this case) we remove 1.I'm not entirely sure but this is what I think the question means. Although I've got a doubt against this too. Over here. Maybe you can help if you understand my doubt? Cause I myself am not sure if i've correctly understood the question.
Oh, thank you. Let me see your doubt...
Oh, I see ,does it mean that the a1...ak don't have to be consecutive? For example , as "4 3 5 2" I can choose a1,a3 to be a record?
What category of question does problem E, fall into? Can someone suggest similar problems.
Dynamic Programming
http://mirror.codeforces.com/problemset/tags/dp
Wow..That's my first time solved all problems in div2,Thanks for writers!
How to solve problem C?