shashank21j's blog

By shashank21j, history, 9 years ago, In English

Hello coders

Good luck to the qualified teams. And those who are not qualified can still participate in unofficial rankings.
World Cup Finals begins in a few hours at 16:00 UTC 26 September and will go on for 6 hours.

It's going to be a very interesting and difficult contest. You can participate in a team of upto 3 members.
There are no ratings for this contest.

GL&HF

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

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

It's weird to change scoring system during the contest (especially at the end of it). We specially didn't write wrong solutions because we knew that we won't get any partial scoring for that. And it turned out that people who did got them. If I'm not mistaken we would end up in top 3 if the scoring was binary

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

Editorial of problem Bear and Safe is undetailed and unclear. I wonder does anyone read these editorials before publishing them? It seems like a very important job, but in fact nobody cares.

Also, I have recently seen in discussions of this problem that you removed the solution of one team from the leaderboard because it was not the intended solution. Really guys??? I think it is obvious that you must make strong tests, and if you fail in it, it's your problem, not participant's.

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

    Is it real? As I know, it's not a theorical contest, WTF is the "intended solution"?

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

    I have always thought that in real programming competitions you should care about correctness of your solution, not about how much setter/admin will like it.

    Now I am curious: shashank21j, do you at least have test case which makes this solution give wrong answer? Taking into account the fact that you didn't remove that AC short time after contest, but it was still there several hours later — it seems that you either struggled with finding such test case or for some reason you decision changed some time after contest. It looks like a complete fail anyway — in case you have such test, setter failed to prepare problems with good test cases (taking into account the fact that contestants had feedback only on pretests — it makes squeezing wrong solutions harder), otherwise you simply banned a team with probably correct (or maybe wrong not nore than using hashes without additional checking is wrong) solution, because you don't like it.

    Now I am afraid that next time you'll ban people for using Rabin-Vazirani? :) Or maybe some solution for problem about strings will be banned because it uses hashes and collisions are possible?..

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

      I also wonder what would happen if there scoring was partial:) Would it be just zeroed?

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

        Maybe something like partial scoring over partial scoring? :)

        "This solution is a bit similar to intended one, let's multiply score by 0.2 here. And this one is quite close, we believe we can give it 90% of points it scores".

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

      Greens cannot into judging the contest, that's all.

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

        In fact, there were 4 problem authors who contributed to this contest. I am curious was their opinion considered while making decisions about the contest.

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

          Every one was consulted. And had a mutual agreement.

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

            Then they just didn't care, I suppose. Every person who has a long experience in programming contests would say that the exclusion of the submission because authors suggest it is wrong is a very, very, very bad decision.

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

              Please don't feel bad. They are back on leaderboard because yes there is no counter testcase to break their solution.

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

                Even if it was, you mustn't exclude the submission. It is unfair to that team, because there might be other wrong solutions which you didn't notice, and consequently didn't try to make a countertest for them. In fact, there was a long discussion about it on codeforces some time ago, when Jacob's solution at one of the rounds was in such situation.

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

                  for that challenge only 1 team got correct code, so there's no one else got un-noticed.

                  And sure i agree it should be left on testcases to decide who get AC and who doesn't so it shall not happen again unless specified in challenge itself.

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

            Please tell who exactly was consulted. I wanna know whose contests must be ignored in the future.

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

              Information about problem setters is public — this particular problem was prepared by Errichto, and 3 other problems — by adamant, zemen and malcolm. I am also waiting for some comments from their side :)

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

                adamant says he was not asked about the exclusion of that submission. I think we are waiting for Errichto comment about this situation.

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

      I'm sorry but we had to be fair to the best teams. And I hope you use this thread to discuss challenges and solutions. Because it's not going anywhere like this.

      Every effort will be towards making contest as objective as possible. And as fair as possible.

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

        The best teams are those who passed all tests on the most of the problems. It is the foundation of the programming contests. The problem is Errichto's weak tests, not the incorrect solution, which passes them. Your strange desire "to be fair to the best teams" will lead to the decrease of people who solves Hackerrank contests, because now people will not be sure that their solution will be accepted, if it passes all tests.

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

About the problems — they were quite interesting, thanks to the authors. But I'd prefer to have a 100-points problem also, because of the large gap in difficulty between the first and the other three.

And I hope that the organizers will take into account our comments to make future contests on Hackerrank better.

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

I also have a proposal about the partial scoring system: why not to make groups of tests, like on codechef? Otherwise these contests can turn into some kind of lottery. For example, in the semifinals our completely wrong solution on 5th problem got WA only on 5 tests among about 50, and got OK on all tests with n ≤ 200. If we finally hadn't solved that problem, it could have been unfair to participants who got correct solution with a small bug, which received less points than our.

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

