Greetings! CodeForces Round #336 welcomes both divisions this Wednesday, December 23, 2015 at 16:35:00 UTC. The round is authored by me, Amor727, Chilli, and GlebsHP. We hope you'll like the problems. Scoring and score distribution: Not Dynamic; Div1: 500 — 1250 — 1500 — 2000 — 3000; Div2: 500 — 1000 — 1500 — 2250 — 2500
Much thanks to Amor727 and Chilli for writing and editing problems, GlebsHP for organizing the competition and for his very helpful attitude, Delinur for translations, winger for testing, Marina Kruglikova for statement fixes, and MikeMirzayanov for his amazing CF and Polygon platforms.
During this contest you will be assisting Genos from the series One Punch Man. His master Saitama will also make some appearances. We wish everyone good luck and high rating in assisting the two. From the contest crew and the two fellows below, happy holidays!
Congratulations to the winners:
Division 1:
Division 2:
Editorial of round: /blog/entry/22256
Auto comment: topic has been updated by ed1d1a8d (previous revision, new revision, compare).
I love ONEPUNCHMAN, I was waiting for this for ages!!!! GL && HF!
P.S Hoping for some funny jokes.
hardest contest, hardest life.
but easiest contest , easiest life :D
Yep, you're so smart :D
Div 1 contest being prepared by a Specialist? I can imagine contest setting going like this:
-GlebsHP: Seriously? A Div 1 contest being prepared by two purples and a specialist? Who do you think you are?
-ed1d1a8d, Amor727 & Chilli:
Guess I should improve my rating. :)
Round #335 also has been prepared by two purples.
It reminds me of that conversation: http://codeforces.com/blog/entry/10797?#comment-160875 :)
like One Punch Man very much!!!
Can you take a photo of your keyboard? Just interseted about chinese keyboards:D
emm...)))
Hi again guys!
Thanks for support :D
GL & HF!
P.S. When I firstly have seen this blog I thought that it was Xephy's :)
Saitama is like a reference to tourist xD. Onecodeman ;DDD
Code until you go bald :P
Hope to celebrate the Christmas by becoming specialist :)
Accepted from one submit. (c) One Submit Man
To train for this contest, every day for a year I did 100 pushups 100 situps and 10km running
It's why you are cyan.
To be RED you should do every day for a year 100 div1 C problems, 100 div1 D problems, 10 div1 E problems.
what if.. the reply from Baian is a joke too :P
he substituted the physical training with hard CF problems
To be accurate actually 10km div1 E problems ;)
It's a reference to Onepunch Man, an anime that this contest will be referencing. It's a pretty good show for someone just wanting to watch something for laughs and giggles. A solid 10/10 in my book.
A solid 5/7 from my side too!
Haha, I saw that 9gag post also
You could've done better if you didn't forget to seal your AC xD
OneCodingMan
tourist vs jqdai0815
that would be interesting.
Please Like me... Please .
Please disLike me... Please .
Poor me... T-T :( ... What was I think about my comment and the Liks that it can get.
Likes can not be beggary You must work hard and be helpful to gain them
(English is not my native language)
It will be jqdai0815 for tourist
who looks like ONE PUNCH MAN in codeforces ??
this contest will be amazing ☺ !
It would be interesting if tourist jqdai0815 rng_58 and Petr all participate in this contest ;)
Match of The Legends!!! WoW
So addictive site ^_^
One Punch Man...!! Who'd be the "One Code Man" of this contest.....??
Actually it'll be interesting to know who'll be the five code man/woman.
GL & HF !
The problem will be like determine the minimum strength of the monsters that can beat Saitama :D
in the last line, this description make the answer obvious : print -1 if it doesnt exist.
My first round on codeforces . I hope that I will will enjoy :)
tourist and jqdai0815 are online, looks like they will participate . Guys get ready for the ULTIMATE CLASH OF 2015 .
I wish tourist would become active in talking to the community. So few red coders care to participate in the comments section.
deleted (i had a mistake about times)
ANIME is the WORST ONE I HAVE SEEN
I dont think so
All of my friends who watch anime said it is at least best of the season one. On myanimelist it is placed #10 in top. So I guess you have watched only #1-9 before that one? :-P
What are you Sir Beresta :D a sword?
Nice, I've just watched first two episodes of this anime today. Guess I'm ready for this round now :D
Standard ? really ? 500 — 1250 — 1500 — 2000 — 3000 is standard now ?
It probably means "not dynamic".
Yeah, sorry this is what I meant.
I thought that "Not Dynamic" means that there will be no problems on dynamic programming ><
Spoiler alert?
Am I the only one here who doesn't watch this show?
Me neither. I watched Death note and I loved it, but I don't watch animes in general.
What are your top 3 animes Xellos? :)
i think we will hope for the many math problems!
On an unrelated note, what do you guys think is more important? Learning more and more concepts or mastering what you know?
Well i don't have much experience but i think whenever we learn a new concept we should try to solve a few problems related to it to make it clear to us . This way, we do both the things simultaneously upto a level .
When I say mastery I mean, solving 100-150 problems of that type.
Reminds me of this
Edit: That one is even better
In all rooms...
Что-то пошло не так
Actually I don't think it's a bug. Maybe it's a new feature to see all the other participants with hacks. I think it's actually pretty useful.
The thing is that these people made successful challenge without submitting a problem :) I think it's a bug in standings, though.
Anyone else keep getting a runtime error for Div2C/Div1A?
How to solve B? Is the solution is keeping remove the largest palindrome subsequence until the string become empty?
No. B is DP problem.
How to solve it with DP?
Click
No, see 1 4 4 2 3 2 1 for example.
Actually, the approach works for this example.
Remove 1 2 3 2 1, then 4 4.
deleted
I think it is wrong approach. I don't know what to do when you have multiple choices to remove the largest subsequence.
I don't know if my solution will pass the final test cases, but here it is:
Let DP[i][j] be the minimum number of operations to remove the continuous subsegment [i..j]. Then you have DP[i][j] = min(DP[i][k] + DP[k+1][j]), with k in [i..j-1]. You should also consider the case when V[i] == V[j], there DP[i][j] can also be DP[i+1][j-1].
The complexity of my algorithm is O(n^3).
Sometimes it's better not to choose the largest. For example in 32123433 it's better to remove 212, but not 32123.
Yes. But it is only the special case. You will check that '343' is also palindrom. And decide to remove '3' + '343' + '3' in 1 sec.
I think the question is quite similar to palindrome partitioning with bit modification. http://www.geeksforgeeks.org/dynamic-programming-set-17-palindrome-partitioning/
But could not get the dp relation for the actual problem. :(
B seemed much harder than C...
Yeah. Worst case complexity is 10^10 (a=10^5,b=2*10^5). How did people do it in time ?
Seems obvious that solution with such complexity won't work :)
I suspect that correct one would be like O(len(b)), however I didn't find the correct one.
I know. I didn't even bother coding something with this bad complexity.
Look at each character in A and count how many opposite characters in B it will have to pass as you shift A across B.
Now I feel dumb
Damn. So easy :(
because you shouldn't solve it 10^10
The correct solution is like that:
Take a note, that you asked about the sum of "differences", not to count all differences. This leads to following approach. Fix some position in second string, and the first string will be shifting relatively to second one. Actually the positions, which are opposites to our fixed position, are making a subsegment in first string. And you just need to count how much exist chars different to fixed one in this subsegment.
When you step from currently fixed position to next one, the subsegment is moving to the right. So just maintain the count of chars of each type in current segment and advance it carefully.
Even better. Make a segment tree to count 1 and 0, and call for each index in a.
Even better. Make an array with prefix sums to count 1 and 0, and call for each index in a. :P
Agreed
Even better :). You need an array only for counting 0s because the 1s for some segments are equal to = length of segment — number of 0s for this segment.
That was what I meant, one array is enough, our statements are the same :)
"Fix some position in second string, and the first string will be shifting relatively to second one."
How the first string is shifting relatively to the second string if the position in the second string is fixed?
I mean imagine the process of taking differences of A and substrings in B as imposing A to some place in B. You can shift such a place and the imposing part is shifting too, consider all shifts, which overlay fixed position.
The same for me.
Если D решается динамикой по подотрезкам, то у меня походу бомбанёт, что мне не хватило минут 5 отдебажить код =\ P. S. Ещё из-за плохого копипаста не прошла C :(
именно так она и решается)
Да сам виноват, поздно понял, что эта задача очень похожа на ту, которую решал буквально 2 месяца назад :( Больше всего раздражает, что у меня выходило где-то 7-8 разных случаев, и в каждом нужно убедиться, что не ошибся где-то на единицу.
How to solve Div2D? I think it is dp[from][to] but I kept getting WA #14 :)
PS: I realized where my mistake was :)
I know that feeling very well.
Well, no need to wait for systests, it's back to Div 2 for me.
I'll try to boost my self-esteem with a virtual contest...
Lagged at the last 10 sec and couldn't submit B. I think the solution is correct. I hate when something like this happens :/
It will be fixed soon.
when will the system test start?
Soon!
I solved B Div2 with prefix sums
Your code looks sharp and understandable to me.
Could you, please, explain how did you come up with the solution?
Do you have some napkin drawings left? :)
Can someone help me figure out where my code fails for 2C? https://code.hackerearth.com/a0bb04m?key=71b2fc5852347cfd361c5a3802736190
You need to sort pairs before doing binary search and dynamics.
damn... rookie mistake.
Ugggh got me too. I spent forever trying to figure out what went wrong they were all presented in order until pretest #9.
I solved problem C(div2) by binary search? How do you think will it pass?
It should, if it is the highest complexity in your solution (would be like O(N logN)).
Made binary search but got TL on 38 test... http://codeforces.com/contest/608/submission/14955285
Could someone tell me what's wrong with my code for div2 C? http://codeforces.com/contest/608/submission/14957339
Thanks every one...
tourist come back............? tourist.........3374 TooSimple...... 3112
Rating changes please.
+40
-100<rating change<100
In the previous contest I had a -118 rating change.
thanks for completed quickly system testing and also will be so happY if rating update quickly.
Bruteforce get AC on DIV1 D? http://codeforces.com/contest/607/submission/14951821
-_-.....
How poor testing must have been so that such solution passes :|??
LOL. The test setter probably thought that div 1 guys know complexities well and would not attempt to write such a solution :)
Even funnier is that these ineffective solutions have the best running time :D Don't waste your time preprocessing, mr. coder.
The slowest it gets is 171 ms with a TL of 3.5s. That's messed up.
I was in charge of tests for this problem and made the mistake of generating queries randomly, which gives them on average a very low complexity. We failed to catch this during our internal testing due to the fact that our sample brute force had O(N) updates and O(1) queries (instead of the O(1), O(N) like here). My deepest apologies, I'll definitely be more careful in the future.
Blue -> purple -> yellow :) Just in 3 contests
It seems that there is a new test now, a rejudge, and you're 166th. Adding tests for the archive is commendable, but I do not approve of messing with the scoreboard :>
:< Wow another mistake. Apologies Meirambek, I'll return you to the scoreboard.
Try to resubmit your solution!
От души братан :)
Can anyone tell me how to solve div2 C?I think it is at least not bad to boom ith beacon if activate it will destroy k beacons(k>1),so I do it by something like Prefix sum ,but keep WAing on test#11 QAQ.Is my thought totally wrong for this problem?
Don't get your solution, but my AC was like that:
For each beacon from 0 to n calc how much beacons would be destroyed if i-th beacon is starting one, using dynamic programming (we have calced all lower ones before i-th, so could be reused) and binary search (to find how many beacons destroyed by i-th). Complexity here is O(n * logN).
After that try to disable from 1 to n beacons and calc best sum using data from the previous step. Complexity here is O(n).
my AC was : http://ideone.com/z8dqVj ( No Binary Search )
consider this dp state ,
dp[present_pos] = total_beacons_affected_by_present_beacon + dp[previous_unaffected_beacon]here, previous unaffected beacon means the beacon which is unaffected by the present beacon
After that try to disable beacons from present pos to n and calc best using the previous data
i.e., min of
total_beacons-total_beacons_until_this_beacon+dp[present_beacon]all positions .matthew99 first. LOL:))
really is he/she a middle school user? O_o
Yes he is.
Probably from his handle, he is born in 1999 ;).
Yes,He is
Hi everyone, this is my first contest on codeforces. Someone could tell me when the editorial will be posted? And when the ranks are updated?
Editorial already posted http://codeforces.com/blog/entry/22256
About rating, nobody knows)))
Thanks!!
Rating is a precalculated result.But why every time it should be given so late. Above 2 hours..but it should not be updated.
And after every contest there is a dilemma: go to sleep or wait until raitings are updated...
Ratings updated.
Why DemiGuo's rating did not change being in TOP 5?
It seems that her submits are skipped... so strange! it's impossible! She was 1st for a while in contest! MikeMirzayanov , what's going on?
I'll be happy to read explanations about the submissions:
I'd wager coincidence! The programs are small, and it seems highly unlikely for someone in Demi's position to consider cheating. Sadly I also can't offer much towards improving cheat detection.
Edit: a friend of mine thinks the similarity is "clearly not a coincidence". Sigh... how does one reason about the probabilities involved here? Could be a scientific research question. Perhaps the users involved will make a statement, unclear what good that would do. I thought it better to give the benefit of the doubt, but hey at least we're not banning users.
Have you taken a closer look?
These parts:
differ only by replacing a with A, b with B and nxt with Next. This is NOT a coincidence.
Also, they both have unused variables named now1 and now2. As much as I want to believe this is a coincidence, this is really hard to explain away.
It's possible you're right; it just seems weird from a psychology angle. Keep in mind there are a lot of pairwise comparisons to be made on Codeforces, so unlikely events can happen. A lot of the similarities are very natural simplifying choices to make (i.e. low entropy). We should check for stylistic consistency with her other submissions; that might "explain away" some of the coincidences.
I'm just having trouble imagining someone with legit skills wanting to do this (especially when you're female so the whole world is watching you as sort of an example); even if it were, the code could have been disguised a lot better.
Edit: I didn't notice that now1 and now2 are unused :/ Damn whyyyyy
If we assume that cheating did take place, what happens next? It looks like you can get away with cheating if you have the skills and take effort to obfuscate the source. Will Demi and others just get better at it? Do many orange/red members already do it??? Deterrence is hard if people with actual skills cheat.
When someone doesn't try to hide the fact that they're cheating, they really don't care about consequences.
AC submissions are not only ones should be looking at.
Consider submissions:
They both WA9 and use such algorithm simulate first string, simulate second string, simulate first string again (the first submission contains original reference to now1 and now2). The second submission simulates second, first, second (probably because the first got WA9).
i didn't want to say this just because i didn't want to attract attention but you guys made me say it ;D, from what i see from the coding style of both accounts the owner is the same person!
Why do I have TL with O(n*log n) solution on div2c? http://codeforces.com/contest/608/submission/14955285
could be an anti-quicksort test case. (quick sort has worst case n*n)
Div1C was a very elegant problem, I really liked it.
Thanks! I worked quite a bit on that one.
Div1C http://codeforces.com/contest/608/submission/14965956 Who tell me what is the wrong? I try to get the 30th data,the last 10 letters of the first string and the second,using this method if(n==999999&&a[0]=='W'&&a[1]=='N'&&a[2]=='W'&&a[3]=='W'){ puts(a+n-10); puts(b+n-10); } but I failed,because I find the 20th data is same with the 30th I also have try to run other's program to compare with mine using random data,but never find the difference. Who can help me ?
Saitama Sensei!