Блог пользователя radoslav11

Автор radoslav11, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +56
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -52 Проголосовать: не нравится

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.

»
3 года назад, # |
  Проголосовать: нравится -14 Проголосовать: не нравится

How can someone be Problem setter?

»
3 года назад, # |
  Проголосовать: нравится +76 Проголосовать: не нравится

As a problem setter, I want some contribution.

Spoiler
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +9 Проголосовать: не нравится

      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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +22 Проголосовать: не нравится

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

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +15 Проголосовать: не нравится

    As a problem setter...

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    They were quite interesting indeed. :)

»
3 года назад, # |
  Проголосовать: нравится +28 Проголосовать: не нравится

Reminder — the contest starts in less than 15 minutes.

»
3 года назад, # |
  Проголосовать: нравится -37 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 3   Проголосовать: нравится +60 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -15 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    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.

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится -20 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +22 Проголосовать: не нравится

        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.

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится -26 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +22 Проголосовать: не нравится

            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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
              Проголосовать: нравится +27 Проголосовать: не нравится

            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.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

how to solve GCD SUMS problem?

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    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.