smurf's blog

By smurf, 7 weeks ago, In English,

Greetings Codeforces Community!

CodeChef invites you all to join us at CodeChef’s monthly serving of the Cookoff. A 2.5 hours contest with five servings of challenging problems for you and your peers to relish. Crafted out of the very best ideas, our set of curated problems will take your codebuds on a delightful trip.

Further, the February Cookoff will be the perfect opportunity to give a boost to your CodeChef ratings and rankings. Meanwhile, you can also share with us some original and engaging problem ideas which can be used in CodeChef's future contests, here: www.codechef.com/problemsetting/new-ideas.

I hope you will participate with your fellow programmers and enjoy the contest problems. Joining me on the problem setting panel are:

  • Setters: teja349 (Teja Reddy), adarshagr8 (Adarsh Agrawal), pshishod2645 ( Prashant Shishodia), codewiz (Nitish Gupta), taran_1407 (Taranpreet Singh), nagpaljatin1411 (Jatin Nagpal)
  • Editorialist: (Akash Bhalotia)
  • Tester: raja1999 (Raja Vardhan Reddy)
  • Statement Verifier: Xellos (Jakub Safin)
  • Admin: teja349 (Teja Reddy)
  • Mandarin Translator: UoA_ZQC (Qingchuan Zhang)
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Fedosik (Fedor Korobeinikov)
  • Bengali Translator: solaimanope (Mohammad Solaiman)
  • Hindi Translator: Akash Shrivastava

Contest Details:

Time: 16th February 2020 (2130 hrs) to 16th February2020 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.

Good Luck!

Hope to see you participating!!

Happy Programming!!

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

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump. Contest starts in 10 minutes.

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve cyclesum. Div1 B.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    General Case.
    In our case w=n, just append the input to itself and find max subarray sum with window<=n

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You do realize you replied 5 minutes before the end of the round right?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Really sorry, wasn't aware that it had not ended yet.
        Sorry again

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You probably missed the fact that $$$N$$$ is odd.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, I just didn't knew how to use it. Care to explain in detail or is it too easy?

      • »
        »
        »
        »
        7 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Xor all the A[]s and the B[]s and since n is odd, you get the value of A[1] xor C[1]

        Edit: typo

»
7 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Regarding the last problem, what's the complexity of finding the next largest element for each index of an array, using path compression?

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    $$$O(n)$$$ with a stack, while the top is <= x pop, then top is the next largest element and push x to the stack.

    • »
      »
      »
      7 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yeah, that's what I implemented as well, but the path compression version is quite elegant, I am curious what it's complexity is. My guess is n log (n).

      • »
        »
        »
        »
        7 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        What do you mean by path compression ?

        • »
          »
          »
          »
          »
          7 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Here is one variant — Suppose you denote the original array as a[] and the required array as nxt[]. To find nxt[i], start with cur = i + 1 and keep doing cur = nxt[cur], until you find cur such that a[cur] > a[i] and set nxt[i] = cur.

          This is likely just DSU, as was pointed out in another comment.

  • »
    »
    7 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It's the same as dsu, you can also use union by size to make it "faster".

»
7 weeks ago, # |
Rev. 2   Vote: I like it +9 Vote: I do not like it

Did anyone notice that the handle for one of the setters isn't provided? Well here it is! codewiz(Nitish Gupta).

Edit : Thanks smurf for the update and sorry for the trouble.