kingofnumbers's blog

Invitation to CodeChef June Cook-Off 2016
By kingofnumbers, 8 years ago, In English

Hello Programmers!

I would like to invite you to participate in June Cook-off, it will start at Sunday, 26th June, 2016 at 21:30 HRS (IST), and will last for 2.5 hours, The contest will have 5 algorithmic problems of varying difficulties. the link to contest here.

  • Problem Setter: kingofnumbers (Hasan Jaddouh)
  • Problem Tester: mgch (Misha Chorniy)
  • Editorialist: pushkarmishra (Pushkar Mishra)
  • Mandarin Translator: huzecong (Hu Zecong)
  • Russian Translator: Antoniuk (Vasyl Antoniuk)
  • Vietnamese Translator: VNOI Team
  • Contest Admin: PraveenDhinwa (Praveen Dhinwa)

Top 10 international and top 10 Indians will get CodeChef laddu, find more about them here.

Feel free to discuss the problems after the contest, I hope you will find the problems interesting, looking forward to see you in the contest.

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

»
8 years ago, # |
← Rev. 3   Vote: I like it +10 Vote: I do not like it

For CAKECUT is there any other solution in O(N2) or O(N2 log N) ? I know only of an O(N3) algorithm.

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

    The intended solution is O(N^3) with bitset optimization (which make it N^3/32), you can read about the solution in the editorial

    Actually when I came up with this problem I tried to solve it with a solution without bitset but after trying hard I couldn't find a better solution than bitset solution, so I decided to let it be the intended solution and hoping that someone will submit a solution during the contest of complexity O(N^2) or O(N^2 log N) without bitset, after the contest I looked at all correct submissions but all of them are the same solution with bitset.

    I would be very happy if someone can find a solution without bitset and explain it to us.

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

      In the editorial, shouldn't the formula for count0 be c0·(c0 + 1) / 2 ? Because there might be a submatrix that has even sum and its left edge is the first column of matrix.

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

      Okay, the formula which I mentioned above is right but if you increment c0 by 1, then c0·(c0 - 1) / 2, can also be used(which is what editorialist has done), but I think it should be mentioned in editorial to not confuse others.

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

        I didn't understand from the editorial how is it that the amount of good rectangles increases by c0·(c0 - 1) / 2.

        Could you elaborate on that?

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

          c0 is the count of zero's after XORing 2 rows. What does a 0 at place i indicate? It indicates that submatrix between the 2 rows which were XORed, the left most column and the column at position i, has an even sum. So how many even sum submatrices can we create which end in these 2 rows? We can choose any 2 out of all occurrences of 0s. Hence the formula. Note that you have to increase c0 by 1 to count submatrices which have column number 1 as the leftmost column.

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

hi everyone! i saw one of the accepted solutions:- https://www.codechef.com/viewsolution/10621740 here h^4 and s^2 is directly used which will overflow in c++ according to constraints.. then why this gets accepted?? any thing i am missing out.. please help..

→ Reply