marat.snowbear's blog

By marat.snowbear, 5 years ago, In English,

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.

Best regards,
Will see you at some next round,
Marat.

Round stats from DmitriyH
Editorial

 
 
 
 
  • Vote: I like it
  • +511
  • Vote: I do not like it

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

tourist has solved only 590 problems ?!

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +52 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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 good at it." (I have known it from wiki). So actually he was simply good even 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. :)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +33 Vote: I do not like it

      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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Where can I see the number of problems I have solved?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +13 Vote: I do not like it

        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:)

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          Well, that was an irony and there is always somebody who doesn't get it. It won't be an irony otherwise.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +2 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +18 Vote: I do not like it

            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

            • »
              »
              »
              »
              »
              »
              »
              5 years ago, # ^ |
                Vote: I like it +6 Vote: I do not like it

              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.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 years ago, # ^ |
                  Vote: I like it +9 Vote: I do not like it

                You tell me about permanent spamming in comments...

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
            Rev. 2   Vote: I like it +26 Vote: I do not like it

            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.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -9 Vote: I do not like it

    Please Ignore.

»
5 years ago, # |
  Vote: I like it +5 Vote: I do not like it

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~

»
5 years ago, # |
  Vote: I like it +94 Vote: I do not like it

It seems to be the longest CF Round announcing post I have ever seen.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +101 Vote: I do not like it

    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 :)

»
5 years ago, # |
Rev. 2   Vote: I like it -37 Vote: I do not like it

Википедия просила напомнить вам, что день, когда состоится этот раунд будет 269-м днем года.

Так вот почему раунд перенесли с четверга на пятницу.

»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

never into ACM/ICPC and stuff like that before
ME TOO
It Will Be A Great Inspiration For Me

»
5 years ago, # |
  Vote: I like it +39 Vote: I do not like it

What a great introduction! All the best for your first round marat.snowbear :)

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Impressive intro. I'm looking forward to your round

»
5 years ago, # |
  Vote: I like it +51 Vote: I do not like it

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 :)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +51 Vote: I do not like it

    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 ;-)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    So, how was the movie?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Glad to see a different announcement post for a change :-D.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

It seems, this is gonna be such an interesting round, but alas I'd be travelling.

»
5 years ago, # |
Rev. 2   Vote: I like it +14 Vote: I do not like it

Hope that the problem statements won't be long as the blog entry! :D

»
5 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

"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! :-)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    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 !!!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      I understood his line but you didn't understand mine.

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

hahaha funny intro for your Round, I guess I'll be having fun with problems' statements too. Won't miss this one.

»
5 years ago, # |
  Vote: I like it +9 Vote: I do not like it

such an unusual cool announcement ;)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Interesting and well written post.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

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!

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +34 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

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!

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Longest welcome not ever :)

»
5 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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)

»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

Most intresting post that I ever seen :D
Special thanks to marat.snowbear ...

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think it will be good contest for us.... thanks to marat.snowbear.... GOOD CONTEST!!!)))

»
5 years ago, # |
Rev. 2   Vote: I like it +6 Vote: I do not like it

5000 contestants have registered!!

EDIT: The final number is 5093. Hasn't this broken all existing records on Codeforces?

»
5 years ago, # |
  Vote: I like it -6 Vote: I do not like it

Contest ended))

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve D ?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +9 Vote: I do not like it

    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).

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You didn't handle the case when W=1, did you?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

first is Hack.Me last is yasinkkaya

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

+1 to problem setter. Awesome set. My Solution to A got hacked. Hope to see you again :)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How to solve C?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can look my solution http://pastebin.com/V3jPNSjK

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    5 years ago, # ^ |
    Rev. 3   Vote: I like it +5 Vote: I do not like it

    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

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +6 Vote: I do not like it

    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:

    • f = 1. We have minH = 2 ≤ 13 = n, so we check if ...nope, since .
    • f = 2. We have minH = 2 + 5 = 7 ≤ 13 = n, so we check if ...yes, it is, . So we increment the result.
    • f = 3. We have minH = 2 + 5 + 8 = 15 > 13 = n, so we don't have enough cards for three floors, much less for more floors. So we break out from the loop and return 1 as our count.

    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 \pmod exist?)

»
5 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Yeah, I underestimated E, my fault. Could have a problem for D for the first div :-)

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      How to solve it?

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +28 Vote: I do not like 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.

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 2   Vote: I like it +1 Vote: I do not like it

          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.

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 -_-

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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:(

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      It's even sadder when you haven't solved even B because you forgot to put "YES\n" into your answer...

      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        that should give WA in the first case !!

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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 :)

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          I thought the formula is 2^n-1..so it passed the first 2 test cases and gave WA for the 3rd test case.Seeing that, comes the realization..:P

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You have to be really new here if you consider such experience as very painful ;).

»
5 years ago, # |
  Vote: I like it -11 Vote: I do not like it

Please put + to my comment i have many — please help me

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve B?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

great thanks 4 test with w = 1 in pretests in problem d

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What a Interesting problem >> A :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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..?

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    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.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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 :(

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +21 Vote: I do not like it

    Because of

    #define int ll
    
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      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.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      OMG I didn't notice lol :D

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What is your problem here? It looks ok.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

"worse didn't take part in today's contest so the fight was tough on both sides of the table" :D

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    void create_test(){
    	cout << 200000 << ' ' << 100000 << endl;
    	for (int i = 0; i < 200000; ++i)
    		cout << 1000000000 << ' ';
    	for (int j = 0; j < 100000; ++j)
    		cout << 1000000000 << ' ';
    }
    

    This solution running more then 3 seconds on this test on my pc.

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But the solution running less 2 seconds on codeforces...

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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. :-)

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    What do you think is a corner case in A?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like 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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Problem is in this cycle:

    for(it = M.begin(); it != M.end(); it++)
    	{
    		VI v = it->S;
    		perm_no = perm_no*1LL*SZ(v);
    	}
    

    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:

    for(it = M.begin(); it != M.end(); it++)
    	{
    		VI v = it->S;
    		perm_no = perm_no*1LL*SZ(v);
                    if (perm_no >= 3)
                        break;
    	}
    

    This change makes solution AC: 7976891.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it
»
5 years ago, # |
  Vote: I like it -9 Vote: I do not like it

I'm Purple :o I'm not ready for Div1 yet...

What to do??

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Only one person can solve problem E

»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

pls ignore