radoslav11's blog

Invitation to CodeChef April Cook-Off 2021
By radoslav11, history, 4 years ago, In English

We invite you to participate in CodeChef’s April Cook-Off, this Sunday, 18th April.

Time: 9:30 PM — 12:30 AM IST. Please note the change in contest duration.

The April Cook-Off is going to have Amazon as the official contest recruiter! Amazon is hiring for Software Development Engineer 1, Software Development Engineer 2, and Support Engineer roles for its fast-paced environment.

Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.

Joining us on the problem setting panel are:

Prizes:

The winners will receive CodeChef laddus with which they can claim cool CodeChef goodies. Know more here.

The video editorials of the problems will be available on our YouTube channel as soon as the contest ends. Subscribe to get notifications about our new editorials.

Good Luck! Hope to see you participating!! Happy Programming!!

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

Comments Comments (31)
| Write comment?
»
4 years ago, # |
  Vote: I like it -52 Vote: I do not like it

Google kick start and cook-off timings are matching , please change the cook-off time if you can, both are important for me , because through cook-off Amazon is hiring.

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

    Kickstart starts 4 hours after cook-off ends

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

    On kickstart schedule page, turn on the switch that reads,

    'Display in local time'

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

How can someone be Problem setter?

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

As a problem setter, I want some contribution.

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

    Give me one moment where a Tester have said that the problems are not at all interesting. As it seems that by default all problems and all contests are interesting.

    The definition of interesting may vary though and it can't be generalized.

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

      If a problem isn't interesting, it has less chances to appear in a rated contest.

      However, I agree with you that interesting is a subjective term and may differ from person to person. What I meant to say was that I found most of the problems interesting.

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

      If a tester thinks that the problems aren't interesting, they usually don't comment "As a tester, the problems are garbage."

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

        But they should if they are a real tester . But Guts are needed for that!

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

    As a problem setter...

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

    They were quite interesting indeed. :)

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

Reminder — the contest starts in less than 15 minutes.

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

Long queue again :( anyone else with the same issue?

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

Why ques are sorted in some contests and aren't sorted in some contests? This is really confusing. radoslav11

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

Did I cheese VALET by coding O(N*max(T)) solution or is that intended?

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

    Intended was $$$O(nlog(n) + Tmax^2)$$$

    While creating tests I tried to fail these solutions, the fastest O(NT) soln took more than 1.5 seconds so I thought maybe we were safe, still 1-2 O(NT) solutions passed, I'm sorry about this :(

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

      I see XD. Straightforward O(N*max(T)) seems to pass within TL without any pragma shenanigans if you only do basic operations. (tho took me 7 tries to fully optimize...)

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

      But still is this problem worth "Div1 only"? I personally think that this problem is quite easy in terms of logic.

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

I think SANITIZE is relatively easy but seldom people try it during contest.

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

    Yes, this problem was intended to be easier than both VALET and ARRAYOPS. But surprisingly, it got only 3 submissions in Division 1. Maybe people didn't even try it seeing the less number of solves.

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

      I think a lot of people did see that simple solution that we need two queryies foreach point. But the most of them cannot or are not willing to write down that formular stuff needed to acutually calculate the coordinates.

      In that sense the story of the problem was a bad one. Because you could have also written: Read 2N point IDs and the distances to 2N lines from stdin, calculate the points.

      You would had got the same small number of submissions.

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

        What? Of course, intersecting lines is not the hard part of the solution. You probably don't understand the problem. You can't choose the point you query.

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

          You get the points ID as an answer to the queryies, and whenever we got an ID two times we can calculate the point with that ID.

          So why the story, why interactive? Instead just give answers to the queries as input. This whole story is a pseudo problem, because the real one is to write down the formulars correctly, nothing more.

          But that formular part is fairly hard, compared to the simple insight we need to see that we need two not parallel lines to construct a crossing point of them.

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

            Well if you consider solving 2x2 matrix equation part hard you probably need to work on your arithmetic skill first....

            I did read the problem during the contest but I couldn't immediately come up with how to get rid of the "interactive" part of the problem, and I did not give more thought during contest because of low # of solves.

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

            I don't agree with you that obtaining formulas and solving simultaneous linear equations in two variables was the hard part. The hard part of the problem was to make sure that no two lines are parallel by taking suitable values of A and B and to simplify the absolute value part in the formula by taking suitable values of A, B and C. And to test these parts, the problem was made interactive.

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

This is just my opinion, no hatred. I found that the difficulty of problems was not evenly distributed, like for div2, C and D had a huge level difference. Also I didn't like the problems this time.

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

    C wasn't easy ( medium i would say ) but a doable constructive problem in my opinion. But I agree with you that the contest wasnt easy as in I expected much more solves for D ( since it's a div2 ) but to my surprise only 5 solved :0 , and I disagree completely with the fact that they gave an "Easy" tag to C.

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

how to solve GCD SUMS problem?

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

    That's just an overview of the whole solution: We will have a $$$O(n (\log n + \log C) \log C)$$$ precompute (actually it's less than that, because the final $$$\log C$$$ comes from computing the GCD) and we'll answer queries in $$$O(1)$$$ after that.

    Consider an arbitrary query $$$(L, R)$$$. Then if we have done some divide and conquer, there would have been a unique position $$$M$$$, such that in the DnC we split at it and $$$L$$$ was in the left subinterval, while $$$R$$$ was in the right subinterval. Then, we can split our answer as $$$f(L, R) = f(L, M) + f(M+1, R) +$$$ contribution_merge. The first two terms can be precomputed during the divide and conquer and after that, the merge can be easily done in $$$O(log^2 C)$$$ per query as for every position we will only care about $$$O(\log C)$$$ different GCDs. This is still too slow, so we need to realise that all merges for some fixed $$$M$$$ are very similar. Hence, we can do a 2D partial sums precompute in every DnC node. The complexity of the precompute would be $$$O(\min(M-L, \log C) * \min(R-M, \log C))$$$, which we can prove is $$$O(n \log C)$$$.

    Unfortunately during the contest, some people were able to optimise their $$$O(\log^2 n)$$$ solutions, but I still think the intended solution is pretty fun.

    → Reply