MankiratAulakh's blog

Codejam round1B
By MankiratAulakh, history, 4 years ago, In English

Why it is so hard? Are they making this for grandmasters only?

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

Comments Comments (76)
| Write comment?
»
4 years ago, # |
  Vote: I like it +27 Vote: I do not like it

The round is not finished yet, please don't discuss difficulties.

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

Codejam Round 1B (Div. 1)

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

A problem is one of the worst problems I have ever seen.

Still I am not surprised to see my rank drop by more than 500 places in a matter of few minutes... it's like always...

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

    Do you mean problem A?

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

    .

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

      Said the guy who's been here for less than a year? You probably haven't seen many other worse problems.

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

        Shh... don't offer a different perspective here... you're breaking the echo chamber.

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

    I think A is not that bad, I wouldn't say I liked it, but it is far from the worst problem I've seen this week, let alone ever. I think the problem may rub many coders the wrong way because it is a clock problem and problems about clocks and calendars mostly suck, but if you look past that I don't think it is very bad. The solution was nice and clean with no dumb edge cases.

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

      The solution was clean (not so long as expected) but I don't think we got something to learn, just some basic modulo arithmetic and a lot of thinking behind implementation.

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

        I didn't need to think about implementation at all so I think you do have something to learn.

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

          Suspicious, that's what a telegram cheater would say XD.

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

            Is this your account? Username matches your name.

            Don't get me wrong but submissions of problem A matches line by line with the leaked submission as mentioned in this blog.

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    A problem is one of the worst problems I have ever seen.

    Offer your justification. It's not that bad in my opinion because all you need is two equations relating the hour, minute, and second hand positions. It requires a little bit of logical thinking which is what you would expect from a programming problem. I don't understand any of this hate.

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

learnt 2 things from today's contest-
1. practicing for 1 year has only given me useless ratings, I am still at the same level(0 problems completely solved in Codejam 1B 2020 and 2021)
2. what's the point in making problems if coders can solve them? — logic behind making the problemset

