hmehta's blog

Topcoder SRM 732
By hmehta, history, 7 years ago, In English

Topcoder SRM 732 is scheduled to start at 21:00 UTC -4 on Thursday, March 29, 2018.

Featured Problem Writer: ltdtl

You will be able to register for the SRM in the Arena or Applet 4 hours prior to the start of the match. Registration closes 5 minutes before the match begins, so make sure that you are all ready to go.

Don’t know how to compete in Topcoder SRMs?

Check out this guide to know how to compete in an SRM.

You can compete using:

  • Topcoder Web Arena(Beta) — Please watch this video for step by step guide.

  • Topcoder Java Applet — You can refer to this guide here to set up the applet. (Note that those who have Java 8 installed on their machine will see a security issue — You will have to add Topcoder in security exceptions in Java Control Panel. Please refer to the details in the guide here)

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

Comments Comments (36)
| Write comment?
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Contest starts in 7 hours! gl&hf! :)

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

    Reminder: The contest starts in about 1.062 hours! Good luck and have fun!

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve Div 1 250?

→ Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it +11 Vote: I do not like it

    Better question: how do you solve any of the Div 1 problems...

    EDIT: Seems like I actually had the right idea on the 500 but for some reason TopCoder wouldn't run my code properly at the end... don't really know why.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 3   Vote: I like it +3 Vote: I do not like it

      Read EDIT first

      Not sure if that's correct (looks fine), but very tempting guess for optimal strategy for 250 is: 1) choose final color, 2) in every connected component of nonempty cells choose a cell that you will hit until whole connected components reaches final color. Implementation is kinda straightforward.

      EDIT: Lol, I just failed systests on 250, but passed 800 xD

      EDIT2: Yeah, this is fine, I just got a small bug :(.

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

        So share 800 then :) But for 250 mine passed and same idea.

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

    I found the same colored components and then constructed a bipartite graph where vertices represent components and edge is added between two components of different color if they have a cell each that is adjacent. I don't know how to proceed from there.

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Pick a square and keep flipping it. Do the best you can for each connected component and add up.

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the answer for div1 500 even fit into int?

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

    No. That's a huge issue. Not to mention it's far from original problem: link

    → Reply
  • »
    »
    7 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    No. They will re-grade hacks that don't fit into an int.

    Hopefully I get my points back...

    EDIT: I resubmitted my solution in a practice room, and it passed. Hopefully this means that I failed on an overflow challenge, and should get AC

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

      Btw how do you notify admins about such problems? There is no "request clarification" in the web arena.

      Fun fact: Swype offers anus when I type admins.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
        ← Rev. 3   Vote: I like it +15 Vote: I do not like it

        Swype, hm?

        Translation:

        <b> "Yeah, five roosters work"
        <b> "...five minutes work"
        <a> "Please don't use T9 when writing to me"
        <b> "Well I don't want to spend a week typing in each message"
        <a> "And then you write that you're lying in bed with your tractor" (tablet)
        <b> "And it's not T9, it's Swype"
        <a> "I don't care about the name of that text rapist, what matters is that I hate it"
        <b> "You just move your finger along the screen and 90% of the time it figures out what you want to cabbage"
        <a> "I noticed..."

        → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      This won't be a simple decision, to readjust the hacks after the match. There was identical situation in SRM 701 because of unexpected hacks, which met the constraints in d1 300 and decision was, that there will be no readjustments.

      Both decisions must be consistent. They already made a decision that this is not possible to readjust the hacks after the match, so theoretically the round will be just unrated and the hacks stay as is.

      Otherwise they should also rejudge hacks from SRM 701 and recalculate all the ratings.

      cgy4ever

      → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve 800?

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    What both players want to minimize is number of jumps through opponents (because that moves them by 2 cells instead of 1). They want to omit them as long as possible. Define balance of row as C[i] - w[i] - (b[i] - 1). Whenever first player must make jump in some row he chooses row with biggest balance, whenever second player must make jump, he chooses one with smallest balance (out of these rows where jumps are possible). Assume that b[i] = w[i] - 1 for simplicity. Then it boils down to greedy simulation according to rules of choosing row which I described. If b[i] = w[i] - 1 is not the case then we look at parity of difference w[i] - b[i] - 1. We can reduce this difference modulo 2. If it is even then we simply put balance into multiset of balances. Out of balances of rows where this was odd, we sort these balances and decrease by one first half and increase by one second half (this corresponds to choosing rows where there is exactly one empty cell between pawns, first players wants to make big balances even bigger and second player wants to make smaller balances even smaller). Then out of all these balances create a multiset (along with balances originating from "even" rows) and do greedy simulation described before.

    Don't ask me about the proof, but it intuitively seems like reasonable strategy to delay jumps as long as possible and reduce number of empty cells between pawns at start modulo 2.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Hacked! Also, self-hacked!

      800 has super weak tests. Look at my in-contest submission and count the number of bugs. It only fails on 1 or 2 full tests! After I fixed some stuff, but kept the same general idea, it passed systests, but I easily found some tests where it fails by stresstesting against other solutions and solving cases where the answers differ by hand. Here's my solution:

      • let's count the maximum number of rows where the 1st player can jump over the 2nd one so that it'd still be 1st player win, and denote it by q

      • sort the rows by decreasing balance; the 1st player can jump over in the first q (if it's worth it), the 2nd player in the last N - q - 1, and they fight over the jump in the remaining row

      • if jumping over in some row means player 1 can make more moves in this row than player 2, then player 1 makes this jump; add Ci - bi - 2 to sum1 and wi - 1 to sum2

      • otherwise, player 1 doesn't make this jump; add wi - bi - 1 to sum0

      • the same works for jumping decisions of player 2

      • player 1 has sum1 + (sum0%2) moves, player 2 has sum2 moves — if player 1 has strictly more moves, then player 2 can be forced to make N - q jumps and lose

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

        Can you provide a test where my solution fails along with explanation? Of course I believe you that my solution should fail, but I am just eager to see it.

        → Reply
        • »
          »
          »
          »
          »
          7 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it 
          3
4 3 4
1 1 2
2 3 4

bw..
b.w
.b.w

          Your solution says if the starting player is B, then B loses. B wants to make the 1st move in row 2 and force W to reach

          bw..
.bw.

          Now, B jumps over W in the first row, which forces W to jump over B in the 3rd row eventually. That gives B more moves.

          Btw, my solution fails on e.g.

          .b.w
.b.w
bw..

          If B makes the first move in row 1 or 2, my idea is broken by W's initial strategy "make a move in the other row", which lets W mirror B afterwards. If B makes the first move in row 3, W also makes one move in row 1 or 2 and one move in row 3, which eventually gives the same set of moves in a different order.

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

            Thanks, it is indeed a good hack for my solution.

            → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    This is the way I solved the PawnGame problem (I was a tester for this round). Let l[i] be the number of squares left of the black pawn, r[i] be the number of squares right of the white pawn and m[i] be the number of squares in between the pawns. It only ever makes sense for black to jump when l[i]<r[i], for white when l[i]>r[i] and for no-one when l[i]=r[i] (if someone is forced to do so otherwise he might as well give up). This also means we are never in a rush to jump (the other player will never take away that option). So the game will start with both players making moves toward each other until no such moves are possible anymore. When such a state is reached, it is trivial to determine the winner. The trick to this problem is determining in what rows the players should move in the first stage.

    I came to the solution by noticing that in the end the only thing that matters is in how many rows it will makes sense to jump for black (B) and in how many rows it makes sense to jump for white (W). Then the number of moves available for black will C-B and for white C-W, where C is some constant (not accounting for rows where l[i]=r[i], but those rows will decrease C for both players by the same amount). In other words, the goal of both players in the first part of the game is to get as many pawns as possible to 'the other half of the row'.

    When m[i]%2=0 a move by one of the players can always be countered by the other player, so for those rows it is already clear which of the pawns (if any) will get to the other side. A similar reasoning holds for when abs(l[i]-r[i])>=2. So the only interesting rows left are those in which m[i]%2=1 and either l[i]=r[i] or abs(l[i]-r[i])=1. In the first case always one of the pawns will reach the other half, so 'winning' this row relatively gains 2 points, while in the second case either the pawn that is ahead will reach to other half or the row will end in a draw (l[i]=r[i]) so 'winning' this row only gains 1 point.

    So the complete strategy for the first part is: If there is a row with m[i]%2=1 and l[i]=r[i], move in one of those rows. Otherwise if there is a rows with m[i]%2=1 and abs(l[i]-r[i])=1 move in one of those rows. Otherwise move in any row.

    Before reading this thread I did not know the problem also appeared in Winning Ways for Your Mathematical Plays, maybe I should read that book :). Note however that the strategy above corresponds with the table from the book in the spoiler below (when m[i]%2=0 all moves can be countered and when m[i]%2==1 the first option 'costs' only a star, the second option costs 'half a move' and the final option costs a full move).

    I think the problem is really interesting and has a beautiful non-intuitive solution. It is a shame that I didn't notice the test cases were so weak and that this (understandably) takes a lot of attention away from the beauty of the problem.

    → Reply
