The end of the December is fast approaching and it is time for the best last contest of the year! The Good Bye 2018 round will take place on Sunday, December 30, 2018 at 14:35 UTC.
As the people who already engaged in discussions about the ultimate problem suspect, I am the problem writer. As such, I'd like to thank to:
- arsijo and KAN for the round coordination and one of the problems,
- AlexFetisov, cyand1317, Errichto, Jeel_Vaishnav, Lewin, misof, winger for testing and invaluable suggestions,
- MikeMirzayanov and everyone involved in building and running Codeforces and Polygon platform.
The round will last for 2:30 hours and you will be given 8 problems for both divisions. There will be an interactive problem.
You have the last opportunity to reach Your rating goals for 2018. Good luck!
UPD: The top 3 participants eligible for ICPC 2019/20 season can win a great prize.
UPD2: The scoring distribution is 500-1000-1750-2250-3000-3000-3750-4000.
UPD3: Round is finished. I hope you enjoyed the contest! I am really sorry for the duck-up in problem G. I'll share more details once the important things (systest, editorial ...) are taken care of. The systest might be slightly delayed because of that.
UPD4: Editorial
UPD5: We apologize for the issue with problem G. We are still investigating this issue. Verdicts “Idleness limit exceeded” may be changed to other. We will write a full report about it later.
UPD6: The results are final, rating will be recalculated shortly. Congratulations to the winners:
please, add Eve to the tags
Are you crazy? Eve is a criminal!
Eve makes the problems fun, she deserves to be in the main page.
On the other hand, she adds Christmas-y feeling.
Who is Eve?
See here
You just changed the way how I perceive EVE for the rest of my life.
I always enjoyed contests from majk. Hope to see something interesting for the last contest of the year!
Looking forward to it :))))
I am so sorry, but is it rated?
Did you just missed this? "You have the last opportunity to reach Your rating goals for 2018. Good luck!"
Oh, oh, oh I missed it men, I am so sorrrrry, Thank you very much, You are the best, You are better than tourist
Are you doing this to win Most annoying person on CF by Um_nik? You are doing pretty well in it if you ask me.
Best birthday gift ever! Thanks, majk!
Happy Birthday :DD
I don’t have good memory of goodbye 2017 hope this one overwrites that.
wait for the rating up！
Damn,
It might take CF 1 year to update the ratings.
No there is 31 December for updating rating :3
Might, mate.
"...you will be given 8 problems for both divisions." For (div. 2 and 1) or (div.2 and 3)?
Div 1 and 2.
Why is this post tagged with 'Alice' and 'Bob ? By the way, Happy new year in advance to everyone in Codeforces community.
Because I often use Alice and Bob in the statements.
"You have the last opportunity to reach Your rating goals for 2018"
This makes me kinda sad. As I feel like I won't be able to reach it.
Be confident...
Here's a list of past Good Bye contests.
who fricking cares
Newbies like me freaking Care, and I'm freaking worried about the fact that you can't spell "freaking".
EDIT:
The past Hello contests:
- Hello 2018
- Hello 2015 (Div.1) [Unrated]
- Hello 2015 (Div.2) [Unrated]
Happy New Year!!
Not exact.
Hello 2015 (Div.1)
Hello 2015 (Div.2)
Oops! Sorry for the inconvenience!
But I think they(Hello 2015 Contests) were Unrated CF Gym Contests.
Sure, but they are important because they're a origin of Hello <year>! rated series.
tfw my rating goal for 2018 was CM...
nvm, thanks to magic my rating goal is a (temporary) reality
Happy New Year to all!
happy new year！
TinTin122 don't miss this!
Thanks dude
kg16 try your luck on this :)!
so excited to back expert by end of 2018
if i dont get crapping expert this time i will do russian shooting
Just a little thought. Why dont codeforces make everyone automatically registered for every contest like codechef where we dont need to register for a contest ?
Because there are rooms in codeforces for hacking. If everyone is assigned to a room there will be alot of rooms and most of them are empty.
Last contest of the year, Wishing a very good rating for everyone...
Wow man, you're creating quite inspiring rating graph :). All the best for tomorrow's contest.
Good to see an Indian Problem Setter. Random doubt, Is there any contest that is from an Indian User?
Will this round be rated for div 3?
Yes.
Thank you!
Upvote me, If you think, I can cross 1600 rating in Good bye 2018 contest.
Downvote me, If you think, I can't !
Be honest with your opinions, that will motivate me to do hard-work !
Or just downvote him for spam comment.
That also fine by me :) kostka I upvoted you !
This contest was a quite challenging, enjoyable and memorable contest for me. I pushed myself so hard to reach that 1600 mark. I couldn't reach there but I ended up solving 4 problems.
Thanks a lot ! your contest is pre-new year gift for me. majk
You can win if you want
best pat of the year
Everyone else on New Year's eve vs me
When verdict of problem will be accepted and when will be "Happy New Year"?
Happy New Year when AC i think
Hope to All high rating.
Happy new year,guys!(So what does the tag"Alice and Bob'...mean?)
Every time i see this blog, majk color keeps changing :D
I am a fast learner!
Not like it's helping your Atcoder rating.
Are you competing today?
Maybe, if there's time. Hard to say, everything's messy around holidays.
And this is how it ends when I have people bugging me all the time during the contest.
2018 was a great year with lot of good contests hope this year be even better. thank to every one how prepared a contest and a special thanks to mike.
I hope that everyone can get high rating && change his/her handle's color by no magic.
First contest in cf history with more than 10000 registrations
I hope codeforces servers could handle the requests from this much contestants.
9000 and counting ...
DearMargaret ----> DearMargaret.
He doesn't want to achieve his goal anymore ?
His new username is just V--o_o--V without the specs :D
Happy New Year! Fun & high rating for all of you:)
But I have to warn, that CF-Predictor doesn't support handle change. So if you change handle, the prediction is going to be completely wrong (for the first time only). As there are some people who changed handles, today's prediction is going to be a bit inaccurate for everyone.
Don't be upset, just enjoying the competition!
It's about time that I become a specialist.
you are already a legendary grandmaster
missed by 2 points :)
It's biggest number of registrants ever
Будем надеяться , что сервера CF не упадут из-за 10к участников.
scoring distribution doesn't seem even
Good Luck! (:D)
\10000 Registration!/
Lets see if i can end this year with pupil
I suspect huge queues...
I freaked out when I opened the registrations page — lots of grandmasters :o. But then I realized they have just changed their colors :P
I already reached my 2018th goal (min 1600), but, damn ,this contest seems to be like a chocolate candy , cant keep my fingers from touching it. I hope for everyone steep positive slope in this contest.
however,good luck to the server!!
Total: 10312Will the CF servers be able to hold 10000 participants?
let's hope for a smooth one this year boys.
Been Newbie throughout 2018, time to pull out all I've got, to, at the very least become Pupil. I know the Purple, Orange, Red and Black Reds be like "Seriously, someone fighting to reach green??"
Most of us have been there, don't give up :)
All the best to legend Petr
hope he does screencast for it too
Will the fake colors be disabled for hacking purposes? majk, gotta ping real fast, sorry.
tourist is here.
tourist joined. Let the battle begins!
11444 candidates registered...
It'll be a fierce contest.
Best of Luck Guys...
Finally, I find a contest announcement with no one asking whether it is rated.
is it rated
You think it's funny?
Problem B: "As everyone knows, the world is a two-dimensional plane."
So the earth is flat?
CF Servers failed :( Denial of Judgement
Написал раунд Good Bye 2018 — Good Bye Rating
Petr hasn't solved problems A and B yet :O :O :O
He tries to get AC problem H, but solving problems A and B will take just 3-4 minutes for him.
UPD: Finished. He didn't solve them, neither he solved H :(((
Petr, please, solve problems A and B! Gain ~750 points!!!
.
After reading first 5 problems GoodByeExpert :(
No need for Expert ;) You are already Grandmaster!
\ps Actually same here :((( Also after reading first 5 problems "MathForces confirmed!".
Hacks for B?
Overflow
problem c was nice :D , how to solve D ?
n!+((ans for n-1)-1)*n)Don't know why it works though.How did you get this? :D
Observation ;)
I was trying different methods to get 56 for n=4 using the answer of n=3 i.e 9. Coincidentally the first method I tried gave the correct answer for 10 and it passed :)
A concatenation of 2 permutations will have the sum n*(n+1)/2 iff the suffix of the first permutation won't contain any elements from the prefix of the second. That mean that the prefix of the first permutation needs to have the same elements as the prefix of the second (when we are talking of some prefix i and suffix n-i). Now 2 consecutive permutations will satisfy this condition always except for one time when the suffix elements are sorted in decreasing order. For example: 1 3 5 4 2 , the next permutation will have some elements from {5,4,2} in the prefix. Now it's only the matter of implementation. For each prefix i add to the answer A(n,i) * ((n-i)!-1)
It should be clear that we automatically get n! subarrays, from the permutations themselves.
For a given permutation, look at the the length of the prefix that remains the same when going to the next permutation. For example, for n = 4 say the permutation 1324 appears at index i. from 1324 -> 1342, the length of the prefix that remains the same is 2 (because 13 stays the same). Then, this means that we get 2 more subarrays that work, i.e. the ones starting from i + 1 and i + 2.
The answer will be n! plus the sum of the lengths of these prefixes. We can calculate that recursively, given by the formula in the other comment.
So every subarray
pwhich works is a permutation of numbers [1...n]? Can't there be some other subarrays?So, this part was really hand wavy, but I think that a given subarray can have at most one duplicate, and if that's true then it would follow that every subarray that works is a permutation of 1..n. Not at all sure whether that's true, though.
EDIT: This is not true, as given in an example by DEGwer in the editorial comments. spacewalker's comment below is good justification though.
Still, thanks.
It is... at least in this scenario.
Every subarray is either a permutation of [1..n], or some suffix of a permutation, plus a prefix of the next permutation.
Consider some permutation P, and divide it into parts
R1 a R2 b R3such that the length ofR2 b R3is maximal, andR2 b a R3is decreasing. The next permutation algorithm tells us that the next one, Q isR1 b reverse(R2 a R3). Let's look at the subarrays based on where they start:So we end up with a range
R1 a R2 b R3 | R1 b reverse(R2 a R3). (The divider indicates where Q starts.)R1 a. Then the prefix of P we don't hit is precisely the prefix of Q that does intersect with the subarray. So it's a permutation of [1..n].R2 b R3. If you simulate moving the subarray start throughR2 b R3, you'll notice that the differences in sums of neighboring subarrays increase, then decrease. This means that the only time the sum will equalSo either the subarray is a permutation of [1..n], or it doesn't have the right sum.
Thanks for the full explanation. It explained well.
P.S. At first I was tricked by your fake grey color :D
We can calculate for each x, the number of permutations where suffix of length x is not sorted. All these permutations combined with prefix of ext permutation of length n-x will have all distinct elements.
As out of all x! permutations only one will be sorted.
This can be calculated as n! * (x! — 1) / (x!) for all x <= n-1
and simply n! for x == n
The sum of all these terms will be the answer.
(
( 
× i! × ((n-i)!-1))) + n!
This contest was the worst performance of mine ever.. what a great way to end the year :/ I really felt out of luck this time, spent an hour on D but couldn't guess that formula even though it seems I was close. Oh well.
same here ..
Please don't tell E was erdos gallai + binary search
But it was...
You supposed to not telling that.
That's what I tried, but the only thing I don't quite get is the range to binary search over, since the set of values that work (within a particular parity) isn't monotonic. I'm pretty sure it's an interval, but I don't quite get how to find a value in that interval to pivot from.
EDIT: nvm, seems like I'm misunderstanding what exactly you're binary searching on...
So sad. I didn't know this theorem. However, it may be more difficult for me to prove it during the contest. Thanks for reminding, and I'll learn it later. Thanks majk for a nice contest!
what a problem D is!
how to solve D.
The idea is: number the permutations p1, ..., pn!. Then, for each interval of length n, say [l, r], some part of it is in permutation pi and the rest in permutation pi + 1. Let's say that [l, m] is in pi, and [m + 1, r] is in pi + 1. Now, you need to make two observations: Between one permutation and the next, any prefix either is the same as the other, or changes in exactly one element. If pi and pi + 1 have the same prefix of length r - (m + 1) + 1, then [l, r] will have sum
. Else, they will not.
The second observation is that a prefix of length l will change every (n - l)! permutations, so in total, this prefix will change
times (the - 1 comes from the last permutation).
Therefore, to solve this problem, you notice first that if some interval is completely contained in a permutation, its sum will equal
. Then, iterate over all the sizes of prefix, and for each, add to your current answer 
. The result is the answer.
all math problems and i got hacked, gg
It was a year full of "well, I cannot prove it but seems a lot had solved it. let's try the intuitive solution. Damn! seems it worked".
Pretest 8 for B?
I think the test case is that which some coordinates are located in same row or same column. (But it is not certain.)
pretest 4 was more challenging
The difficulty of Problem D and E seem to be quite different. How to solve E?
any idea about test 18 problem E?
How to solve D: 1) Write bruteforce 2) output n*n!-bruteforce(n) 3) find this sequence in oeis 4) profit
I searched for this sequence for 30 minutes, but did not find it ((
http://oeis.org/A038156 n!n - that
This
Btw, is there a Hello 2019 where I can recover back?
1500 rating is not quite suitable for a Legendary grandmaster :D.
Yes there is, you can find it by going to the contests page.
Very interesting problemset. Does anyone know how to pass 18th test of problem E?
What did you do? My solution is a horrible bunch of formulas and pointers and simply put garbage. I haven't coded something so ugly in the past year or so. I just iterated through all possible values of x and checked them with erdos gallai theorem (which btw, was kind of given in the statement, and I find that even more stupid than the problem itself). I also thought of maybe binary searching and having all values of a given parity in a range, but since people kept getting WA, I assumed that this was a wrong approach (+ I didn't have a proof)
I used the same approach. First I find minimum degree of graph with Erdos-Gallai theorem and then do a binary search to find the maximum degree.
I did the same thing. Agree it's one of the trickiest things I coded in a while :(
There is already a pseudocode available here which works in linear time.
For my solution I needed a modified version of the algorithm (to compute bounds for the missing degree), so just plain code wouldn't help too much.
How to solve E
Hint
it cost me totally three papers to solve problem D
BTW,a nice contest :)
large lao take me up，take me up！！！
Who thought it was a good idea to propose a stackexchange answer as a problem?
Reference
The problem statement provided a reference to those algorithms.
Before clicking your link I was expecting to see this :)
I've still managed to spend more than an hour to get it to work, though :(
why u didnt solve a and b , petr
It's a combination of two things: I was hoping to get H right until the end of the contest, which would give more points; I was quite tired at the end of the contest, so I was basically staring at the statements and not understanding them (at least not immediately, and then I switched back to H).
I also assumed G would be googlable, but I couldn't find this thread. I also solved D by googling the algo for next permutation and probably would've taken one extra hour to solve the problem otherwise (and with a complete proof, since it's not straight forward that you can only cut a sequence in the unaltered prefix)
Problem D seemed quite solvable to me: I just wrote some random permutation such that the next one differs much from it, and looked at how much the sum differed from the expected sum at each point:
In another view:
From such example, we can see that, for the whole suffix that changed, the differences are nonzero in the general case: the first one is positive, and all the following ones are negative.
Next, there is a straightforward calculation of how many permutations differ from the previous one in the last k positions. And then summing that up.
Nice find!
I wonder though. The answer at StackExchange does not use the fact that all primes are of the form 4k + 3. It seems correct in the general case.
So, how does the 4k + 3 help? When trying to solve problem G, I've found that law of quadratic reciprocity has a special case for numbers of the form 4k + 3, but couldn't make anything of it.
It is explained in the editorial: finding square roots modulo primes of form 4k+3 is faster, so the interactor is faster this way.
Thanks, didn't see the editorial is already published.
So I was trying to find a solution using a special property, but the property was ultimately for the jury side of things. Aaargh.
That's not just a stack exchange problem. It's even worse: a relatively well known theorem (erdos gallai) which as a matter of fact was directly linked by the wikipedia article from the statement. I also find the problem veeeery bad, and apart from the trivial idea once you know the theorem, I found the code quite disgusting.
That's not the correct causality. We found out after the problem was set, but still saw some substance to the problem (you first need to understand which question to ask and why).
UPD: I thought it was about problem G. Disregard.
That's trivial for anyone who has a chance to understand the theorem in the first place, the hardest part is writing correct code.
super tricky problems hehe, tnx
For B, I just output:
{tx, ty} = {(sum of all(a[i]) + sum of all(x[i]))/n , (sum of all(b[i]) + sum of all(y[i]))/n}I feel confused after seeing big codes of others :|
I just sorted {a[i], b[i]} and {x[i], y[i]} and output a[0] + x[n-1], b[0] + y[n-1]
As soon as i saw, all of the x[i] + a[j] are equal, the first thing that came into my mind was, sum of all of it will be n*tx.
Actually, the best contest of 2018...
Today's problems were fun! Thanks to majk and coordinators!
Problems were very well explained. No ambiguity. It gave you time to think instead of wasting it trying to understand the problems.
Nice problems. Bad difficulty. 2.5k+ solved D and 300- solved E. It's really big step. What results are you expected for that problems?
We knew the jump was big. We expected a bit more solutions on F, but E is roughly what we anticipated after the tester spent time on them. I originally thought that F is a nice and simple Div1A-B problem.
What was the solution for F? My idea is: first check how much water/grass needs to be added to avoid getting stamina < 0 on lava (water preferred to grass, added as early as possible); start with all flying, then "convert" it to walking/swimming with cost 2/1 for all lava in order; swimming is preferred and gets converted from largest position to smallest, walking gets converted from smallest position to largest. Finally, ensure the stamina doesn't drop below 0 on grass/water by converting flying in the same way (this part is trivial).
Yes, this greedy was my solution as well.
...WA on pretest 11
I actually didn't find the conversion to flying to be that trivial. Maybe you have some issue there?
I convert from flying. If there's a half-meter of water where the duck is currently flying and I'm processing a half-meter of lava, I make the duck swim the last possible half-meter of water (where it's currently flying) that's before that half-meter of lava. Otherwise, I make it walk on the first possible half-meter of grass where it's currently flying.
Are you saying you have two passes of conversion? Not sure, but it doesn't sound right.
Maybe for the second pass, you need some flying converted to swimming earlier. And previously, you converted water from largest position to smallest. It may have been profitable to move the converted part closer to the front, so that the second pass is cheaper.
In my solution, I had to handle both passes you describe simultaneously. To look ahead, I first calculated two quantities from back to front: how much surplus energy we will need moving ahead, and how much grass will be available ahead for conversion (I convert to flying, not from flying). Still not sure whether I got everything right though.
How would I convert flying to swimming earlier? I convert to swimming asap whenever possible. If by earlier you mean position-wise, that could just lead to a worse situation where I just removed some flying I could convert to swimming to add stamina for flying over early grass in the 2nd pass.
My rule of thumb: Quickly check the hard side of problem, and Ctrl+F for the word "factor", "prime number" or any number theory stuff. If there's any, skip the round.
Trust me. It works very well.
Got a better idea: check if the setter's handle contains "majk"
I like numbers!
are u one of the problem setters for Hello 2019??? I am probably not in the mood of another round of mathforces XDDD
Just my personal (i.e. biased) opinion:
This Good-Bye contest was by far the least enjoyable one for me. Problems D and E (which for many constituted the main 2 problems in this contest) were not of very high quality:
Problem D has a nice solution — which is, unfortunately, much easier to come up with than to prove. Also, for many, OEIS helped, and very few spent time proving their solution is correct (I, for instance, saw the ridiculous number of fast ACs and just coded it and prayed it works on the N = 10 test).
Problem E allows for many solutions, but I think the problem is not very "fresh" — meaning that there are quite a few standard results about degree sequences.
My opinions are also heavily biased, but honestly it's funny to see my "strategy" giving me so much win XD
Googling up "degree sequence" is first thing I'll do if I solve E, so it's interesting how majk overcomes the issue: Just link the wikipedia and make people see them. It's better than nothing, I believe..
Completely agree with you. I hate problems that are 90% math and 10% coding (C and D).
What if instead of whining about the contest, you practice math problems so you can start AC-ing them? :)
Great contest to end 2018! Specially because you have multiple solutions for the problems :), which you get to know when you visit your room and see people doing tons of things to solve B!!
[RANT]
I feel really hurt by problem G.
One of my solutions, 47754232, should clearly be WA#1 (notice that very early in the source code I output N nonsense lines of numbers!). However, it failed only on 4th pretest, costing me 50 points (actually a couple of times, as understandably, I couldn't expect the bug to stay there!)
One of my other solutions, 47754966, passed pretests in just under 3s. This was quite weird for me as my solution was essentially:
(This is very important for what happens next.)
...but okay, it happens.
Then, 20-25 mins later, I get an announcement that we can't actually use more than 100 queries! This of course incurred a large penalty on me (a few more WAs, 40min worse time etc.) as I needed to do a bunch of patches in order to make it into the limit. (Hopefully, it will pass the systests.)
[/RANT]
I feel you should do something about each of the above.
I have checked the submission you mentioned manually and changed it so that it doesn't ask too many queries. You seem to have some bug in your approach, since on test 5 it sometimes detects as few as 6 factors, depending on the randomness. The correct approach should have error probability of order 10 - 14 with 50 queries.
I am deeply sorry about the issues you had during the contest with this problem, but in this case we will not change the verdict.
I am happy to discuss more if you wish, either here or PM.
I vented in the comment before and I don't think I have anything else to add. It's good to know that I had something wrong in my code, too. I still totally hate the way the things worked out (I hardly remember getting that infuriated by a single task), but there's no frickin' thing to do now.
I wonder if I would've passed the original version of the problem. Or maybe not, I'd be fuming if it turned out I would.
:<
I dont see how tourist can come up with the solutions to hard problems so fast. I think he is a great googler.
haha, great google is in his mind
I think it's pretty hard to be tourist just being a great googler ;)
HEAVY DOWNVOTES on the way xD
Boy, I am so slow, not only am I slower to code than everybody, but even my programs are judged slower than everybody...
Man, your comment reminded me so much to Pet Cheetah lyrics, Lol.
(8) No, I move slow. I want to stop time. I'll sit here 'til I find the problem. (8)
If you want to hear it XD
how do i view the contents of a hack?
You need to wait for systest, then it should be avaible on the hacks tab and you can click on "View test", here is the link for some other past contest where you can do that.
After system testing, go to your submission page, you will find a link called
View testin the verdict column, belowHack #some_numberI made 5 unsuccessful hacks trying to hack two O(n3) solutions of problem B. This is the second problem in recent contests were the limit is set to 1000 and O(n3) solutions pass!
Also depends on what is inside the loop. Implementation with very light calculations generally passes for the order of 109
1e9 operations can be done in about less than half a second
It depends on the constant
Problem D. I don't sure it's correctness. a[n]=n*(a[n-1]-1) starting with a[1]=3. ans = n!*(n-2) + a[n-2]
Are you sure that "Idleness limit exceeded on test 4" is not a bug in interactor?
I'm looking in it. It seems sometimes interactor is too slow and it gives ILE verdict because of huge waiting in a solution. I'll handle all such cases and rejudge solutions if needed. Sorry for it.
Possible way of thinking in D:
Suppose the concatenated sequence of permutations is p(1) || p(2) || … || p(n!) where “||” is the concatenation operator. The sub-array you will choose will always be in the form of: suffix of length L from p(i) || prefix of length n-L from p(i+1).
Let’s loop on j from 1 to n to see how many suffixes starting at index j (in any of the permutations) we can choose out of all n! suffixes out there. First note how p(i+1) will differ from p(i), the rightmost number in p(i) which is less than to the number on its right (call this number v1 and its index in p(i) ind) will be swapped with the smallest number in sub-array [ind+1:n] (call this number v2) such that v2 > v1, then subarray [ind+1:n] is sorted in ascending order, sub-array [1:ind-1] won't change, resulting in p(i+1).
We have 3 cases here:
1) ind >= j, then all the changes will happen within the sub-array [j:n] to get p(i+1), so prefix of length j-1 is same in p(i) and p(i+1), so you are sure this suffix || prefix should be added to answer.
2) ind<j-1, then the prefix of length j-1 will be different in p(i+1), here is one important thing to notice:
In p(i), sub-array [ind+1:n] is sorted in descending order and p(i)[ind] < p(i)[ind+1]. This implies that p(i+1)[ind] will be v2 and sub-array [ind+1:j-1] in p(i+1) will have sum at most = v1 + v2 + (sum of sub-array [ind+2:j-1] in p(i) or 0 if ind+2>j-1). So the prefix of length j-1 has sum in p(i+1) < than that of p(i) and this suffix || prefix shouldn’t be added to the answer.
3) If ind==j-1, then prefix in p(i+1) will have greater sum (as v1 is swapped with v2), and this suffix || prefix also shouldn't be added to answer.
To conclude, our answer for every suffix of length L (for L from 1 to N) is the number of suffixes of length L which are not sorted in descending order = n! – nCL * (n-L)!. Add 1 at the end to account for p(n!).
I was frustrated seeing so many people solve D quite fast. But What!? OEIS!? Thanks a lot to let me know such a great thing!
Actually, I tried to search it in OEIS but couldn't find the solution.
After thinking for a while, realized it was just counting how many preffix — suffix combinations would exists and came up with it. :P
It's on OEIS as the difference dif(i) = i! * i — ans(i)
I made a submission for problem G which passed pretests with 100 sqrt requests, and then printed the answer. After the limit was put in place, it still showed as passed presets, but it failed systests on test 1. Is there anything we can do about this? The problem statement says 100 requests, and printing the answer doesn't seem to be a request.
The submission is here: 47750364
Hi, I'll handle it in the best way. Right now I'm fixing erroneous ILE verdicts for this problem.
Thanks Mike!
I'm investigating your issue. I'll keep you posted.
UPD: This is a mistake on our side. After rejudging you get AC.
Maybe I should actually read the wikipedia link that was given in the problem statement E instead of wondering where everyone got the solution from.
in problram F:
3
1 1 1
GWL
shouldn't it be 5+3+1=9?
no, it's 2.5+0.5+3+1=7
I didn't even realized can fly half meter until someone told me.
Watch problem again, The duck looks at me like look at a retarded : |
After long struggle with Python3 and bugs, my 2018 sadly ends with
My solution rquires division over big integers. However I have no template for it, so I tried to implement it using C++ first, after some time I changed my mind. Because of unfamiliar with Python, I spent long time coding, thinking about many things about language rather than the problem(like is there any functions like std::unique()?). Oh it's really a terrible night for me.
Well I didn't mean stop writing problem, I think the problem is a good problem but it's harder for people only using C/C++, compared with those are familiar with Java or Python.
Maybe throw them into a set using
list(set(x)), not sure if this will work for your application?Seems work, thanks!
Why do I see legendary grand masters with ratings less then 1400? Is this a glitch? Someone please explain.
It's a feature on Codeforces during the holidays. You can change your color and even name.
Thanks.
A duck comes to another duck to 'duck' lmao
For what purpose does a duck duck with another duck I wonder? ;_;
And I wonder that this duck travelled 1017( = 1012 * 105) meters over lava and what not just for a few seconds of ducking :D
Maybe ducking with the chosen duck actually worths the efforts...
47761370
Oh come on! TLE 50, for real?? That's
, man, it's not supposed to have TLE on 
!
Basically, the problem has an O(N) solution. The editorial mentions O(NlogN) and O(Nlog2N) solutions (which should both pass). But, somehow, N is set to 5 × 105. What's the reasoning behind setting N so large?
Tragic tears were shed when I couldn't get my nlogn to pass pretest #18
it was a lazy seg-tree so the constant factor was larger but still...
Similar to what happened to me. Mine is
though. :'(
47751545
I resolved my case by changing multiset to vector... 47769849
it appears that gathering all elements of multiset by iterators has extremely high constant o:
When will the ratings be updated?
The moment I saw the solved count of D for the first time, I felt like something wasn't right, and went for OEIS, yet found nothing (I tracked the wrong pattern I supposed). Then 20 minutes later I solved D by a math-inspired dp solution, with a few proofs backing my claim.
Then two hours later people told me that D can be OEIS-ed...
I don't know what to say regarding my case... :)
How do you find it on OEIS?
I didn't make it to find anything on OEIS. Other people did.
If you're asking generally of how to search on OEIS, just input a part of a sequence.
I input the sequence and oeis said not found...
If it's the sequence of answer with input from 1 to 10, trust me, I tried it and found none as well :(
You can look up for other people's comments. They mentioned some other derivative sequences ._.
Actually, the sequence in OEIS has the formula f(n) = n*n! — (solution), so that's why it's hard to find it there. I couldn't find it either :(
Basically, I thought about the problem, and it occurred to me that really, what we want to count is the number of ranges that don't work. Ie: N!*N-cnt.
And that's indeed what's on OEIS.
Is it rated majk?
Most certainly yes. We're just checking some submissions on G.
Out of curiosity, how were the large primes of the form 4k+3 created for test data in G?
I think they pick some known big primes public somewhere. Probability checking is not allowed.
Random + Miller-Rabin.
It's so...disappointment... I used unsigned long long and get
Time Limiton pretest 4 for n = 1:I shoud just use usual long long, but... loosing 39 points of rating because of such stupid little mistake...
ok
ok
uh oh
eh
what
what
You got mathforced
The story of your life.
3 10 10 50 WGL
In problem F how is the ans 220 for this ? I think it should be 240? Am i missing something? pls help
To fly pass 50 meters of lava, you'll need 50 units of stamina, taking 50 seconds.
Going past 20 leftmost meters normally will build up 20 units of stamina, taking 80 seconds.
To build up additional 1 unit of stamina, the most optimal way will be swimming in-place within water segment. It's like, from a point in the water segment, you swim to the right 0.5 meters, then swim back to your starting point (or you can choose to start swimming to the left then going back right, the result is still the same). Each unit of stamina stacked costs you 3 additional seconds.
You'll need 30 more units of stamina before flying pass the lava, so you'll need 3·30 = 90 seconds for the process of building up stamina.
Overall, the answer will be: 50 + 80 + 3·30 = 220.
thank you
Math problem: * exists *
Codeforces users:
Petition to ban weebs
rename codefoces in mathforces
Tourist beat 2nd place by more than 2000 points. Anyone else thinks this is scary?
Мне пришло сообщение о том, что случилась утечка моего кода по задаче D. Оказывается, такое может случиться, если пользоваться ideone.com. Я не знал о том, что использование ideone.com не является безопасным. Заявляю, что никоим образом не хотел причинить вред ресурсу codeforces. Прошу не блокировать мой аккаунт и не применять ко мне штрафных санкций.
I was wondering why rating update is taking so long. Then I noticed that my rating change is 0
lol
It was really a GoodBye 2018 Contest
Good Job Problems Setters and thanks for Giving me a good feeling as a Competitive Programmer
The contest is amazing.
Goodbye 2018! This year I learned much knowledge and made many friends with the ones who also love algorithm and love codes.I think codeforces is a wonderful platform that give we all another home! Hope we all better and better:) Happy New Year!
In Python for C question,
return t + (t*(t-1)*d)/2gives correct answer but,return (t/2)*(2 + (t-1)*d)where t is the number of terms in AP and d is the difference.. gives wrong answer on testcase 18. Can anyone explain this please?If t is odd then t/2 will round off to nearby value in second equation but it will not in first equation as either t or t-1 would be even.
I see many of the comments referring that D can be easily solved with OEIS. Can someone explain what is it and how to use it?
https://oeis.org/
A sequence encyclopedia. In problem D you're given a N, if you assume the answer is a known sequence then you can brute force the first 10 elements of the sequence, and then search it on OEIS. If it's a known result then the website is going to provide you with a formula to calculate the i-th term of the sequence, i.e. the answer to the problem.
In this case the problem itself wasn't on OEIS, but the diference between every interval (n! * n) and the answer for the problem, call it ans(n). If you brute force the solutions for the first 10 n or so, i.e. ans(1), ans(2), ... ans(10), you can look up the sequence of the difference dif(n) = n! * n — ans(n) on OEIS and get the formula that solves the problem.
If the website gives you some formula f(n) to calculate dif(n), then then answer to the problem will be ans(n) = n! * n — f(n), derived from the previous equation.
This is the difference sequence i found on OEIS: https://oeis.org/A038156
This is the one i used, which is the opposite of the previous one: https://oeis.org/A166554
The second link provides you with the formula "a(0)=1, a(n) = n*(a(n-1)-1) for n>0", so the answer you would be looking for is n! * n + a(n), since i said it's the opposite to the actual sequence, i.e. a(n) = -f(n)
Don't forget to include % MOD when calculating everything on the implementation.
Well, it's better not to use it ;) Give some time on it's mathematics to see how overlaps between two permutations contain all the numbers (thus, the same sum), and you will yourself derive what's needed! Sample cases for the rescue, verify your formula for 3 and 4!
"How to do X?"
Stack Overflow in a nutshell
Can anyone help me understanding the approach of C? I am a beginner.
only divisor(k) of N can be used and then it's a Arithmetic progression for 1 to n-k-1 by difference k
Huh, some specialist took the third place.
Good luck & high rating!
I am so happy to be a specialist after goodbye 2018.
Case 7 of F is: 1 9 W
Jury's answer is 18. Can someone tell me how this is possible? The best option I can find is 19.
[Solved] swim 4.5 meters and fly 4.2, 4.5*3 + 4.5 = 18
[Deleted]