418 I'm a teapot
Hi everyone! >///<
I'd like to invite you to Codeforces Round #418 which begins at 15:05 MSK on 7 June. Please note that the timing is unusual.
This is my first round here! KAN reviewed the contest and helped me through the preparation process, while Alladdin, FalseMirror and Tommyr7 tested all the problems, and MikeMirzayanov and the awesome Codeforces and Polygon platforms made all this happen miraculously. This wouldn't have been possible without your efforts!
The round is rated for the second division, and participants from the first division can take part out of competition. As usual, there are five problems and two hours to solve them. The problems will feature... Well, let's wait and see :)
The scoring distribution will be announced later.
Hope everyone few bugs and fair ratings. Looking forward to seeing you then!
UPD 1 Scoring will be 500-1000-1750-1750-2500. It's recommended to read all problems' statements so as to find the problems that suit you — we tried quite hard to make them clear and interesting.
UPD 2 The round is delayed for 10 minutes due to technical issues. Apologies.
UPD 3 System test is done. Congratulations to the winners!
Div. 2 Top 5
Overall Top 5
Hope you all enjoyed the contest. You all did a great job! The editorial is on the way, please be patient :)
UPD 4 For the impatient, here are the tutorials for problems A to C. More are coming!
UPD 5 The complete editorial is out. Cheers!
Is it rated?
is it "is it rated?"?
yes, it is "Is it rated?"
I see that you have experience. It is rated! is it rated?
also, are u real Alex Navalny?
20!8
Блэт, Нэвэльный!
Whats that comment? 8-)
"first"
First
Edit: Dang it, it's not bad enough to get 100 downvotes.
maybe "i'm teapot"?
выйду в div1, скриньте
Заскринил, проверяй :3
Just in case anyone is scratching their head: https://httpstatuses.com/418
Возьму 156 место скриньте
Гениальная шутка, случайный незнакомец
why always scoring distribution is announced later ?
it's just because you have no girlfriend.
codeforces is not a place for such shitty jokes.
purple guys are allowed to say everything
and blue are not
I would like to prove you wrong by typing that comment, but I prefer to keep my contribution. It is not purple, but it's because the guy is Bredor. Look through his comments and you will know.
And don't copy-paste buddy.!Be creative and make your own jokes..!
Bredor is a famous troll and everyone knows he writes sarcastic comments all the time.
While your comment was ill-timed and not even funny.
Hmmm... It seems like Alladdin and amethyst3 are brazzers
Hope to see a
NORMAL CF ROUND
What do u mean by "Normal CF round"?
3000 — A 2000-B 1000-C 500- D 50-E *Numbers of Accepted submissions
500-D ?? that's normal ?
You mean you're waiting for the delay ?
As a tester, wish everyone good luck and have fun!
Haven't seen a Chinese round for ages. Cool.
My roommate wants to take part in a round by qls before he dies!
Me too!
I'm a fan of quailty ！！！
I'm a fan of quailty!
Hope it could be easier than last Chinese Round
Link ?
418 I'm a teapot so for this round you will enter as a normal water(current rating )and exit as hot water(current rating+154).
For what it's worth, I hope you're right.
It's only for my current rating and to need for make me pupil . But for you it's maybe 129.:D
Yeah I noticed, but getting 154 wouldn't be bad for me either :D
I hope you make this done but in my case for getting 154 need more heat that's so hard .
It is easier to get +154 rating with current 1046 rating, than getting +129 with 1771 rating.
The time when the contest will be started it is 'Iftar Time' (Fast Breaking Time) for Muslim in southern Asia. It will be better and helpful to us if the contest starts an hour later from that time. cyand1317
Meanwhile it would be quite late for participants from eastern Asia, it's just difficult to meet everyone's needs... :( If the timing does create difficulties, you can try virtual participation later. Apologies for this.
(It would be great if authors have a list of different regions' occupied time intervals...)
Thank you! I got it.
Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
It should be 500 — 1000 — 1750 — 1750 — 2500 right?
Teapots also make mistakes like humans do... You know.
Have you noticed that the round number is the reversed contest number ?
Contest number is 814 and the round number is 418.
Well, I'm 4 min later than you.
Problem C and D have the same score!Amazing!
A 1750 C always makes me upset :(
Data structures and Constructive algo related problems may be exist in today's round...mathematical term too :)
10 min extensions seems to be a template.
The CodeForces classic, never fails
you are getting 3 upvotes/sec xD
Contest extended by 10 mins ... :)
you mean delayed ? :D
contest delayed?
Yeah it seems :)
which directly means, we will get less time for dinner , because after this, there is CSA contest also :P
what is CSA contest ?
sorry , I misread the contest . it's on 8th June . My bad.
That's tommorow.
yeah , I saw it just now.
10 minutes fact!!!!!!!!!!!!!!!!!
Coding ended(Ramadan and Iftar fact).
Everytime :(
Contest Delayed , Maybe a good time for more contribution .
It won't be a normal Codeforces round if it is not delayed :D
Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
This time no zeros are dropped, believe me.
10 minutes delayed???
A Codeforces contest really cannot be regular without a 10 minute delay, can it :)
clicked 'ok' to go to contest arena and then 10 minute delay!
Show the time of the contest 10 minutes later so then u don't have to delay it every time !
why there's always 10 minutes delay?
maybe because of love.
maybe because we are family
hahahah BC
10 mins again
10 minute delay is a tradition now in Codeforces
May I ask, what kind of of technical issues causes delay by 10 mins?
Someone getting late to work? :)
A ten minute delay for me to make a beverage, thank you!
6000 People registered for the contest. 10 minutes delay means 6000*10 minutes = 1000 hours = 41 days of their life. Just saying. Waiting sucks.. :(
normal codeforces round = The round is delayed for 10 minutes due to technical issues
It's about Monogatari! Now it is somewhat interesting. 8-)
There's some spoilers in task statements lol(but I had already completed mongatari series).
I am only mid-way through the series, and I am pretty sure I got spoiled by B,C,D — but who cares! I should be fine as long as if I don't lookup for the characters' name in English.
Actually you don't) Especially B, C and D, they have nothing to do with the plot. While E is taken from the first episodes you would watch.
I kept that in mind while writing statements so as not to contain spoilers to the anime.
lol, after reading A and E I assumed that the others are about the actual plot as well.
Good job for not spoiling the amazing series. :)
I should have mentioned that in the announcement ._. Did this scare some of you away?
The oddity within my buggy code did scare some of me away. :P
Does that part of you want to go home for now? Is Mayoi visible?
The debugger window shows traces of Mayoi within my recusion loop right now.
Anyone else facing the issue of getting logged out constantly? I had to login at least on five separate occasions during the contest. Not complaining, genuinely want to know whether mine was an isolated case or not.
Same here.
Same here. About 10 times.
this B made me crazy
waiting for the end of contest to see test 6
also test 2 : In the second sample, 5, 4, 2, 3, 1 is the only permutation to satisfy the constraints.
dive me crazy , why 4,4,5,3,1 is not accepted !!
Because {4, 4, 5, 3, 1} is not a permutation of the numbers from 1 to 5.
uh, well
i also misunderstood this point
thanks
i made the permutation but still getting WA on 9.
can there be more than than 2 positions where ai != bi??
no , one or two , it can't be more than 2 differrnces
No
now i got the mistake, i found no. not appearing in a and find the it's correct position. but position was not found correctly in my case.
It's a permutation. every integer from 1 to n must appear exactly once
didnt get the point :/ , RIP rating
You could contact with them and they are very helpful, they helped me alot =D
In problem C, n*q should pass but my solution got TLEd on pretest 10. :/ why?
I used sliding window, total operations 2 * 1500 * 200000 = 6 * 108
Repeating answers are there. Total answers are 26*1500. Store them.
Yes, there are 26 * n possible answers and you can precalculate them all in O(26 * n^2) using two pointers.
I am afraid that is a bit too slow for a 2s TL, while there exist an O(n^2 * 26) solution.
What exactly?
why the n^2 ? I think a 2-pointers solution should run in O(n*26)
I just preprocessed every single combination that could possibly appear in the query, i.e. for each character O(sigma = 26) and each segment [l, r] O(n*n).
I don't think you could solve it in O(n*26), even for a sliding window 2-pointer solution it should take O(nq) or O(n*n*26) — but hey! It's surprising to learn that someone solved the question in O(n*26), would you share your method to me?
Oh sorry I was mistaken. it's a O(n^2 *26) as well . I forgot the original loop that considers all cases of m.
Usually 1 sec is equivalent to 1e8 operations.That's why your solution exceeded the time limit. Btw I implemented an O(N*N*26) solution.
My (26 * N2 * log(n)) solution 27641415 got AC which is also around 6 * 108
I even got AC with O(n^3 + 26*n^2) solution =))
I passed with n*q
Solution
my solution is the same complexity and got TLE aka.Sohieb
27649598
Same here bro :(
Hello, using cin.tie() and cout.tie() works fine :)
My submission
Even I also got TLE in beginning, but then I just uncommented one line(First line in the main function)
My first submission with TLE
What is intended complexity of B solution? I solved it in O(n) and now i'm scared that i've missed something.
My complexity is same. P.S. 70 lines of code...
Yeah, about 80 for me. Hope it's okay...
Mine 61 with a 13-line fast read... Am I missing something?
Mine 15 line code in python
I think it's solvable in O(n) but there's a simple O(n^2) solution: find the two positions in the first array which has the same value(there will be exactly two of them). Replace one of those two positions with each of 1~n and verify if it's valid.
And how to solve D?
Not sure if I will get AC, but I constructed a tree, where x is parent of y if circle y is inside x. Then dp: f[u][x]=maximum area of subtree u if there are x nodes in the first set.
what is generator command line argument ??
Is the following solution to D correct? It passed pretests, but I'm not entirely convinced. If circle is inside odd number of circles or 0 circles add its area, else subtract its area.
i did the same
I did DP on graphs
I think the expected solution is a DP.
If I understood your algorithm correctly, your algorithm should fail on this case:
Edit: Incorrect test case
Actually the answer here is the area of the large circle + the area of the second largest, which is the same as my algorithm.
Ah you were right. I think that solution should AC
How do u check how many circles it is inside.
You just do O(n^2) to check how many circles contain a particular one.
No. Like there are 2 circles. How do we check if one if inside the other?
Distance of two centers is smaller than the difference of two radius
Yes,its true!If we're taking the outermost circle(not covered by anyone) as a single unit it
Great round!
I must be misunderstanding problem C. Can someone explain to me why this solution is wrong?
For each subsequence of s and each character c:
Then for each query (m,c) just output best[c][m].
I'm pretty sure my code has no bugs but I keep getting WA on pretest 7.
I did the same and passed pretests, maybe you are forgetting best[c][moves]=max(best[c][moves],best[c][moves-1])
Actually I took care of that too, but still WA. :(
maybe forget best[c][moves] = max(best[c][moves], best[c][moves — 1]) ?
best[x][y] can't be greater than n.
Haha nevermind, it was a stupid bug where I mixed up the indices of i and c at one point. Good thing this round is unrated for me. :)
I solved B but i'm interested how did you guys solve it??
You didn't XD
Let res be the permutation we need to find. Now it is easy to observe that there can be only at most 2 numbers missing in res according to given a and b arrays. Now find those missing numbers and assign those numbers in missing places in res and check if the res is valid or not.
Yeah, it's time to compile error in 20 seconds before the contest ends(27649694).
The reason was that locally I have kotlin 1.1, but cf has only 1.0. Comp error appeared twice in this contest. So sad =(
But would it pass if it had compiled?
What is solution of Task C? I think there is pre-calc and DP, but what is rule for dp of this problem?
No Brute force for C takes O(n^2*26) iterate over all substrings 26 times.
http://paste.ubuntu.com/24800897/ a solution. PS: I don't know if this will pass systest ;) Edit: AC
Thank you Chinese for this round :D
Как решаеться задачa С
Всего есть 26 * n вариантов запросов, для каждого из них нужно заранее посчитать ответ. Это можно сделать использовав метод двух указателей на строке. Сложность будет 0(26 * n * n).
Но я не уверен на все 100. Мое решение еще не проверено на систестах.
Прошло, вот код http://codeforces.net/contest/814/submission/27648048
красава )
Very fast System testing!!!
I was logged out several times (using google account) which is not nice. Please fix it!
What's the intended solution for E? I drafted a O(n^4) (roughly) DP solution for it yet somehow it fails me even on the sample test cases. :/
http://ideone.com/kOBovo
Edit: nvm, I am completely off the track.
RIP B
What is f**cking going with cf? Why I'm loosing task because of compilation error with "M_PI" in GNU C++14, although it's work on my compiler, which is GNU C++14 too?
Show us the code
Here it is: 27649530
Just googled online and it appears that it has been removed from the C++ standards, RIP.
Okey, thanx. Now, there is question, why it's still working in compiler in linux?
Maybe your compiler is different than cf's.
I am not sure about this — but this stack overflow post might be helpful: https://stackoverflow.com/questions/29264462/m-pi-not-available-with-gcc-std-c11-but-with-std-gnu11
The first answer also mentioned a post: "GCC 4.9 when used with -std=c99 doesn't define M_PI, but does when used with -std=gnu99", maybe it's about the -std=gnu flag, as it is also used by CF.
But I'm using -std=c++14.
Okay, maybe it's because of different in Linux and Windows compiler.
Thank you, for helping solve my problem, it's just blow my mind, because it was possible to enter to div.1.
Yeah, but GNU C++ should include it. Maybe its because CF runs on windows?
it's not cf fault :|
I experienced exactly the same thing when preparing the round. Perhaps you could just add an extra
#define... Well, as long as something's learnt you're improving yourself =)I can't understand why Reyna solution 27632209 for problem A got WA?!!!
Checker comment
Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\e034999a3f1f1dd18b018c40c84c8c46\check-f7e8e87d48909eaa32eeaee49e520cf4\run\output.fd0138e687.txt.What is the meaning of that?!!
Looks like cf error(look at the checker comment).
500 Internal Server Error :-)
Something's broken, we will fix that.
Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
why i got a wrong answer like this？
Can't find file C:\Contesters\Work\invoker-prod\work\codeforces2\838e4a3610786f013367ecfa30b8ac63\check-b58f02c6459228487139e47a79e2e72e\run\output.fd0138e687.txt.
Something's broken, we will fix that.
thanks
What was the approach to solve problem B?
Just split in two cases, one with only one number who differs, and another with two, use a set in the first case (you need to know the number who is missing) . And in the second case, generate the two possible vectors and use two sets, insert each vector in a different set, and print the one with setsize == n.
Thanks for your reply, I also read the editorial and your approach is different and also interesting. I think your approach is more efficient, is it O(n)? The editorial approach is O(n^2) I think
I think it is O(nlogn) because of the set. You can see my code (27639904)
ok, at first, there is a simple observation. a and b can only have at most 2 different positions where the numbers aren't same. So you should think of these 2 cases.
Case 1 : Only 1 different position(Sample testcase : 3) Here, u should check which is the missing number from 1 to n, and put that into that position
Case 2 : 2 different position (Sample testcase : 1, 2) Here, there should be 2 missing numbers from 1 to n. try putting them into those positions and see if the permutation is valid. One of them will be valid and that's your answer
How so? I think even in case 2 there can will be only one number that differs ?
I think u don't understand what did I mean with missing numbers. ok, look at these.
so we know for sure, 1 3 4 is in the permutation and 2, 5 hasn't been used yet. So these are 2 missing numbers which should be used in these two (?) positions
After seeing the system test, I wish I worked on hacking B. I saw no one was hacking B and thought maybe those pretests were quite good. Alas!
Why does greedy approach work in D? In each step of dfs(start from outer circle) try to put new circle to part where it gives positive area. http://codeforces.net/contest/814/submission/27649536
Well, if we put a new circle (call it "Ci") to part where it gives negative area instead of part where it gives positive area, we lose 2 times of circle Ci's area. No matter how we divide the circles in circle Ci into 2 parts, each part will contribute less than circle Ci's area, so the sum is less than 2 times of circle Ci's area. So it's better to put new circle to part where it gives positive area.
thnx
What was wrong with test case 22 in B? My output seems to be correct? :/
http://codeforces.net/contest/814/submission/27638764
your output differs from sequence b in more than 1 position (first and last positions)
Then Test Case 21 would have given WA as well! Same goes for 18!
in tc18: your output mismatches sequence a in only one position (third position) and mismatches sequence b in only one position (first position) so it is correct
in tc21: your output mismatches sequence a in only one position (fourth position) and mismatches sequence b in only one position (first position) so it is correct
Thanks I got it! :D
nope. look closely. your output should differ exactly in 1 position. Test case 21, 18 is alright.
Thanks! I understood! :D
please help me to understand the below solution has loop as (in main()) for(w=1;w<=9000000000000;w++) { r=r+2; } even then why its not giving TLE?link hereIt's optimized to O(1) by "-O2" switch.
How my code for Problem C got accepted? I made ans[2000][26] in my code and i was using ans[x][26] in my code. (Due to linear storage of data in cpp? )
(Yes.)
Can anyone tell why my C fails? Thanks a lot.
Basically for each alphabet I created a vector of <Cost, Profit> where Cost number of color is to be recolored and that would result in a subsegment of that color of at least length Profit. And for each query I just find the upper bound base on m and calculate the answer.
http://codeforces.net/contest/814/submission/27647932
28 aaaabbbaaabbbbbbbbbbaaaaaaaa 1 3 a
You'll choose to fill change it into aaaaaaaaaabbbbbbbbbbaaaaaaaa (gives 10) wheareas aaaabbbaaabbbbbbbaaaaaaaaaaa is better (gives 11)
Rating update please. I will be expert for the first time :)
It is really very good feeling!
Congratulation :D
Thanks!
Wow! +803!
Congrats! Codeforces hot news without doubt.
Congratulations! I'm waiting for this moment too :-8
Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).
didn't know CF compiler was so fast that it would support complexity of O(2e5 * 1e3) or O(n * q) for C
please help me to understand the below solution has loop as (in main()) for(w=1;w<=9000000000000;w++) { r=r+2; } even then why its not giving TLE?link hereMaybe compiler optimizations
Pretest so weak, FST so much . TnT...
Please note that the ratings are not final now and are going to change a bit because of the issue with a couple of submissions. We will rejudge them and update the ratings, don't worry.
Did anyone else assume the garland to be circular. :(
Yes, it's my carelessness not to mention that it's linear... Though the word "garland" in CF has been used to refer to linear lists quite a few times. Apologies for this. T^T
This is the biggest increase of rating ever in codeforces Right ???
This is the biggest increase even after he was hacked on A and B.
(If you can't see the photo click here)
Well this is weird ... on Mhammad1's profile it shows that his rating change is 803 but on the friend's rating change list it shows that his rating change is 681 ... is this a bug ???
On the friends rating change list it shows that his rating before the contest was 100 but it actually was -22 ???
Please Help! Why does testcase 6 fail? Submission
You are expected to output a permutation of first n number with given condition. Your output have 4 repeated.
Ребят обьяснити почему во 2 задаче к тесту 4 3 2 1 3 4 2 1 2
не подоходит вариант 4 2 1 3
у меня это выводит он вроде правильный а засчитали как неправильный
Ответ 4 2 1 3 правильный, но решение, которое ты посылал, выводит 3 2 1 4, что неверно.
та я уже понял В-Внимаельность
I solved the D without DP and it worked. code
Yes, greedy seems to give AC for this. :D Congrats :p
For question B, I ran my code in c++14, it gives the wrong answer on test 39 but the same code i tested on c++11 (also on my machine), it gives the correct answer. If is a cf bug? here is my code http://codeforces.net/contest/814/submission/27655109.
In the function
findNum, you checktemp[i] != 1without previously initializing thetemparray. So it's up to the compiler to initialize that array with anything (even 1s). The same solution with explicit initialization passes in C++14: 27657207The first letter of the second word of the problems' name are "aeiou", and prepositions are also different. Interesting name ~ :).
Auto comment: topic has been updated by cyand1317 (previous revision, new revision, compare).