teja349's blog

Invitation to CodeChef September Long Challenge 2018 sponsored by ShareChat!
By teja349, history, 6 years ago, In English

Hello CodeForces Community!

We’re excited to announce the September Long Challenge sponsored by ShareChat. Along with the opportunity to boost your ratings and win some cool laddus, there are some exciting full-time job opportunities with ShareChat for professionals across the globe. More details about the job opportunities can be found on the contest page.

  • Problem Tester: teja349 (Teja Vardhan Reddy)

  • Problem Setters: (Shivam Gupta ), XORier (Priyanshi Gupta), adamant (Oleksandr Kulkov ), step_by_step (Stepan Filippov), bciobanu (Bogdan Ciobanu), rajat1603 (Rajat De), DOlaBMOon (Max Hsia)

  • Problem Editorialist: vijju123 (Abhishek Pandey)

  • Statement Verifier: Xellos (Jakub Safin)

  • Russian Translator: Mediocrity (Fedor Korobeinikov)

  • Mandarin Translator: huzecong (Hu Zecong)

  • Vietnamese Translator: VNOI Team

I hope you will enjoy solving them. Please give your feedback on the problem set in the comments below, after the contest.

Contest Details:

Time: 7th September 2018 (1500 hrs) to 17th September (1500 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.).

Contest link: www.codechef.com/SEPT18

Registration: You just need to have a CodeChef handle to participate. For all those, who are interested and do not have a CodeChef handle, are requested to register in order to participate.

Prizes: Top 10 performers in Global and Indian category will get CodeChef laddus, with which the winners can claim cool CodeChef goodies. Know more here: discuss.codechef.com/questions/51999/how-do-i-win-a-codechef-goodie.
(For those who have not yet got their previous winning, please send an email to winners@codechef.com). First to solve each problem individually: 100 laddus (For problems common to both Divisions, only one user will get laddus for that problem).

Good Luck!
Hope to see you participating!!

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

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

Auto comment: topic has been updated by teja349 (previous revision, new revision, compare).

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I hope no one solves the last question. :P

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve TAB GAME subtask 2, (with proof )

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 7   Vote: I like it +3 Vote: I do not like it

    Hint: For all points in the set S = {(i, j) | i >= 3 and j >= 3}, (i, j) = 0 if and only if (i-1, j-1) = 0. You can prove this by contradiction.

    Proof that if (i, j) = 0, (i-1, j-1) = 0:

    Let(i, j) = 0. Assume that (i-1, j-1) = 1. Since (i, j) = 0, (i-1, j) = 1 and (i, j-1) = 1.
    Since (i-1, j) = 1 and (i-1, j-1) = 1, (i-2, j) = 0. Similarly (i, j-2) = 0.
    Since (i-2, j) = 0, (i-2, j-1) = 1. Similarly, since (i, j-2) = 0, (i-1, j-2) = 1.
    Since (i-2, j-1) = 1 and (i-1, j-2) = 1, (i-1, j-1) = 0.
    This contradicts our assumption.
    So if (i, j) = 0, (i-1, j-1) = 0.

    The converse:

    If (i-1, j-1) = 0, then (i, j-1) = (i-1, j) = 1. So (i, j) = 0.
    So if (i-1, j-1) = 0, (i, j) = 0.

    Rest of the solution should be simple.

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

      if (i-1, j-1) = 0, then (i, j) = 0 is obvious by contradiction, but how to prove the converse?

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

        Added the converse.

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

          May be I'm missing something but how did you get this If (i-1, j-1) = 1, then (i, j-1) = (i-1, j) = 1. So (i, j) = 0.

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

            Sorry, that was a typo. It should be If (i-1, j-1) = 0.

            → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone explain the logic behind Bad Shuffle problem?. I tried running the algorithm given in the problem 100000 times and then finding the permutation with maximum and minimum frequency but obviously, it will barely made through the first subtask. As it seems there is propper algorithmic solution to the problem as I saw in this solution here. Can someone explain the proof of this solution.

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

    I haven't tried yet, but I guess it can be proved by considering a graph just similar to this

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

    Don't know the proof, but it's similar to my solution. Found out how it works after backtracking for small cases.

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

    It reduces to a pattern finding problem. As RayPatterson said, you brute force it for for all cases from n = 1 to 8, write down the permutations which have minimum and maximum frequencies and try to find a pattern between them, that gives you a generalized solution for any n.

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

Not very important, but did codechef reduce the number of Indian participants getting laddus from 20 to 10?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve ANDSQR ? I know that it must be solved with datastructure segment tree or something like that ,but i don't know how to use it in this task . Can someone to explain me solution?

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

    Maximum number of set bits in a number will be 30. Hence the bitwise and value starting from any particular a[i] will change at most 30 times. Go backwards starting from any i and check where the and value (initial value = a [i]) changes . You should be able to do it in 30 iterations max. For this just keep track of the index where the the particular bit was unset for each bit . This way you will be able to find no. Of good sequences in whole array . Use segment trees to find the count of good sequences in range . If you are not clear mention which part.

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide the prerequisites and idea for the FCTR question ?

→ Reply
»
6 years ago, # |
← Rev. 5   Vote: I like it +5 Vote: I do not like it

I checked the top submission for CHEFLST question . The implementation and complexity is understandable but can anyone explain how are all numbers guaranteed to picked by this algo, please . Link in Traxexeuler's reply .

→ Reply
  • »
    »
    6 years ago, # ^ |
    ← Rev. 3   Vote: I like it +20 Vote: I do not like it

    That solution is wrong. The test cases are pretty weak.

    1
3
0 0 0
0 0 1
0 1 0

    The correct answer is 0 1 but the code prints 0.

    Your link is broken btw: https://www.codechef.com/viewsolution/20056532

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

      Thanks for pointing out. If you have solved the question can you please help what is the actual solution for the question ? Is it something related to finding determinant for a matrix as it looks we need to pick up elements from every row , every column , basically what a determinant for a matrix does .

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

        After some more investigation, about half of the 100pt submissions seem to be wrong. That's ridiculous, CHEFLST was the hardest problem!

        I did not solve it myself, and now I feel sad for the people who did come up with proper solutions.

        I was told that this approach is correct: https://www.codechef.com/viewsolution/20118711

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

What is the idea behind problem Chef and Lost Story?

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

    Let s = 10, such that all entries of M are  < 2s

    Consider a matrix H whose entries are polynomials Hij = xMij. Now, if we find the permanent of this matrix under xor convolution, then the answer would be powers with non-zero coefficients. But sadly, we can't find permanent in polynomial time.

    Instead, multiply each entry of H by a random integer, and find the determinant, and by Schwartz–Zippel lemma, we would get the right answer with a high probability.

    To find the determinant, we can use evaluation and interpolation in a XOR-FFT fashion (considering the resultant as a multivariate polynomial in s variables, and evaluating determinant at roots of unity, (in this case, { - 1, 1}s). Overall complexity is O(n32s)

    Link to solution

    → Reply