edit-learnt a 3rd thing today
the only things that worked more efficiently than coder's brains were telegram and whatsapp
1 2 3 4 5

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

    I feel the same bro...$$$;___;$$$.

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

    We are on the same page :(

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

    Most of them(cheaters) got themselves manually rejected(plag check) so that's a relief!

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

    I didn't even get the ratings T_T . The struggle continues into next year :(

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

Yeah 1A had easier problem 1 and previous 1B also had easier problem 1 this time its too hard

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

Why didn't they write "In case there are multiple correct answers, you may output any of them" to the output-section of problem 1??

I spent an hour thinking there must be only one correct solution, and trying to figure out why I do not have the same output as sample 2, before finally noticing that the fact that you may output any solution WAS HIDDEN IN THE SAMPLE EXPLANATION?

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

    Yeah, I got confused too because of the multiple answers. Also imo B was much easier than A.

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

    In problem A of the Qualification round they said the following:

    "If there are multiple solutions, you may output any one of them. (See "What if a test case has multiple correct solutions?" in the Competing section of the FAQ.) This information about multiple solutions will not be explicitly stated in the remainder of the 2021 contest. "

    The mentioned FAQ section also states the same thing. So technically they have resolved this question once and for all.

    But I agree that handling the issue in such a way is a bad idea and this should be mentioned in every problem where the question theoretically may arise.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -94 Vote: I do not like it

    You can't always expect to be spoon-fed the information you want.

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

      Isnt writing "multiple answers exits" in the output section a must have thing rather than a spoon-feeding ?

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it -32 Vote: I do not like it

        No, it never implies there can't be multiple solutions.

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

Bruteforcing my way through B2, and still can't explain how did it pass. Btw A is the wackest problem ever.

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

    Can you send the link to your solution , I checked all no. till 32 for the answer .

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

      Check till 1000 and your solution will get accepted.

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

      and I checked till 100 only. Don't know why they keep so high time limit also. How to judge limits by the time limit?

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

    Because after some time, your counts for every i that you can get begin to increase like fibonacci.

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

I need more practice :/

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

How to get editorials? If anyone got solutions please explain

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

Me after reading A

Spoiler
→ Reply
»
4 years ago, # |
  Vote: I like it +11 Vote: I do not like it

spent an hour to figure out why my solution for C gived RE while using local tester provides WA.

even caught RE in this solution

this solution

still don't know what the problem

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

    I had a problem because I read in $$$p$$$ as an int, not as a long long. Maybe it's the same for you, can't tell the type from just what you posted.

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

      int P... extra LOL, thanks

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

      How did you get the judge to give you the first value? The only code I could write that didn't TLE was when I output the position first. E.g this will TLE waiting for the judge to give a value.

      code
      → Reply
»
4 years ago, # |
  Vote: I like it -17 Vote: I do not like it

geometry sucks so I skip the first question(with rotation) and solve the other 2 questions instead.

For B we need to find a suitable bound for the answer. If it is too large than may TLE. By brute force we can know its 402.

For C, If there is a '9' then fill the top block. For second top digit if there is a >='8' then fill it. If there is no place for the top block then we need to fill the second digit with a lower value. I set it to >='7'. In my local environment it has some chance (I guess >20%?) so I Submit a few time and pass the second test case.

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

    1st didn't involve geometry. That single sentence with 'angle' did not matter

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

A was the worst. Wasted about an hour on C, and all ended up in TLE. In the end, solved B but it was too late. Missed by 77 ranks, bad day :(

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

Promotion is based on relative difficulty i.e. how well you do against other competitors. As long as the round offers differentiation (the problems are of varying difficulty, and the scoreboard isn't just a speedforces), it is fine since promotion is relative.

Complaining about things like problem quality is fine. Complaining about things like difficulty doesn't make sense. There were 1500 participants that solved more problems (or more quickly) than you. That wouldn't really have changed if the problems were easier, assuming differentiation still exists.

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

If this contest was on codeforces, it deserves something like 500 downvotes for its announcement blog.

A is totally boring code writing. B is just brute force, I even tried to ans = 10000 and still passed.

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

Problem A is quite possibly the worst CP problem ever.

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

    Definitely an exaggeration. The problem is not too bad once you relate the clock's hand movements with modular arithmetic by analyzing the fact that the hour minute moves 12 times as fast as the hour hand and the second hand moves 60 times as fast as the minute hand.

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

That was some really low-quality round (perhaps one of the worst GCJ I've ever seen), in my opinion.

  • P1 was just cumbersome modular arithmetic, with products of 64 bit numbers and a lot of eye-rolling;
  • P2 wouldve been a nice problem, but for the fact that $$$O(T \cdot MAX^2)$$$ boring solution passes without a problem; not to mention, probably a lot of people implemented it without proving that it works, just YOLO;
  • P3 was just atrocious.

I hope R1C/R2/R3 will be more decent.

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

    I mean, the easiest way to prove your code works in P2 is to write it and run it on all pairs $$$a, b$$$ with $$$U[1] = U[2] = \dots = U[20] = 20$$$, so I don't think there's anything wrong with implementing it without proof.

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

    Agree completely. The analysis for P2 was one of the strangest editorials I have ever read. As if they expected any participant to go through the computation to compute 402 as the EXACT bound they need to iterate up to and write it in their code, instead of just setting MAX = 10000 and sending it.

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

    I think it's a matter of taste. Personally, I would call this round quite enjoyable.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -30 Vote: I do not like it

    If you have to use products of 64 bit numbers which cannot be done in long long, it is your problem.

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

    I'm not sure what the justification for being anti-P3 is? I thought the problem is fine--the observation is fairly nice and pretty intuitive, and the implementation can be completed in a fairly clean way. In particular, both the accuracy and time bounds are not at all tight, allowing implementations that are not particularly well optimized but that are easier to write to pass. I can imagine that this problem was more frustrating for those who attempted greedy solutions rather than the intended DP, but by setting a 98\% accuracy bound on a problem where the efficient solution is very nearly tractable (about $$$3.25 \cdot 10^9$$$ states), I think the authors signaled pretty clearly that the solution would probably look like the intended DP combined with a heuristic that serves to reduce the search space.

    I also didn't find P1 as frustrating as some others did, but I should also note that multiplying numbers in a way that creates LL overflow is completely unnecessary. My solution involves dividing numbers by $$$11$$$ and $$$719$$$, modulo $$$360 \cdot 12 \cdot 10^{10}$$$, and computing the modular inverses and multiplying by them directly, as one would normally do in a modular arithmetic problem, would overflow. However, since $$$11$$$ and $$$719$$$ are fairly small numbers and the time constraints are not tight, it is sufficient to divide by $$$11$$$ by simply adding $$$360 \cdot 12 \cdot 10^{10}$$$ to our value until it is congruent to zero mod $$$11$$$. The resulting implementation is quite clean--aside from code reading the number of tests, my solution is only 24 lines, and it certainly isn't particularly optimized for length.

    (That said, as others have pointed out, P1 definitely should explicitly have stated in the output format that printing any valid answer is acceptable.)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -11 Vote: I do not like it

      Why am I downvoted while I says a subset of your idea?

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

My code in problem C has edit distance 0 to get AC. I just need to submit it again to get it, so frustrated...

→ Reply
»
4 years ago, # |
  Vote: I like it -60 Vote: I do not like it

I'm only candidate master and I managed to solve the first two problems and qualify with rank 646. They seemed impossible at first but I eventually found nice solutions for both of them:

Broken Clock

https://www.youtube.com/watch?v=21ADzj9dzz4

Subtransmutation

https://www.youtube.com/watch?v=p0YtxvbuRjI

I will admit that Broken Clock is harder than Subtransmutation, especially since ticks, and the hands movements aren't intuitive.

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it -43 Vote: I do not like it

Why it is so hard? Are they making this for grandmasters only?

I dunno, It seems I got successfully promoted to the next stage

As you may notice I'm not exactly a grandmaster...

But yes, it is as always with such events, a lot of reading and coding. Much less fun than from codeforces rounds

→ Reply
»
4 years ago, # |
  Vote: I like it -12 Vote: I do not like it

The results are in preview right now and the ranks are updating. My rank got increased by almost 500. This means that 500 people got caught in plagiarism check or is there something else I am missing out? TIA.

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

    Kinda sad that >500 people were cheating in the top 2500...

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

    I think so. I noticed the Broken Clock full solve percentage went from around 26% to 21% after the contest ended.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it -41 Vote: I do not like it

Funny thing

B has score 31
A has score 30

Unofficial cutoff is 31, so
31 is enough to pass to the next round (depending on timing though)
30 is not enough

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

Though I don't find this round hard, I don't find this round good. And you don't need to be grandmaster to solve 100: I'm candidate master and was able to solve everything and placed 104th with some strange feeling that I've 15 more minutes till the end of round and nothing to do. I struggled a lot with A, but both B and C have seemed very easy for me. If somehow anybody is interested in my solving of this round without any commentary: my screencast

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

Are they making this for grandmasters only?

spoiler
→ Reply
»
4 years ago, # |
  Vote: I like it -20 Vote: I do not like it

Personally I don't find the rounds hard. P1 was simply modulo arithmetic (N==s+t mod 360x12x10^9 or sth then subtract and everything is uniquely solved, rmb permutation) and P3 was greedy 9 which I guessed by taking a nap in-contest

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

After reading problems(Specially A), I was checking the announcement blog for downvote.

It was really bad.

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

I am not enough qualified to talk here. but why binary search failed in second test of B. I am binary searching over the answer for both the parities seperately. and my isitpossible function looks like this.

ISITPOSSIBLE function code
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Isitpossible is rarely monotonic (A = 1 is maybe the only case where you can easily say that it is). This is most obvious when A and B aren't coprime (checking separate parities isn't enough) but generally it also isn't when A and B are coprime, and it's not hard to come up with examples where one can see this on paper.

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

For anyone interested, here's a link to my screencast: https://youtu.be/zvV4sjS0fBU

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

I tried to upsolve A in python and faced this...

let's find the clock rotation angle for current permutation. I obtained the following formula (so we can test each permutation in O(1), idk why it's not mentioned in editorial):

x = (A * 12 - B) * inv % mod

where mod = 360 * 12 * 10 ** 10 and inv is an inverse of 11 for this mod. Naturally, I decided to precompute inv using the familiar code:

inv = pow(11, mod - 2, mod)

and guess what, this line gives an incorrect answer, apparently because of integer overflow. In python. Can someone clarify this? I would've freaked out if it was an actual contest...

→ Reply