»
7 years ago, # |
  Vote: I like it +28 Vote: I do not like it

Wow, decided to write SRM after so long break to have some fun after work. And here it is... 500 and 800 and both like 10 lines of code, but 250 is implement sh*t lines w/o bugs? No surprise people chose Codeforces these days.

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

    What ruins it for me is having to wait a minute or two when opening a problem, entering the room, logging in, etc. Also that my quickly bashed together and untestable (see previous line) code for 800 only failed on one test — it should've failed on many more!

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

    Div1 250 is not actually "very implementing". I am not smart enough that I wrote 100-line code in the contest, but I re-implemented in the practice room and I only wrote about 50 lines. The code is in my submission on practice room. It's like a normal Div1 Easy, isn't it? (Though I think the max score should be 300)

    → Reply
»
7 years ago, # |
← Rev. 5   Vote: I like it +54 Vote: I do not like it

Are the testers too smart? Immune to nervousness? Do they fear being judged for saying the problem set is too hard? A year ago TopCoder was full of those nerve-wracking 250s, and I'd hoped they were gone for good. By the way, I really don't think this is the setter's fault. Like I said, this was too common an occurrence until relatively recently, so it's definitely systematic.

Yes, I know, I got a zero this time, but that's not the point. Think of the experience for blues, for example: A total of two blue coders got positive scores. Not only that, the vast majority of people got zero solved problems, even after trying hard for more than an hour. This was meant to be at least a bit fun, come on.

