This round is in memory of Leopoldo Taravilse.
Leopoldo Taravilse (ltaravilse) was a distinguished member of the competitive programming community in Argentina and Latin America. As a contestant, he reached the ACM-ICPC World Finals in 2010 and 2012, and was active in CodeForces and TopCoder. After 2012 he became a problemsetter for the ACM-ICPC South American regionals and the Argentinian Programming Tournament, and later coach for a World Finalist team in 2016.
Leopoldo's passion was helping others realize their full potential in competitive programming. He taught at various competitive programming schools in Brazil, Cuba, Peru and Bolivia, and his role organizing the Argentinian Training Camp cannot be overstated. Under his wing, it grew from a small group of friends in 2010 to a major event featuring international sponsors and having hundreds of participants coming from all corners of Latin America. Through successive editions of the Training Camp, Leopoldo inspired students to learn and improve, to give back to the community, and to have fun doing it.
With his intelligence, warm heart, relentless work ethics and witty sense of humour Leopoldo touched countless lives. We will miss him as a friend, a mentor, a teammate, a drinking buddy, a role model, an overall great person.
Rest in peace my dear Leo.
You can see this blog: A round in the name of ltaravilse.
And you can donate for prizes of this round: In Memory of Leopoldo Taravilse.
Hello everyone!
I'm pleased to announce: Codeforces Round #502!
This round will take place on Aug/08/2018 17:05 (Moscow time). It is rated for all participants and everyone will have 8 problems and 2 hours 15 minutes to solve them.
The contest is created by Magolor. This is the first competition I proposed. I hope that you will enjoy it. The heroes are from a TV show that I like and do not have any relation to Leopoldo.
6 of the 8 problems are created by myself. Thanks to:
- ODT for inspiring me and discussing the problems with me.
- Anton arsijo Tsypko for examining my problems, helping me a lot on this contest and designing problems B and G.
- Max MaxZubec Zub, Danya danya.smelskiy Smelskiy, Sofia Sonechko Melnyk, Stanislav stanislav.bezkorovainyi Bezkorovainiy, Vitaliy kuviman Kudasov, Aleksandr Kostroma Ostanin, for testing the round and improving the problems and solutions.
- Mike MikeMirzayanov Mirzayanov for Codeforces, Polygon and the help he offered to me.
- Nikolay KAN Kalinin for helping with the contest and designing problem G.
- Ahmed ahmed_aly Aly for his initiative to host this round in memory of Leopoldo.
...Yet Another Chinese Round...?
Scoring distribution: 500-1000-1500-1500-2000-2500-3000-3250.
Prizes distribution: $153 for top 30, delivered using bitcoin or amazon gift card (each contestant chooses).
UPD1: Chinese Editorial is published. You can view it through This link. English Editorial well be published soon.
UPD2: Congratulation to winners!
10.step_by_step
UPD3: English Editorial is published.
Prize distribution, wow
It is really sad that such great people pass away...
I have a suggestion. In several countries, there's a tradition called "moment of silence". Generally, it is a minute of silence during some important events as a gesture of respect. Can we all agree, as the community, that we won't submit anything during some particular minute during the contest?
'moment of silence' cannot be done by no submission for some time during the contest.
With all my respect, I doubt this will be appropriate.
If it's really meant for contemplation, reflection, etc, I would rather skip contest at all because you have to be in rather different emotional conditions during competition and during moment of silence. Switching between them forth and back in such a small time span seems both unrealistic and disrespectful.
Just a suggestion, if it can be done like in football matches. A minute of silence before the contest begins? Maybe the problem statements are displayed a minute late and the round is of duration 2:14.
I still think that would be appropriate, but looking at all comments below, I have changed my mind that would be a good idea. Nevermind.
Your idea came true. There was no one to submit in 25 minutes, only 502.
rated&bitcoin i don't think that could happen, naturally server will be down for more than 1 minute don't worry.., btw i got your point!
wow, are you a time traveller?
Did you use Velorian car? :O
Now everybody knows this was a bad idea. :(
i think the hardware of codeforces servers agreed with your opinion and made a few minutes of silence by their selves, even though it was not the thing that everyone wanted...
R.I.P leo...
Finally, Div.1+Div.2 combined round!
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
null
Upvote if you are waiting new problems from Taravilse
You’re undebatably one of the most disgusting and miserable people I’ve seen here on CF.
you're a fucking piece of shit you know, have some respect for people who were friends with him. If I were in front of you I would hit you in your fucking face scumbag
Blue guys are not allowed to hit my face
Seriously,I didn't expected that comment from u!!
Are you jealous?
Do you think this will help,vote-cheater?We admire Taravilse not because of your votes.
Even though this comment was obviously not written in good faith, does anybody know if ltaravilse had written any unpublished problems? They could be added to another round.
Upvote if you are waiting new problems from rotavirus
WOW!
The contest is made by a middle-school student
Chinese ??
You f***ing racist f*ck. I bet you're white. Stupid white trash
Sincerely, i wasn't racist at all. I was showing my respect to Chinese students because they are clever and prodigious.
So,please never judge a comment directly without dissecting its real meaning
It's surprising but normal :D In China, even primary school students can set up a contest add you can find them on some OJs. Show my respect to those 'dalao' OIers. orz
It is actually a junior-high school (still very impressive). See Wikipedia.
ooh. good. finally a combined round. so awesome people like me can really show my skills. I really should not be on Div 2. These losers man.....
Rest in Peace Leopoldo ltaravilse Taravilse!!
I'm glad to find the Chinese contest again. However,I'm sadder after noting the first part of this article and hearing that such a great person left.
Hope the contest can be hold successfully.
And hope Leopoldo rests in peace.
I can't speak English very well,please forgive me.
(So I hope that the description of the problems can be concise.)
I agree with you so much.
Sometimes I feel like this life has just been cruel, to make people, whom others love, pass away at such early ages...
Too bad, never had a chance to know him or work with him before. Still, rest in peace, friend...
2 hours and 15 minutes for 8 problems? That's quite challenging! :D
Does "Chinese round" mean wrote by Chinese or wrote in Chinese? If it is the latter, it will save a lot of time to understand the problems for the Chinese. By the way, I'm also looking forward to the Chinese editorial .
Maybe "Chinese round" means Chinese do not have to do the contest at midnight.:D
But 22:05+2h15min=00:20... Maybe earlier than those start at 22:35 or even later. But I think if it means this, Codeforces Round 500 (Div. 2) [based on EJOI] and Codeforces Round #503 are the "Chinese rounds" instead of this one.
But I think we have to do this contest at midnight.We'll take parts in this contest from 22:05 to 0:20,isn't it?
I am a Chinese and now I'm travelling in USA now.It could be a good time for me to take part,but I didn't bring my computer:(
I think it's the former. Well, never saw the latter works before, but if the setters were generous enough, they might provide a link to the Chinese statements when the contest begun, maybe?
A good suggestion!
Actually not. In fact 'Chinese round' means that the time fits Chinese people. Being a foreigner, hope that CF will prepare translation of the problems, of course it will save competitors lots of time understanding the problems.
Actually not. In fact 'Chinese round' means that nobody will solve E div 1, one or two persons will solve D div 1, and about 10 people will solve C div 1.
@jiry_2 & Codeforces Round #FF (Div. 1)
This makes me think of ZJOI.
ZJOI 2018 Day 1 is a nightmare. (We can only orz jiry_2)
qwq
Wow！orz！
Wow Orz!
Your meaning is the problems wrote by Chinese are too hard for most competitors ?
Hey! I'm curious about how you find that? This blog was just created two weeks ago!
It's just in your luogu personal page QAQ.
I remembered that you wrote something about 502 error in your blog before the contest. A fantastic flag.
I am sorry to hear that a great man passed away.
In this round, it is more important to remember such a great man than to compete with others.
IOI is comming, we lost a great man!
R.I.P. ltaravilse
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
if (Div1 && Div2 && prize) {
combine (Div1 + Div2);
}
Mathforces?
Why did CF merges Div1 and Div2 ？？
For prize distribution, perhaps.
Oh? Maybe
Really sorry for the loss :( May his soul rest in peace.... A great thing to honor him.....to which he dedicated his life most!!
I will be part of this round just for you Leo(Been inactive for two yrs ), for all the things you teach us at the very beginning.
Leopoldo was our coach. I met him first in 2005. We were Latinoamerican Champions in the ACM-ICPC World Finals in 2016. We had spoken 6 hours before he had the accident. So sad :(.
Thanks for making this round
Rest in peace brother.
Good that this Leopoldo Taravilse died. He is a piece of shit!
Why do you have to be toxic in every posts?
Coz i like to spread negative vibes :)
It's sad that there is someone so pathetic, having to look for attention in the most disgusting of ways.
If he is then what kind of useless stuff are you?Everyone has no permission to look down at such a great man.
How can you say something like this for someone who has passed away? You are such a pathetic and disgusting person!
Is It Semirated?
Div1 + Div2 combined? My rating would be as dead as leopoldo now.
You are a disgrace to the Codeforces community.
What's bad about common round?
No offence,just crack a joke about the difficulty of Chinese Round(hell) .
Not all Chinese rounds are duliu >^<
However,your last round is very duliu
yep! ( >﹏<。)
Please trust me, Chinese rounds will make you "happy". I think that you understand my meaning.
yeah...it makes me "happy".In another sense，maybe just lucky of survival.
Sorry, my meaning is that Chinese rounds will be very hard sometimes. Really, I agree it with you that survival is very lucky.
Rest in peace great Leo.
Wish Leo a peaceful rest and Magolor a great debut.
(Too sad GoFundMe doesn't accept PayPal for personal campaigns)
А что с ним случилось (может быть это где-то написано в посте, но у меня с английским беда)? UPD: То, что он умер — это понятно. Из-за чего это произошло?
RIP ltaravilse
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
such people.... they have always inspired us by there great patience and fresh minds , a round is a great respect for soul that loved and lived its career sincerely , thnx guys for that great work and hope the best for every real worker like ltaravilse
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
C and D have the same scores? Does it mean the difficulty will be similar?
Yes.
Thanks.
it will be great that contest starts 10 mins later so i could participare in it from the start
Please, no delay
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
Round 502 and Error 502
Coincidence? I think not.
Contest should be unrated imo. It's a pity since the problem-set is nice :(
Hi. So to me seems like a notorious coincidence.
Is it just me or Codeforces is heavily lagging ?
looooooool what just happend !!!
Ребята, привет! Давайте не будем омрачать данный раунд, а получим от него удовольствие, ведь этот раунд в честь Леонарда...
It's been a long time since the unrated round. That day has come!
Looks like both Leopoldo Taravilse and Codeforces servers passed away, RIP :(
It’s a pity to be unrated.
Unrated! Goodbye.
Please, sorry to the issue. One of our subsystems failed completely unexpectedly. It was internal assertion failed in https://github.com/greg7mdp/sparsepp (Assertion num_deleted failed). We are investigating the issue. It was the first time ever this subsystems failed with such message.
The round is unrated and the prizes are postponed to be awarded in some of the next rounds.
Sorry again. I apologize to problem writer Magolor, the coordinators and everyone who helped prepare the round. You did a great and good job.
Unfortunate that this happened. As always, thanks for your hard work on the platform.
You should not make such announcements in the middle of the round (no matter how obvious it is that it will be unrated) because it just instantly kills everyone's motivation to continue with the contest.
I think he did the right thing, it would have caused a lot of confusion had he not announced it. Those people who 'lost the motivation' would have felt worse after realising their time was wasted.
However, tried your best but get nothing is also bad.
Nah. Participating in a contest has never been "get nothing", especially with such high-quality ones like today's.
It's not just rating bruh.
deleted
Yeah, rated contest just bring out some kind of weird adrenaline and motivation. to solve problems.
But what would Benq fill, if he found out that
it is unratedafter the contest? He took 1st rank, and he needs only 26 rating points to become a LGM!P.S. Benq, I believe you will do it next time :)
A sudden notice of unrated makes me full-body relaxed.XD
Magolor you struggled a lot to make this round happen and it's unrated now,i am really sad for this
So bad ToT
Successful Hacking Attempt +100
Anyway,these problems are really high-quality. Many thanks for these amazing problems.
The website became "502" during Codeforces Round 502 :P
The problems in this round is fantastic anyway :D
How to solve the D problem? I could think nothing but tries.
The contest is not over yet.
Such a nice contest in memory of the great person with interesting problems and prize distribution, ...and unrated =(
Sad :(
I liked problem D, but no comment for B and C
I think unrated is fair to all participants . but is not to the author and coordinators .
They spent lot of time on this contest but their work does not paid off.
I can understand that there does not exist a solution which is fair to everyone . And I know the sudden fail is not anybody's fault .
Hope there won't be next time . And I think the author needs to be compensated , if could .
9141 participants we don't see this every day
How to solve C :
Participate in atcoder regular contest 91 (pretty recent contest).
Participate in round #502.
Copy-paste the solution from ARC91_E.
Add 2-3 lines and submit the code before the server goes down.
PROFIT !!! (actually not, it’s unrated xp)
I have actually written a brute force code using small n values and deduced the relation from there
How to solve D ??
Hint: There are at most 4096 different strings, and k is between 0 and 100.
make a mask for every string in the original multi-set and keep track of occurrence of every such mask, then brute force for every possible pair of masks where 0 <= mask <= 2^n what is the resulting cost for this pair, from this loop you can keep track for every mask m what is total number of strings s in the original multi-set such that cost of m with the mask representing s is at least k where 0 <= k <= 100 using cumulative sum. then every query can be answered in O(1).
You'll need to preprocess queries to answer them in O(1).
First, let's mantain a set S for each different string (stored as an integer bitmask) and a frequency array, we don't need to use a STL set, because a vector (or array) and the frequency array will help us to avoid double counting.
Then, we will have a matrix ans[M][K] that will contain the number of strings in the set that has Wu value with string M (bitmask) at most K, so we will use preffix sums to process them after. What we'll do now is brute force the mask M and use our "set" to compute the Wu values and do something like this (pos is the number of different strings stored in array v):
With that you can answer queries in O(1) with a preprocess of O(n2nmin(2n, m) + K2n)). Where K is the max value of k.
Note: Try to use I/O that can make it on time, maybe scanf or getchar since the lengths are fixed. :D
2 minute silence for Top 30 people !! :)
D in custom invocation, no input, n=12,m=q=500000,all strings="111111111111", all queries="111111111111 100", all answers=500000: about 700 ms.
D with scanf: about 1700 ms.
D with cin+ios_base::sync_with_stdio(0): TLE.
Can you tell me why this is happening? I always use fast IO using cin and cout and thought that the difference could not be that big (to give TLE I mean).
I think the problem is the difference between speed of reading STL strings and C strings (aka char*).
Nope. 41361499 reads chars and still gets TLE.
Sorry, I should saw your code before writing something. Now, we talk about different things. I compared reading STL strings and reading C strings and you use char one by one reading (it's not the same as two methods, mentioned above).
Can you link some documents about this?
I always think read char must be faster than cin and cout. Yet I managed to get AC using cin + ios_base::sync_with_stdio(0) but gpt TLE using read char.
Thanks.
close... http://mirror.codeforces.com/contest/1017/submission/41359754
Don't you know that Chinese Round are always DuLiu
Sad to know that the round is unrated. But, anyway, I really enjoyed these high-quality problems.
How to solve F?
Seem turn out to do how bruteforce :)
I have just written an Eratosphenes sieve with sqrt memory. I think it should pass
How did you do the sieve with sqrt memory?
It has been described here
The time complexity of this method is still
, right? I don't think that this complexity could fit the time limit.
Don't think so, it fits very well =)
My reaction after knowing this complexity can actually pass F
Codeforces server is faster than light...
What will be your reaction when you find out about this project: https://primesieve.org/ ?)
Spoiler: their
sieve works 0.44s for numbers up to 1010
Isn't it a common sense that the performance of Codeforces servers is very good?
A clue is modulo 232 so it is smth bruteforce.
I don't think that has any influence. I think that sieve here is a bottleneck, not computations directly influencing result.
I've never seen this module and I used long long with this extrange modulo.
Luckyly it was AC anyway
If intended solution is to enumerate all primes then do bruteforce, then the problem is trash!
It works 2 seconds in a max test, so I think yes:) It astonished me enough too when i had realised it
Exactly. This is one of the “outstandingly dumb” problems for me in the past 6mo ~ 1yr. It doesn’t even deserve its place in a joke contest. Something is broken in codeforce’s QA process.
(FYI : the author doesn’t even do sieve with sqrt memory, you can check out that in editorial)
It seems you can just use eratosphenes with n/3 memory with bitset.
It worked out with almost stupid eratosphenes and vector bool 41370869. So even no need in sqrt memory optimization.
With bitset even faster 41371002
The problems are nice, but those statements are just horribly confusing. Take an example (problem E):
Repeated how many times? The most natural way to read this without considering the impact on problem difficulty is: repeated once.
Incidentally, the Russian translation says "repeated once" more clearly ("ещё раз", "once more").
Of course I agree that the statements as a whole, and this particular part, could have been better.
Don't know about others, but with all the tricks, problem D is just straight brutal in terms of thinking imo.
Not something too hard to implement after you got everything, but to reach that state is another story...
What was you solution to D? I thought it was straight-forward k*n * 2^n precomp and O(1) answers to queries.
Of course, I did not implement in contest because i left after the server crash ( ͡° ͜ʖ ͡°)
Well, my idea is pretty much the same — pre-processing offline then O(1) to queries.
But that processing part was straight deadly. Even O(22n * n) didn't fit in TL for me.
At the near end I realized 0 ≤ k ≤ 100 (yeah, screw me), and changed the processing method to such with complexity of O(2n * 100).
What was your 2^2n * n idea, I only thought of the one that relies on small K.
Literally, I tried through all pair of distinct strings (masked to integers for simplicity), and calculated that for each pair, what would the Wu value for that pair is.
After calculating everything, I sorted the values, then start handling prefix sums.
The queries would be O(log(2n)) due to binary search though, but that part is insignificant compared to the pre-processing.
My (failed) solution: 41366581. Still I advise against seeing it, my source code today has been a huge mess :<
Thanks for sharing. And now I can see why you thought it was so difficult xD
It didn't fit in TL for me too.
Does the problem require some kind of Fast IO?
I'm not even sure.
Even my "Pretest passed" solution (which was O(2n * 100) in pre-processing and O(1) for each query) took about 1.4s for the worst case
(
sync_with_stdioswitched off by default for better IO).I use scanf and it didn't pass in O(2^(2n) * n) :< Didn't realize k <= 100 though :<
Probably not. You can usually get away with some other constant optimizations.
Can you share submission?
2^(2n) and pretests passed in 1s for me
I am too dumb lol. I was fixated on somehow manipulating the trie. But it was just precomp.
and I just realized i loop thru the wu array backwards lol.
Wu array? How did you solve D?
I can't check your submission for some reason QAQ
https://pastebin.com/LtC9Nru7
here lol
i fixed the bug here by making string to binary differently
Thank you for the contest! Keep it up!
In my opinion, the problems were nice. And I quite like the format where there are even more problems than the usual five. Plenty to choose from.
However, there's room for improvement: the legends were not exactly a fit, and the Russian translation was not perfect either.
This is probably a very dumb question but how do you solve C?
You should use sqrt-blocks.
Here is sample for 17.
[17] [13 14 15 16] [9 10 11 12] [5 6 7 8] [1 2 3 4]
Well... I implemented that during the contest but it turns out there are a couple of bugs in my implementation (starting from the fact that I printed no spaces between numbers in the "left-over" block). Your 17 example just so happens to point out both of my bugs :P
What I did was try and divide the array into "blocks". If a block is of length k we will print out n-k+1, n-k+2, ... , n, n-2*k+1, n-2k+2, ... n-k. We see that the sum in this case is k + ceil(n/k). The k is from the LIS (the increasing blocks), and the ceil(n/k) because there may be one extra block, and by choosing the biggest from each block we will get LIS = ceil(n/k). Now, try for each k, and once you find the minimum sum, print the array according to the statement above. Please forgive my grammar, as I was writing this in haste :)
cut into some blocks(use sqrt)such as 9 , cut into 3 blocks,then 7 8 9 4 5 6 1 2 3,make many increase Sequence.
You can always partition the permutation of length n to have 2 specific LIS and LDS values where LIS = i where 1<=i<=n and LDS = ceil(n/i). example: n = 9 you can choose i to be 3 and so ceil(n/i) will be 3 and the permutation can be:
7 8 9 4 5 6 1 2 3
So you can easily get the i that minimizes i + ceil(n/i) and then construct the permutation in this way:
if you have a permutation 1, 2, 3, 4, 5 and the best i is 2. Then you can construct the permutation as follows: 5 3 4 1 2
another example is how I have constructed the permutation of length 9 earlier.
That is if you consider the sorted permutation 1, 2, 3, ...., n and the best i is x. 1, 2, .., x will become the last x values in the optimal permutation. and x+1, x+2, ..., 2x will be the x values before them and so on.
E is only about editing statement of appeared problem.
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
That's good!But I think the difficulties between D and E was so big....maybe I'm too weak.orz
I think codeforces servers have lost their power. Maybe for increasing the number of contestants. In the past a few contests were found that were rated, but became unrated!
Was it really necessary to make it unrated? I mean, it was just a 20-minute delay, what seems to be an issue? Everyone was in an equal position.
During the delay, no one was able to make a submission. It is unfair to someone who completed coding a problem just before the delay happened, but then have to wait 20 minutes to submit it.
Well, delay time could have been spent on solving another problem. If you managed to do 4 problems in 30 mins, you should also look on E. There were a lot of ways to hold your time advantage.
I'm truly disappointed, since this contest was combined, so a lot of Div. 2 programmers lost their chances to try competing with Div. 1 and lift their ratings quickly.
It was unfair and inconsistent with previous decisions. There were much bigger issues yet rounds were rated as f**k.
Those should have been unrated as well.
Can E be solved by constructing the convex hulls of the 2 engines and checking that one of these 2 convex hulls can be obtained from the other by only rotations and shifts?
Ya.
Statement of H was very bad. It took me more than 15 minutes to understand it.
Many statements were very bad. "English by old people from post-communist countries" tier bad. The whole contest seems like it was made in a hurry just to have it before the authors leave for holidays or something.
It wasn't bad English-wise. The story was very bad, complete mess. Idea of films and their endings and ways of combining them was very confusing. I could go on.
I don't mean just bad grammar, but the kind of lack of understanding of a language that causes the stories to be bad because you can't express yourself well. And I don't mean just bad English, I'm pointing it out as an example; the statements were very hard to parse overall.
Both FizzyDavid's(41352396) and tqyaaaaaaaang's(41353078) solution passed system tests in problem E.
But their output for this input is different:
4 4
0 0
0 5
5 0
5 5
0 3
4 0
7 4
3 7
(I think it should be 'YES')
How did all these happen?...
(Problemsettings are satisfactory, though...
Lol, yeah. FizzyDavid considers just rotations by multiples of 90 degrees which are obviously not sufficient (consider segments from (0,0) to (4, 3) and (3, 4))
Sometimes system test is very weak, especially in unrated rounds.
Yes. It was my fault.
Tests are weaker at the beginning.
Then I was asked to generate better test in order to hack:
incorrect hull, use only area and length, use only dot product, ... strange solutions
I thought it is strong enough...
I forgot this one. Sorry.
(Actually, I believe it may pass at first... My fault.)
Will there more tests added? Will all the solutions be rejudged?
We will add this test. But this won't influence the standings due to the contest rules.
BTW: Why no one hacks?
It's useless to hack when it's annonuced to be unrated..
Too many approachable problems :) . I usually turn to hacking when I have no immediate idea of what to do with the next problem, and I believe many others do too. Or when hacked solutions just start to appear, which was not the case today either.
Can someone explain the solution of div2b please !!
Consider the cases where moving a 1 or a 0 in A will change the OR of elements:
A[i] == '0' && B[i] == '0'.A[i] == '1' && B[i] == '0'.Now, if you follow those 2 cases and look closely, You can see that you can move all the ones (let's denote them by
countOnes) from A to the positions where both A[i] and B[i] are zero (let's call those positionsvalidZeros), but, you can only move the zeros from A that have a 1 below them (let's call thosemoveZeros), and it's only worth to move them where case two happens. Let's call those ones that have a zero below themvalidOnes. Now, for all ones in A, you can move them tovalidZerospositions. For all moveZeros in A, you can move them tovalidOnespositions. Therefore, the expression ends up being:countOnes*validZeros + moveZeros*validOnesDoes anyone have a good proof (or can read the Chinese editorial) for why using sqrt blocks are optimal in C? To be clear, I understand that if you are using a block method, that sqrt blocks would be the best size, but it's not clear to me that using a block method would be optimal.
Keyword: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93Szekeres_theorem
After seeing the F and being not able to think of anything other than brute force(I was hoping some good math in there since it is obviously F).I started watching FC Rottach-Egern — Bayern München which was more interesting than E and F questions.
The questions are not bad but estimation of level is very bad.F could be div2 C(at worst D) I guess.
E was interesting. It uses interesting concept of convex hull + string matching.
I could barely understand the question(mainly the legend in behind the question) and the examples were barking on my face to match the convex hulls.I liked implementing it without using doubles.But surely it is not worth E.The idea was good but the problem was not good overall at level of E.
No need to use double. Assume we have polygon A1, A2, ..., An, then just match sequence (dist(A1, A2)2, dist(A1, A3)2, dist(A2, A3)2, dist(A2, A4)2, ...).
May wrong :)
Yes I did something similar.I used side lengths and dot product of adjacent sides to represent angle.
Wow! Can someone confirm this is correct?
The sequence of pairs
(side length, angle)is obviously correct, and if we replaceanglewith dist(Ai, Ai + 2) it's still correct, as we can restoreangleby lengths of triangle sides.Aren't there 2 possible angles if we know the sides?
Nope. Law of cosines. There are 2 possible cosines (α and - α), but since the polygons are convex, it doesn't matter. You could always use all sides + area (sine and cosine) to make absolutely sure without having to prove anything, of course.
Thanks, I get it now.
Div2C? If you want to make a horribly unbalanced round, yeah.
Div2D/Div1B is a reasonable difficulty estimate, going by my impression and the number of successful solutions. Here's my idea: 3·108 is just 36 MB in a bitset, so let's optimise by ignoring numbers which aren't 1 or 5 mod 6 and do a classic, but constant-efficient sieve. This is a perfectly fine div1B; if pretests aren't too strong, people who don't test on maxtests can get burned and other people can get hacking chances. (I'm normally not a fan of weakening pretests, since I don't want to keep worrying if there are some weirder tests that make my code fail systests, but if I'm computing something that's known at compile time, I always check if it's good enough on maxtests or just hardcode maximum limits into it.)
It hurts me so much that I can't even solve a Div2.C! XD
I was under the impression that doing extended seive over blocks works reading the comments. If it works then it surely is not more than Div2D right.
I take back my claim of Div2C in case it doesnt work. But extended seive with easy implementation is good enough for Div2C.
For f**k's sake!
There were much bigger shitstorms (queue blocked for more than half of the contest, terrible statements and mistakes in the problems) on cf and rounds were never unrated. I get used to the fact that no matter what, the round will be rated because majority would be happier. For some strange reason this time it was, even though it was only 20 minutes of server unresponsiveness yet problems were available to solve.
Wtf cf?
Edit. Is it because of money prizes or what? Why to disappoint everyone this time?
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
Ahhhh
E and F, the two problems which roughly determine the 4-200 section of the standings in this contest are of poor quality.
E: disguised polygon congruence, a known problem and not a trivial one. If it were unknown, it could even be an F or a G by difficulty IMHO. Furthermore, as pointed out by others, the tests aren't very strong. They might be strong, but for this kind of problem they need to be stronger. For example, my first submission which makes an ordered triple (length, length, area) for consecutive vertices and then compares these cyclic sequences passes the system tests(as a challenge, try to think of a hack). Although the test which fails this approach is very specific, but I believe it could have been anticipated by the authors and testers.
F: the solution that uses to much memory is clear the moment you start thinking about the problem. Whether it passes the time limit is unclear, but it's easy to realize the problem is written in a way that it seems impossible to solve without finding all primes. After that, googling "Sieve of Eratosthenes low memory" and copy pasting gives you the full solution in minutes.
Omgggggg, siiiiick! That hacks my solution and Benq's as well.
4 4 0 0 1 0 4 4 3 4 0 0 1 0 -2 4 -3 4
It seems that this round should have been won by some fake blue guy :P
But if you use signed area, that is not a problem right?
I use signed area, but even though all areas I compute are positive because I operate on convex polygon. I would get different areas for angles α and - α, but it sees no difference between α and 180o - α which is the problem here
Yeah, that hacks my solution as well.
Edit: I saw the hack and get it, reflected ones are considered the same.
Yes, because the cross product gives you the sin(α), so you cannot differentiate α and 180 - α. Putting the dot instead the cross product solves this issue since all angles are up to 180.
F can also be solved by the usual sieve, using some casework for numbers divisible by 2 and 3.
41372869
I did think about it and I like E as a problem because the right encoding of a polygon matters (or, well, should matter) — how to avoid doubles, how to ensure it's unique, then stuff like no reflections = direction on the convex hull matters... however, this round was prepared quite badly.
I like F as a concept too, but if it's really easy to find, it shouldn't have been in the contest. Especially not one with prizes.
Why have my solution (http://mirror.codeforces.com/contest/1017/submission/41366026) got WA on test 20?
pref[kols][sum] += chis;
here the sum can be greater than 100. so just add an if condition
is there a difference between using
long longas index and usingunsigned intas index in bitset (in terms of performance)?41372257
41372242
Depends on which operations. For example, fetching memory: not really, bitwise operations: yes.
Thanks :)
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).
[Double comment in case people don't check the editorial]
For 1017E - The Supersonic Rocket, many of the accepted submissions (around one-third?) actually fail on this test case:
I wrote up a detailed explanation of what's going on in this post: https://mirror.codeforces.com/blog/entry/61086
Can we add this case to the practice version of the problem?
Hope that we can see contests by Magolor again.
Agree
For problem D, I use O(q × 2n) "solution" and passed it.
my code:http://mirror.codeforces.com/contest/1017/submission/41379865
The second "guy" 000000 seem to be a group of contestants. Look at the submission times, you can tell that the problems were solved separately by more than one person.
He had two submissions at the same time, right after the server came back after the downtime. There is nothing suspicious there.
lol, u guys press downvote like the other guy was right and i was wrong. At least you should check what really happended first
Maybe YOU "should check what really happended first", before making false accusations, without any real evidence.
okay, sorry for not showing the evidences.
you can see he finished A after 2 mins, then he solved C, which took him 4 min to submit at min 6. Then he solve B at min 7, which meant he had 1 minute to read the whole statement and solve B. You can see that he took 1 minute also to fix C's 3rd test, which was him just chaning '2' to '10'. Also you can see he use 4-spaces tab in A and B but 8-spaces tab in C.
okay we had been interupted by server's error. assume he solved both D and F in crashing time, ignore his super fast submit speed because maybe we could do it also (2s between F and D), then look at D and F's code. D using C pattern (he declared iterator i at the beginning), define N = 10005, while F using C++ pattern and using const maxn = 4e8. I don't think those were done by only one person.
his progess of solving E and G was also strange. sometime he submited E and then immidiately submited G. we can also see the spaces tab difference here.
Lmao rekted
Thanks to the contest makes me know such a great people. But also sadly in this way. Wish Taravilse rest in peace.
Is this contest rated??
Why am i getting TLE in D ? 41423817
You can solve each query in O(1) :)
i like cs academy
Auto comment: topic has been updated by Magolor (previous revision, new revision, compare).