I am setter for Bear and Safe. I can prove their solution is wrong — with stress testing I'm able to find countertest. And I did find a countertest. But they have srand(time(NULL)) in their code and without putting thousands of tests I'm not likely to make them to have WA. And result (AC/WA) could change with rejudge.

During a contest I read their code and I knew I couldn't fail them. Usually (e.g. on CF) it means AC but apparently Hackerrank considers different strategy — to fail all clearly wrong (like: I submit random code till it passes) programs. I was asked about opinion on this proposal and I stated it (if anyone wants to know my opinion, write me PM). Minutes later after some talk (and I guess other guys expressed their feelings about it) I agreed for removing Corei13's program. So you can blame me not less than anyone else. I'm open for discussions here and you can insult me by PM.

I wouldn't agree with doing anything against e.g. good solution with hashing — you choose random base/multiplier, do something and you have 1e-6 chance for failing. Then sure, you have AC. Here we have random solution which is easy to fail with stresstesting but very hard to fail without putting maaany tests and thus making judging very long (days?).

Someone used words "weak tests". Yes, they didn't fail incorrect program but I doubt it's possible to fail such programs for sure (or for 99%) with fewer than 100 tests. Now some serious question: what can setter do then? What should he do?

Kostroma, I will polish/change editorial tomorrow. Sorry!

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

    If you give such problem on programming contest, I think you should be aware of risks of incorrect solutions, and if it is impossible to fail them on 100 tests — then you have nothing to do. If you understand that your problem has some random hard-to-fail solution, then it's your choice to give it to the contest or not. If you haven't thought about it before — oh, bad luck, but trying to fail particular participant's solution isn't in the spirit of programming competitions. That's my opinion.

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

      Your main point is "trying to fail particular participant's solution isn't in the spirit of programming competitions". I agree it's not part of programming competitions nowadays ('cause rules are: pass all tests to get AC) but it is some alternative, isn't it? Wouldn't we want only correct solutions passing in the perfect world? Personally, I would prefer such system but ofc. it's not our topic here and it's impossible. And I think there was discussion about it under Petr's blog where he has mentioned issues with my problem on recent CF round (btw. then I fucked up).

      I hope we agree that possible(?) hackerrank's approach makes some sense. Though maybe it's bad or terrible.

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

        But if you require total correctness, probabilistic solutions involving hashing are going to show up again. You mentioned that you were fine with these types of solution if they had a relatively small error margin (e.g. 1e-6). The fact that you could find failing cases on the Bear-and-Safe-solution suggests that it has a much larger error margin, but where are you going to draw the line? What probability values are 'allowed'? And how are you going to justifiably assign error probabilities to solutions? Or is it because hashing is a commonplace technique, whereas the Bear-and-Safe-solution (I'm guessing here) was a heuristical method?

        All in all, this seems more about trying to draw a line somewhere, and from the minor uproar it seems that the HackerRank team and the people here on CodeForces draw the line differently.

        I personally think that the line 'the testcases made before the contest are all the solution is tested on' is the best, since it's clear cut and unambiguous. When you start talking about 'this solution will pass with probability X', or stresstesting particular solutions, you're moving into some very vague territoriy.

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

    I have a simple way to prevent the kind of shit that went on here: a rule that all submitted programs should be deterministic — should produce the same output at any run with the same input. Seriously, what prevents people from using srand(randomly hitting the numpad) instead of srand(time(0))? (apart from not having a numpad, of course...) Or if there's a possibility of bad random solutions passing with luck, then just banning randomness, possibly for the specific problem. Sure, it's a bit weird, but it'd probably do what it's supposed to.

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

      By the way I think that I seen rules like this in some ACM contests (Judge can run user's submissions as much time as possible and choose the worst result). It seems to be good solution.

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

        And then you get solutions using hashing that pass with some bases and fail with the others after an hour or night of stress-testing. Doesn't sound too fair.

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

          Hashes are bad. There simply shouldn't be a problems with intended solutions based on them.

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

            That is a personal choice, but ok, let's assume..

            What about primality tests, Miller-Rabin and so on?

            What about algorithms such as creating a route of a chess knight on a board?

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

              Well, yes. Personally I strongly dislike probabilistic algorithms and problems that involve them at all. But maybe some of them are acceptable (for example ones where probability of failing user's solution is kinda 2 - 256, so it is kinda impossible to fail it even after years of stress).

              But you're right, this is just my opinion.

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

      You can still write your own RNG(or copy-paste mersenne twister) + use input for seeding, this approach will only increase the length of code template.

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

        The point is that if you use the input for seeding, it'll be deterministic: it won't change when retesting and if there's a test that can break it, that test will break it all the time.

        And the second version eliminates even that.