Edit: But at least I'll get to try reading Winning Ways again :)

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

    Are there testers?

    There, fixed it for you.

    → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    As a tester for this round I feel I have to say something. First let me start with apologizing for all the issues this round had. When you are a tester for a round you always try to do your best to do whatever you can to let the round go smoothly and to make the round fun for everyone. I clearly failed this time and for that I feel bad.

    Looking back at the round, there were a few things I should have done better. First, I knew that the easy was harder than usual. Because of that I did push for more samples with explanations, but what I now think I should have done is to make more noise and to try to make it the medium problem instead and ask for another easy problem. The point you make about the round also having to be fun for blue coders convinced me here. The round would be fine that way, I didn't really like the problem we ended up using as the medium anyway and the round would probably be more fun for a lot of people.

    Second, I should have done at least a quick look at the test cases. The system used for testing problems does not make it easy to do that, but some effort in this area should have prevented the extremely weak test cases of the hard problem.

    Third, I should have seen the overflow issue in the medium problem.

    Fourth, I was way off in my estimation of the difficulty of the medium problem; I expected it to be solved by something like 10-15 people. In my testing one of the first things I tried was when can you cut a 2*x piece 'for free' (without the other player getting anything in return), when a 3*x piece, when a 4*x piece, etc. which quickly leads to the correct pattern and then the code is really short. I agree it requires somewhat of a leap of faith, but playing with it some more on paper (or possibly stress-testing) should be convincing enough to code it I would have thought. Originally the medium and hard problems were swapped, but both I and the other tester found the PawnGame problem too hard for a medium and the BrownieGame problem doable (allthough not great) for the medium slot. It turns out we were right about the PawnGame problem (allthough two solutions passed, they only did so because of the weak test cases), but wrong for the BrownieGame problem. The thing I will take away from this is to be extremely cautious about allowing a problem that was posed for some slot to be used for a lower slot.

    Fifth, I should also try to google to see if the solutions to some problems are easy to find that way. Maybe I would have found Conway's book that way. Btw, I just tried it for the 250 and found this.

    The sixth and final thing is that I will ask to be able to start testing sooner. This time I was given access to the problems on monday evening and this was a bit too short for proper testing for me; if it is in a weekend I usually have some extra time but during weekdays combined with a full time job was less then ideal.

    Once again I apologize for the issues in this round and I will try to do better next time.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 7   Vote: I like it +10 Vote: I do not like it

      Hi krijgertje,

      First, no reason to feel bad! It wasn't the intention of my post at all. There was no accusation of malice. I appreciate the almost thankless job the testers do, and I wasn't trying to be snarky with the questions from the previous post. I really felt like the most likely reason for the issue was having a team of super high-rated coders testing problems in a stress-free environment. It's no wonder the likes of you and misof find many things easy that the rest of us don't.

      I also appreciate the detailed comments. With regards to the comments on the easy problem, I know well how hard it is to change things drastically instead of doing local changes to a work-in-progress, and I believe this is only solvable by having a process that makes such "gut feelings" easy to act on. Again, to be clear: I do believe this is a process problem. Maybe Codeforces' testing coordinator can chime in.

      I have some suggestions:

      1) A common theme with those nerve-wracking 250s I mentioned is that it's easy to get an idea that should work (and several that should but don't), but hard to actually prove it correct. At least for the easy problem, I am of the opinion that a proof should be doable in a reasonable amount of time. That is, relying on intuition only should not be required; people can skip proofs at their peril, but I believe the incentives are wrongly placed if it takes 5 minutes to get an idea and 45 minutes to have some confidence in it. So maybe proof sketches should be required of the testers as well and count towards the total solving time.

      2) While I appreciate that most trusted testers are high-rated coders, I think TopCoder would benefit from having a blue/low yellow coder test-solve the easy problem. This could help reach a target accepted percentage for the easy (50%? 60%? 70%? I don't know).

      3) Coming back to the "it's a process failure" theme, I think it's super easy to have peer effects drown out valuable feedback. If someone gets stuck on a problem, they might be embarrassed about it, or just think mentioning it is too much of a hassle, if they're the only one in that situation. Maybe some sort of anonymity in the testing process would help? Or bare statistics on how long it took each tester to solve it would provide enough data. I'm just guessing here.

      Also, I understand that problems sometimes change a lot during the preparation process, so it's easy to think a problem is now sufficiently easy when it's not. Again, I think this is a process issue. A naïve suggestion would be to have one tester not see a problem until it has been fully prepared by the other three, to get at least one unbiased opinion.

      (Personally, I don't think that the solution being on Winning Ways is a big issue, since almost every combinatorial game is in there. But if people think that's a problem, then "try googling really hard for half an hour" could be a part of the problem preparation checklist. Also, I think the overflow problem, while unfortunate, is one of those things that will always slip through the cracks every once in a while.)

      → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it -10 Vote: I do not like it

      Making easy problem a medium one would be a really bad choice. It was in my opinion easier to come up with solution than average TC's 250. The thing is, it just needed more code and samples as always were not very strong.

      But I have one question that is puzzling me pretty often. If medium was originally hard why was it worth just 500 pts? And why hard was worth 800 pts even though it was really tough (nobody solved it properly)? And why was easy worth 250 even though testers thought it is harder than usual 250? I think that given this information 300-650-1000 would be fine.

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

        Well, I just looked at the results of the last ten SRMs or so and in term of accepted solutions relative to the total number of participants, this was definitely one of the hardest (if not the hardest) in those rounds. It might have been easy for you to come up with a correct solution, but it is also pretty easy to come up with a wrong solution (for example always flipping the component with the largest degree or something like that). Also, even if you get the right idea, it might take you some time to convince yourself that it is actually the right idea.

        So I disagree with you and in hindsight I still think that for a lot of competitors (remember that you are one of the top competitors) the competition would have been more fun if this was the medium problem and there was an easier 250 instead. The samples were ok I think (two thirds of the solutions passing seems reasonable to me), allthough we could have added a non-trivial large (20*20) testcase.

        This time there was no discussion with the testers about the point values the problems should have, presumably because of the short time between the last comments relating to the content and the actual round. If there would have been I would have suggested something like 350-650-1000. I guess that the reason the hard was only given 800 is because it was originally proposed as a medium (not a good reason imho, but a reason anyway), but for the other problems I don't know.

        → Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Problems were not so hard, but sample tests were too weak.. It was really hard to get AC at once.

