Hello Codeforces community! I'm happy to invite you to participate in Codeforces Round #269 for Division 2 which will be held this Friday, September 26th. As usual first division coders are invited to participate unofficially, I would appreciate a lot if they will join.
All problems are mine, so if you won't like them... well, you know whom to blame for those. I did my best in order not to disappoint you.
Since this is my first round, let me introduce myself. I'm 27, have around 7 years of programming experience and was never into ACM/ICPC and stuff like that before, learned words like "dynamic programming" couple of years ago from the algorithms course on Coursera and a bit later found this site. I'm from Saint Petersburg, Russia, was born and lived here until I became 24. Then I got married and me and my wife decided to go live somewhere else and we moved to Kyiv, Ukraine, and we love that city a lot and we will return there some day, hopefully soon.
I hope you will find my problem set interesting and varied. Meanwhile let me get you prepared for the round and introduce you the guys you will help to. So the heroes of my round are three animals from Saint Petersburg and Kyiv zoos. Those are Menshikov and Uslada ("Uslada" means Delight in Russian) — polar bears, symbols of Saint Petersburg zoo. These are my favourite animals of that zoo, they can do a moonwalk dance. Their third friend would be Khoras — an elephant from the Kyiv zoo, not sure what kind of dances he likes but he was very friendly last time we've been there. I was always fond of polar bears and elephants so now I have a round with them! Hope you will remember their names, in problem statements I call them by name and by animal type interchangeably. They want the friendship to exist between their countries and they have some minor problems you can help them with.
Traditional and untraditional regards for this round go to:
MikeMirzayanov and the entire team of Codeforces for the site,
Gerald for his help with the problems,
Maria Belova aka Delinur for the translation of the statements,
last but definitely not least, my wife Tanya for her infinite support in everything I do. This round wouldn't be here without her.
Wikipedia asked me to remind you that the day we'll have the round (at least in Russian tome zone and time zones close to it) is 269th day of the year, matches the round number perfectly thanks to Gerald's scheduling skill.
If you read up (down?) to here and I still have your attention then let me know the secret every non-red coder wants to know — in order to become red you need to solve at least 1513 problems on this site. That's a personal experience, trust me.
Another thing I'd like to mention here: gojira was cheating! In his round announcement he mentioned that he's taking the 'eldest problem setter' title from Sammarize but he didn't mention his age, so I can't tell whether this title should be mine or not. gojira, please let us know ASAP!
Will see you on the round and I will appreciate a feedback (both positive and negative) a lot!
P.S.: as usual the scoring will be announced closer to the start time, hopefully my memory won't fail and I will update this blog post then.
upd 0: small update for the English version. In English statements the names of the characters will be Menshykov, Uslada and Horace, don't get surprised :-)
upd 1: scoring will be a bit different from normal today: 500, 1000, 2000, 2000, 2500
Thanks to everybody who was with us today, hope you enjoyed it! My congratulations to the winners. worse didn't take part in today's contest so the fight was tough on both sides of the table. While Menshykov and Uslada are updating the ratings, Horace is finishing the editorial, he's promising it will be ready a bit later today.
I understood and noted some mistakes of mine in this contest, but please let me know if you have anything to tell about it. I like how it's started, thanks for beating the 5K record, that's awesome.
Unfortunately nobody solved E, though hos.lyric was very close to it. His solution failed on the second to last test, which I didn't consider to be a max test. I consider this to be my mistake that I underestimated the problem, otherwise I would leave it for some next contest.
Will see you at some next round,
tourist has solved only 590 problems ?!
Oh, come on, leave a space for a joke in this post!
Otherwise I should probably remove 'on this site', I bet he solved WAY MORE than this number of problems.
I think, marat.snowbear talked about the coder like those, who has just started their competitive programming life. If you tell about tourist, he started his journey in codeforces in 2009. But before it, he achieved gold medal in 2007, 2008 and silver medal in 2006 in IOI.
One of his famous remarks, made in an interview after the IOI 2009, was "I am no genius. I am
simply goodat it." (I have known it from wiki). So actually he was
simply goodeven before he started in this site. :)
But my question to marat.snowbear is, why it is 1513 exactly ?? :P
What is about 1512 ??? :P
At first, I thought reading full blog will be boring... :P
But after reading full blog, it has given me some pleasure. :)
You have made me known about Saint Petersburg zoo. And nice to see you as a good husband. :)
1513 was the number of problems I solved in CF archive when I became red for a couple of rounds. I remember I saved that number to have an answer to the questions like 'how much do I need to work to become red' which are raised occasionally here in blogs :-)
You are correct this number refers to those starting this kind programming, like me. Those who started in school or university and if they target for IOI or ACM they probably have trainings and lessons where they solve a lot more problems, it makes it hard to estimate the number of problems they solved in total. As I mentioned in the post I wasn't into ACM in the university, so the only problems I solved are those in online judges. And around 90% of the problems I solved are from CF, so the number 1513 is very close to the total number of problems solved by me by the time I became red.
Where can I see the number of problems I have solved?
Here. You have 109 right now.
Go to this link to see the number of problems u have sloved http://codeforces.com/problemset/standings
Every time I open a OJ, these five guys (HanSheng Huang, MengQi Ma...) just appearing.
BTW, getting 1513 solved problems on CF is pretty easy, because we have enormous number of very easy problems here; so i think that someone may understand your words literally, set this number as a goal, and then he'll be disappointed when after solving 1513 easy problems he will be just orange or even violet:)
Thanks for your story, i often receive similar questions, now i'll have one more example to show:)
Well, that was an irony and there is always somebody who doesn't get it. It won't be an irony otherwise.
Since you're the leader now in this ranking with big advantage above the second guy (3205 vs 1933) I suppose that majority of those problems you've solved are very easy ones. Why have you done that? You're red coder and it doesn't seem that you really needed that. Do you find challenging solving As and Bs from Div2 or some regionals of nowhere :P?
I, for example, solve div2 A/B just to have green spaces instead of blue ones. After all, checking colour (green/blue/white) is faster than checking the written division number :D
Lol. "Codeforces grinders" :P. People who have time for filling that list with green color — you are happy people, I say :P. Though maybe I will have more time for solving problems if I would cut on permanent spamming in comments :P.
You tell me about permanent spamming in comments...
First of all, there are lot of contests where you have to solve very easy problems very fast. Personal contests like CodeForces, TopCoder, SNxS, 101 Hack, CodeChef Cook-off and so on. At TopCoder solving only first problem with good speed is enough to become red. And often it is also true even for team contests. At SEERC2013 you had to solve 7 problems to qualify for World Finals (well, there was no need to do it fast — all universities with 7+ problems qualified), and in online version of this contest SPbSU4 solved these 7 tasks in ~70 minutes:)
Among contests which i did in CF gyms most are displayed blue, not green. I mean — i still have problems to do in most of them:)
And when i am looking at some contest that i did year ago with results like 9/12, and then take a look at problemset — i often think "what a hell, why i did not managed to solve all 12?" I would say "i am red because i did all these problems", rather than "i did all these problems because i am red and they are easy". I was not red year or two ago:)
BTW, you may assume that i like coding, or like that feelings when you have AC-ed new problem, or simply wanted to become top-1 in problemset, or was focused on preparing for "easy contests with easy problems", or anything else like that. None of mentioned is true, but i don't want to discuss my reasons and motivation here, i don't think that it is proper place for such things.
There are only 8 coders who have finished 1513 problems, in spite of 5 vjudge robots... But there are 16 IGMs and 467 GMs......BTW, the number of rank 16 in problem-solver is 1408, and the 483th is 461~
It seems to be the longest CF Round announcing post I have ever seen.
But it's one of the most interesting posts I have ever seen. I even tried to remember the heroes of this contest :D
I think that the author took the contest very seriously, let's wait for the problems :)
Так вот почему раунд перенесли с четверга на пятницу.
never into ACM/ICPC and stuff like that before
It Will Be A Great Inspiration For Me
What a great introduction! All the best for your first round marat.snowbear :)
Impressive intro. I'm looking forward to your round
I thought I would skip the round(as it is unrated for me) and watch some movie or something. But after reading your blog post, I think I will take part :)
There is a mem in Russian saying that "while you're sleeping your opponents are levelling up" (originally it was about some online game where you need to spend a lot of time to level up further). Same saying works for watching movies ;-)
So, how was the movie?
I had to go out and I came 1 hour into the contest, but then I realised that I didn't register, that is actually stupid of me, but I tried the problems and was watching the standings, the problems are indeed very interesting, hope you set more contests in the future.
Glad to see a different announcement post for a change :-D.
Hope that the problem statements won't be long as the blog entry! :D
"know the secret every non-red coder wants to know — in order to become red you need to solve at least 1513 problems on this site."
So, If I participate in 1513 div2 round and in all of them I solve problem A, in the next round I'll be a red coder? Great! :-)
If you really understand it from that line, then wait until 1513 rounds in codeforces. :O
It has taken 5 years to complete 268 rounds. From normal mathematics, you have to wait more than (28-5)=23 years more !!! Hope you will be RED after that time !!!
I understood his line but you didn't understand mine.
hahaha funny intro for your Round, I guess I'll be having fun with problems' statements too. Won't miss this one.
such an unusual cool announcement ;)
Interesting and well written post.
Considering how you got to CodeForces and achieved so much here, I just thought you are the perfect person to ask this question:
Does the experience in competitive programming change you as a programmer?
It'll be awesome if you could explain why/why not! Thank you!
Well, I think the answer here might be unclear a bit but here it goes. Yes, I think this experience changed me as a programmer, there is no way it won't affect me taking into account the total time I spent on this site solving problems and learning new algorithms and data structures. But the practical outcome of this change is not that huge, might be not even noticeable to other people. In result if you look from practical point of view only then all I got is 5-10 T-shirts and some better chances on Google interview. I have never had a job which require algorithms/data structures skills, at least not of orange/violet level. I also became a bit better in some other programming areas, like debugging things in mind for example, this is helpful when doing code review. But all of these in total is not that much taking the time into account again.
So I would say it's a bit different, my only point of doing this was always the fun. I was always a fan of similar problem-solving sites since my high-school years. I started on sql-ex where you can solve similar problems in SQL, then I moved to project euler with its focus on maths, now I'm here. I would say that I'm here because I am already the way I am, so this site cannot change me much, neither as a person nor as a programmer.
My opinion is that this site for me is for fun only, if you want to learn data structures or algorithms or become better in any other programming area then there other more effective ways of doing that, at least unless you're looking for some red-level skills.
Oh, and I have just remembered one more thing where this site changed me as a programmer. After spending an year on this site I became completely bored on my job, so now I'm unemployed for the third month so far. Even though I receive around 15-20 propositions on LinkedIn per month, I'm not interested in those, so I stay here. Stay aware of this path!
Hope this helps and doesn't sound too depressing :-) Marat.
Thank you very much for your reply, Marat! I really appreciate that!
It's really interesting to know programmer's perspective on competitive programming, since I'm a math major and I only write code for online judge.
Too bad you are unemployed. I hope you'll find job you love soon!
Hue hue hue I feel like my path of going to study physics and keeping programming only competitive and only hobby is a total win, now.
I might still try programming-related work to get moar varied skillz, but I can't imagine sticking with it for long.
According to your performance I thought you are a student who's started training harder lately to get to IOI/ICPC. And now it looks pretty inspiring that you find time for all these trainings and contests at your age. orz
Recently I don't take part in div2 rounds, but going to do in yours. Good luck!
Longest welcome not ever :)
Hi, please could you confirm that the solutions will work with both Java 7 and Java 8? Because many solutions in contest 267 that used Java 7 got a MLE but passed with Java 8. I think that is a bit unfair. Looking forward to participate! (if I can)
Most intresting post that I ever seen :D
Special thanks to marat.snowbear ...
I think it will be good contest for us.... thanks to marat.snowbear.... GOOD CONTEST!!!)))
Yes it was really good contest=)
5000 contestants have registered!!
EDIT: The final number is 5093. Hasn't this broken all existing records on Codeforces?
I'm just worry about system test queue
How did you know???
I don't know =)
How to solve D ?
Form two arrays of difference between height of current tower and the previous one. Now search small array (elephant's towers) in the big one (bears' towers) like a substring in text. Special case to consider is that if w = 1.
For special case w = 1, output n.
Now observe that we can take the differences of consecutive elements, so searching for elephants is essentially finding the difference-elephant in the difference-wall. For example, if the wall is [3, 4, 5, 6, 1, 2, 3] and the elephant is [2, 3, 4], we can compute that the difference-wall is [1, 1, 1, - 5, 1, 1] and the difference-elephant is [1, 1], so there are three such occurrences. Indeed, the elephant appears on subsequence a1, a2, a3 (after raising by 1 to [3, 4, 5]), on subsequence a2, a3, a4 (after raising by 2 to [4, 5, 6]), and on subsequence a5, a6, a7 (after lowering by 1 to [1, 2, 3]).
Now this is essentially searching substring in a string, only with large alphabet (which doesn't matter). We use Knuth-Morris-Pratt algorithm or something like that to find them in O(n + w) time instead of O(nw).
Thank you very much ! I got it.
The difference-wall should be [1, 1, 1, -5, 1, 1]?
Ah yes, I can't count. I'll edit it later.
I think it can be solved taking the diferences between walls and then string matching(kmp for example) but I got wrong answer on pretest 2.
You didn't handle the case when W=1, did you?
No I did not,my mistake :).
first is Hack.Me last is yasinkkaya
and Hack.Me just registered 2 hours ago :(
How can you know ? Maybe Hack.Me wrong on Test 171 ? And my opponent is worse
I have came up to solution of problem D ib five minutes. Today we had a control test on a programming lesson and I had to write a z-function. I just copypasted a code and sent it. TL 4. After some time I improved my code and it got "past pretests". There were a mistake in a code of z-function which I wrote during the lesson. It seems, that mark won't be perfect:D
Is it to match the difference of the w with difference of the other string ?
+1 to problem setter. Awesome set. My Solution to A got hacked. Hope to see you again :)
What is the hack case for A , my soln is like this
1 1 2 2 3 3
your answer probably bear but real answer is alien
lets say input is 2 2 3 3 4 4.ans is alien.
1 1 2 2 3 3: You say bear, expected alien.
1 1 1 1 1 2: You say elephant, expected bear.
1 1 1 2 2 2: You say elephant, expected alien.
Still some way to go.
your solution will fail if input is 2 2 3 3 4 4 Answer should be Alien and not Bear
Solved A in 13 min. Boring screencast (locale: ru; lang: Perl).
How to solve C?
You can look my solution http://pastebin.com/V3jPNSjK
Let's denote by Hi = the minimum number of card which should be available in order to build a castle of height i. We may find the exact formula, or calculate this number inductively (Hi = H(i-1) + 3i-1). Having this formula, we realize that the maximum height a castle can have is around sqrt(n). So we can iterate through all possible heights. In order to check whether or not we may build a castle of height i with exactly n sticks, we have 2 conditions:
1) n >= Hi 2) (n-Hi) is divisible by 3
For a floor with a rooms in it, there are b cards in it, that:
b = 2a + (a - 1) = 3a - 1
So, if we can build n cards into a house with k floors, following statement will take place:
n = 3x - k, k + n = 3x
where x is sum of k different summands. It can always be written as x = 1 + 2 + 3 + ... + (k - 1) + y, where y is some integer greater than (k - 1)
When we know it, we can write solution: 7970170
Observe that the number of cards in a floor is 2k + (k - 1) = 3k - 1 where k is the number of houses there. Thus the number of cards used will be . In other words, the number of floors and the value of n must add up to a multiple of 3 (namely ).
Let there be f floors. Since we don't care about the number of houses on each floor, only that higher floors have less houses than lower floors, we might as well set the highest floor to have 1 house, the second highest 2, and so on until the second lowest, and put the rest of the houses at the bottom. In order for this to work, we want (3·1 - 1) + (3·2 - 1) + ... + (3·f - 1) ≤ n.
Now we can use a simple algorithm or a more difficult algorithm.
The first algorithm is simply to loop over the number of floors from 1. Note that is quadratic on f, so this has an upper bound somewhere around , quick enough for the constraints. As long as minH = (3·1 - 1) + (3·2 - 1) + ... + (3·f - 1) ≤ n, we check if ; in that case, increment the result, as f is a possible answer.
Using the example, n = 13:
The second algorithm relies on another observation. Note that we want to find the highest value of f where . We manipulate this algebraically:
3f2 + f ≤ 2n
(6f + 1)2 = 36f2 + 12f + 1 ≤ 24n + 1
Thus, if we can make the square root with sufficient precision, we can compute the largest integer value of f; simply do .
Now, if , we count the floors 1, 4, 7, .... If , we count the floors 2, 5, 8, .... If , we count the floors 3, 6, 9, .... So if we add to the floors, we always end up counting the floors 3, 6, 9, ..., which is simply . So given this, the final result is simply .
(EDIT: Codeforces is under heavy load ok. Why doesn't
E was harder than usual. Anyway, I liked the round and its heroes. A and B were about coding a simple idea in the simplest way while C and D required some creativity and I liked them both.
Yeah, I underestimated E, my fault. Could have a problem for D for the first div :-)
How to solve it?
DSU + sweep line + one optimization to make it fast enough, would you mind waiting for the tutorial? I'll publish it a bit later today.
Thanks, I just thought that maybe you have some tricky solution which is easy to implement and to describe:)
Available here editorial is
Is this a valid solution to E? 1. Making graph.. 2. Dividing it onto connected components 3. Negating all the weights of edges and finding MST for every connected component(Kruskal) 4. Find the maximum of the weights in that MST 5. Answer is sum of all edges-4.
Looks like you have n^2 vertices in your graph (if each vertical line intersects with each horizontal)...
Or your first part of solution is really hard to do.
Well yeah, didn't noticed that. Maybe something could be done to merge intersecting segments but doubt, even if it could be done it overflows my coding skill. Thanks anyway
Very Nice problem , Its really SAD when you get the idea of D at last 5 minutes , and nothing to do but stare at the problem statement because there is no TIME to code .
and even More painful , seeing your idea was correct in the forum -_-
It's even sadder when you use a wrong formula for Problem C and realize the correct one when don't have enough time to correct it:(
It's even sadder when you haven't solved even B because you forgot to put "YES\n" into your answer...
that should give WA in the first case !!
Yes, and I couldn't understand what is wrong it all the remained 1,5 hours. C was too difficult for me, so I haven't even tried to solve it. So it's my destiny to be gray, as it seems :)
You have to be really new here if you consider such experience as very painful ;).
need more experience to adapt with this pain.
Please put + to my comment i have many — please help me
contribution is not needed
How to solve B?
At first, sort the input array. You just need to permute the array 3 times that the three permutation is same. If it is possible(if two or more pair have the same value or any of three or more numbers are same) then print the value of index by their permutation, for example see the discussion which is written below the problem statement.Hope it will help. =D
great thanks 4 test with
w = 1in pretests in problem d
What a Interesting problem >> A :)
Hey, I don't understand why during judging my solution.. two of the solutions which passed pretests were skipped. As a result of which, my submissions show that I have solved only a single problem..?
Can some one please explain why this happened to me..?
I don't want to be jerk but it seems like that you cheated. Style of coding is really different, so I think that someone gave you code, which would be skipped as it in your case.
It's realy sad if you submit problem B and WA after system testing :(
For what ???!!
FOR (i, 1, n+1) must be changed to FOR (i, 1, 2001)
I'm so sad now :(
How can this solution pass?! http://codeforces.com/contest/471/submission/7966960
Haha, ok, I see. I got this beatiful macro in my template :). I see no reason not to use it and many to use it :P.
OMG I didn't notice lol :D
What is your problem here? It looks ok.
"worse didn't take part in today's contest so the fight was tough on both sides of the table" :D
Does anybody know how to TL this solution — 7969881? Seems to be O(N^2), at least if find is linear, but seems to pass the tests by time.
This solution running more then 3 seconds on this test on my pc.
But the solution running less 2 seconds on codeforces...
It doesn't on CF though :-) Checked in Polygon — it takes 1934 ms. Have you tried running the same test but with ones instead of 1^9? It is there in tests (fourth test) and took 1668 ms in his submission.
This was my first CF contest and the problem set was VERY enjoyable. Nice mix of "easy implementation", "little harder implementation" and "thinking" problems.
Even though I missed the "easy implementation" problem A. :-)
Well done by first-time problem setter. Thank you.
I'd appreciate a nice answer. Can You please explain what's the point in making div.2 A task something with "corner" cases and things that you should think about? Shouldn't that be a task that is really straightforward, and tbh on this competition D was much more straightforward than A? Thanks in advance, enjoyed the contest. :-)
What do you think is a corner case in A?
Eh,maybe said it wrong, but again it's kinda not that easy/straightforward. Just my opinion, saw a lot purple/blue coders getting wa on it.
I got WA for my submission of B in the 7'th test case(for 2000 integers), but I am unable to view the full test case.
How can I get the full test case?
Submission here 7969957
There is no way for you to see the full test. 7th test is simply 2000 random numbers. Maybe it's not the bug that failed your solution here but you seem to have an overflow when counting the number of possible permutations. You're multiplying them and they can easily become negative.
Problem is in this cycle:
perm_no can be easily as big as 21000. This does not fit in 64-bit integer type. But you can break from cycle, when
perm_no >= 3:
This change makes solution AC: 7976891.
Kaban-5 thanks :)
I'm Purple :o I'm not ready for Div1 yet...
What to do??
Create another fake account
Only one person can solve problem E