raja1999's blog

By raja1999, 5 years 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), fugazi ( 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: qingczha (Qingchuan Zhang)
  • Vietnamese Translator: Team VNOI
  • Russian Translator: Mediocrity (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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Bump. Contest starts in 10 minutes.

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

How to solve cyclesum. Div1 B.

  • »
    »
    5 years 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

    • »
      »
      »
      5 years 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?

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

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

    • »
      »
      »
      5 years 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?

      • »
        »
        »
        »
        5 years 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

»
5 years 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?

  • »
    »
    5 years 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.

    • »
      »
      »
      5 years 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).

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

        What do you mean by path compression ?

        • »
          »
          »
          »
          »
          5 years 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.

  • »
    »
    5 years 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".

»
5 years 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 raja1999 for the update and sorry for the trouble.