→ Reply
»
7 years ago, # |
  Vote: I like it +62 Vote: I do not like it

The answers to medium and hard one are page 26 and page 76 in Winning Ways for Your Mathematical Plays respectively.

Spoiler
→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I made a thread on TC forums summarising all fails in this round. I don't know where to write if I want it to be unrated, so I'm at least dropping it there and here. cgy4ever?

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

    1) I remember SRM where significant part of competitors (including me) couldn't log into arena during first ~20 minutes. This didn't cause SRM to be unrated. It seems that you were the only one to suffer connection problems (I don't say it's your fault, but problem is less severe and affecting smaller group)
    2) Weak testcases are always sad, but are never reason for competition to be unrated.
    3) Bad balance of difficulty or problems being googleable are never reson for competition to be unrated
    4) It seems that issue with answer not fitting into int affected competition just slightly and its consequences can be easily reverted.

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      The problems Xellos listed aren't actually the problem. The problem is TopCoder's attitude about the problems. There was reportedly a notification (in the applet, but not in the web arena), that the issue with challenges of 500 is being investigated. And since then there was no reaction whatsoever from TC. Compare it to MikeMirzayanov addressing the uproar after round 382, for instance. Note that I consider krijgertje to be commenting as himself and not on behalf of TC (if that's not the case, then I apologise).

      The difference between solving 500 and solving nothing in this contest can account for whopping 300 rating points. The rating itself is not the main reason we do CP, but I don't consider it so marginal that we can just nonchalantly ignore legitimate questions about the fairness of a particular round.

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it +41 Vote: I do not like it

        On behalf of Topcoder, I apologise for not coming up with a speedy answer to all the queries mentioned above. But have an update for the overflow issue — We are fixing the failed challenge scores. All the -25s will be adjusted and ratings will be updated within a day.

        Once again we are very sorry and trying our best so that all the things you all have mentioned above doesn't happen again.

        → Reply