IceKnight1093's blog

Invitation to CodeChef Starters 157 (Rated upto 5 stars) — 23th October
By IceKnight1093, 2 months ago, In English

We invite you to participate in CodeChef’s Starters 157, this Wednesday, 23th October, rated upto 5 stars (i.e. for users with rating < 2200).

Time: 8:00 PM — 10:00 PM IST

Joining us on the problem setting panel are:

Problem distribution:

  • Division $$$1$$$: $$$5$$$ problems
  • Division $$$2$$$: $$$6$$$ problems
  • Division $$$3$$$: $$$7$$$ problems, of which $$$1$$$ is a subtask
  • Division $$$4$$$: $$$8$$$ problems, of which $$$1$$$ is a subtask

Written editorials will be available for all on discuss.codechef.com. Pro users can find the editorials directly on the problem pages after the contest. The video editorials of the problems will be available only to Pro users.

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. Hope to see you participating.

Good luck!

Congrats to the top 5 in Div1!

  1. Egor
  2. maspy
  3. Kude
  4. liympanda
  5. noya2
  • Vote: I like it
  • +55
  • Vote: I do not like it

»
2 months ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Please mention the total number of problems division wise, like Dominater069 mentions in his blogs about codechef contest?

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Reminder: Contest starts in 30 minutes

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in normal is good. How to calculate the number of subarrays such that the frequency of 1 equals the frequency of 3 and there exists at least 2 in the subarray. I spent the entire contest trying to implement it but I wasn't able to.

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

    let $$$ai$$$ and $$$bi$$$ are cnt of 1 and 3 till index i respectively
    $$$ai - aj = bi - bj$$$
    $$$ai - bi = aj - bj$$$
    this trick is same as we use in two sum problem

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

    you can replace 1 -> -1 and 2 -> 0 and 3 -> 1, 

    1. count the number of subarrays having sum zero,
2. find the segments where there is no zero i.e the segments which contain only 1 and -1 and again calculate the number of subarrays with zero sum for these segments, and subtract this count from the total count.
3. you also have to count the subarrays with only -1 and only 1 and add this count to the answer.
    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    You can make a queue, which holds all the prefixes in that dont have a 2 in front of them, and then empty the queue into a map each time you see a 2

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Seriously I don 't see any reason why constraint on MEDIANT is so small like $$$N\le5000$$$ I mean seriously? There was clearly an easy $$$O(N)$$$ solution , I don't even know how a $$$O(N^2)$$$ solution would look like. Why such unnecessary small constraints??It nothing but created confusion

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

    I did it with an O(n^2) maybe he considered safeguarding idiots like me

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

    how would you check if solution is correct or not in $$$O(n)$$$.

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

      main observation is that if the minimum number is present after the last index of the maximum number then impossible

      if possible then no matter what subarrays you choose for operation you will find a sorted array in the end

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

        i know the solution
        i'm trying to say that constraints are lowered so that CHECKER can run in $$$O(N^2)$$$ or may be something better, but surely not in $$$O(n)$$$.

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it -47 Vote: I do not like it

          oh yeah you also have a point , if checker can't check in $$$O(N)$$$ then constraints have to be lowered for sure but again then it questions the fact whether the problem should exist at the first place.Because if a contestant has a straight-forward solution for larger constraints but checker can't afford that then it's not a proper problem to appear.You may ask why?Because as a contestant , when he approaches a problem constraints mean something to him , he can't think from a problem setter's viewpoint that constraints might have been lowered because of not being able to make a checker

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

            as a problemsetter I am telling you none of your sentences make sense

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

            I saw a problem. Due to my own reasons, i assumed it was dp. I failed to solve it. The editorial was greedy.

            Such a bad problem smh. Why didn't problemsetter tell me it is solved with greedy?

            Whether you think this problem is fine or not is a separate issue, but your argument is completely invalid. Constraints exist not to tell you that do this in O(N) but to deny solutions that run in O(N^3) for example. It is not to mislead you to a solution, rather to not give hints. If you do try to infer stuff from constraints, do it at your own risk

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

      Edit: Sorry my approach had flaws, we can't keep doing both identification of median and modification of array in logarithmic time complexity.

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

        we can identify and remove any element in O(log(n)) as per given output from user

        how will you identify and remove median in range $$$L..R$$$.

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

          oh sorry!! Since after removing any element the array is getting modified, we can't (at my level, maybe someone can) keep doing both operations at logarithmic time complexity. If the array was constant we could have identified median using kind of merge sort tree. I'm really Sorry for wasting your time.

          → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Editorial for A-D with detailed explanation

D WAS really an amazing Problem

Link : YOUTUBE LINK --Click here

→ Reply