yash_daga's blog

Invitation to CodeChef Starters 138(Rated till 6-Stars) — 12th June
By yash_daga, history, 5 months ago, In English

We invite you to participate in CodeChef’s Starters138, this Wednesday, 12th June, rated for till 6-Stars(ie. for users with rating < 2500).

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

Joining us on the problem setting panel are:

Note: Some problems have subtasks

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!

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

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Has the contest admin changed ?

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

TheAbbie orz

→ Reply
»
5 months ago, # |
  Vote: I like it -6 Vote: I do not like it

Distinct Substring Video Editorial : YOUTUBE Video LInk --Click Here

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

    wth , it hasnt even ended yet

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

      No no....I have uploaded it 2-3 minutes before the end of contest... There was no chance of watching...understanding and implementing in just 2 -3 minutes... But still Sorry for that !

      → Reply
»
5 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Imagine ppl cheating in CodeChef Starters xD.

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

The balance feels off, with large gaps between the last four problems. Look at div 2 standings, there's an order of magnitude difference between them. The problems themselves are not bad but the difficulty curve is heavily frontloaded.

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

The clarification section of Codechef is the most useless thing. They never reply any queries that's been asked.

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

    They replied to me in a few minutes in previous contest.... I think they only reply to a doubt that is non trivial

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

      Non-Trivial is a biased statement. In codeforces, If someone asks a silly question, they often reply with "Read the Problem Statements Carefully" or they clearly clarify and answers the question that's been asked.

      My concern to this problem was in both suffix and prefix the "Equal" condition is being used. So, My concern was any array containing all the equal elements will have same AND and XOR for every indices and that clearly satisfies the question conditions. But I was getting WA. I needed [still need actually] a little clarification about that.

      Lastly, sorry for being rude as today, I am totally pissed off.

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

        "Read the Problem Statements Carefully"

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

        if we use same elements in array then at some point we got SUFFIX_XOR less then SUFFIX_AND to avoid this just put another number at end(like 3) eg. 7 7 7 7 PREFIX XOR-> 7 0 7 0 PREFIX AND-> 7 7 7 7 0 7 0 7 <- SUFFIX XOR 7 7 7 7 <- SUFFIX AND

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

          Thanks a lot, my friend. Highly appreciate ur explanation.

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

        1) you are not being rude (and nor am I trying to be rude in following arguments)

        2) that is indeed a silly doubt. (I am not trying to be rude, just brutally honest). The people will answer a doubt only when they feel that the doubt can genuinely not be cleared by the participant. In your case, you came up with a possible solution of all elements being equal, and it turned out to be wrong (because it gave WA). So what should your next step have been? Is it to directly raise the issue with problem setters? Here is what you should have done: Conduct a dry run of your test case. Solve for every step of what output is your solution giving and what is expected. You would have easily figured out that your solution fails for [the case which is stated in the comment below], and you need to cook a better solution. This is the normal problem solving procedure !! If the problem setter tells you the test case where your solutions fail, there is no point in even conducting the contest.

        The clarification section is present to clear any ambiguities in the question. It is not there to ask why your solution is failing or why this approach isn't working or anything else. That is something which we have to do ourselves. There are countless times where I was stuck on a problem because it failed some edge case, maybe on the last test case or something, but that didn't mean I would ask it as a clarification, because that is not what 'clarification' means.

        Knowing where your solution fails, finding edge cases, is a part of competitive programming and you should not seek help during contest for that.

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

        I will give you an example of a query that actually got answered in clarification (which was asked by me in previous contest). Because I really want to help you and others who don't understand, what is expected when someone asks a doubt in the section.

        In previous contest, I had a doubt in this question. The doubt was, regarding whether the the bomb can be placed at a non-integer position 'X'. It was a genuine doubt that wasn't written in the question, and it's answer being 'YES' or 'NO' could have changed the solution for a test case (actually it doesn't affect the answer either way, but whatever, I thought at that time it did, lol).

        Because there was no way I could have answered this doubt myself, I got a clarification about what the question meant, even though that clarification was absolutely useless, it didn't affect what the expected solution should be. Maybe on codeforces I would have got a reply like 'read the statement carefully or sth', but the point is, ignoring that it does not affect the answer, this is the type of doubt that I think are eligible to be asked on clarification section.

        → Reply
»
5 months ago, # |
  Vote: I like it +8 Vote: I do not like it

For this problem, here is a solution without divide and conquer. The main problem with $$$M$$$ not being prime is taking modulo inverse but since $$$M \leq 10^9$$$, $$$M$$$ can have at most $$$10$$$ distinct prime factors. So, we can deal with them separately.

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

    In my opinion, a simpler way is to use a segtree with the modular product as its operation to query the product of each length k subarray.

    mint ans = 0, sum_prod = 0;
for (int i = 0; i < n; ++i) {
  if (i >= k) {
    sum_prod -= seg.prod(i - k, i);
  }
  sum_prod *= a[i];
  sum_prod += a[i];
  ans += sum_prod;
}
cout << ans.val() << '\n';
    → Reply
  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    My solution don't hereneed all this . At each point just maintain the ans till k element before.

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

    Let us define $$$last[i]$$$ = $$$\prod_{j=i}^{i+k-1} A[j]$$$ , if $$$i + k < n$$$ , else $$$last[i] = 0$$$. Define $$$Ans[i]$$$ as the sum of product of elements of all good subarrays ( i.e. having $$$\le k$$$ elements ) with left endpoint as $$$i$$$. Then $$$Ans[i] = A[i] + {A[i] (Ans[i + 1]-last[i+1]) }$$$. You can compute $$$last[i]$$$ using sparse tables. The final answer is $$$\sum_{i=0}^{n-1}Ans[i]$$$

    → Reply
»
5 months ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Code

My solution for TRIPLE PRIMES is not optimal, i just brute forced all pair of primes less than $$$sqrt(n)$$$.

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

    Test cases are weak ...

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

    The prime number theorem strikes yet again!

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

    after careful observation we can infer that one of the numbers would always be 2 as the N is even i.e.( 2^2 + odd + odd) = N (even), now we have two degrees of freedom only we can iterate through the prime array, and check whether the ( newN — primes[i]*primes[i]) is present their in primes array and its value should be diff from the (primes[i]*primes[i]) , in this way the TC is reduced.

    → Reply
»
5 months ago, # |
  Vote: I like it +30 Vote: I do not like it

In problem Cyclopian Edges, it says N <= 10^5 and M <= 10^5. But I think there are testcases where N and M exceed those values.

AC submission: https://www.codechef.com/viewsolution/1064731464. Runtime Error submission: https://www.codechef.com/viewsolution/1064731491. The only difference between those submissions is that I assert that N and M are at most 10^5.

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

    Sorry for that, there was some last minute miscommunication between N and M which lead to this. It is now updated.

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

Why do problems like B exist? Does anyone even enjoy them?

→ Reply