NOV18 - Problem Discussion

copy paste

Hey guys!!

Finally after 10 tiring days the A̶u̶g̶u̶s̶t̶ November long concludes. Lets share our approaches for the problems here while editorials for problems come out (at this moment none n̶o̶t̶ ̶a̶l̶l̶ of them are out)? Got any interesting approach which you cant wait to share? The wait is over :slight_smile:

So, which was your favourite problem? I had best time solving ̶I̶n̶t̶e̶r̶a̶c̶t̶i̶v̶e̶ ̶M̶a̶t̶r̶i̶x̶ ̶:̶)̶.̶ MAGICHF2 ̶T̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶g̶a̶v̶e̶ ̶m̶e̶ ̶a̶ ̶r̶u̶n̶ ̶f̶o̶r̶ ̶m̶y̶ ̶s̶c̶o̶r̶e̶ ̶x̶D̶ ̶-̶ ̶s̶o̶ ̶I̶ ̶l̶e̶t̶ ̶h̶e̶r̶ ̶s̶t̶a̶y̶ ̶w̶i̶t̶h̶ ̶d̶r̶a̶g̶o̶n̶s̶ ̶a̶n̶d̶ ̶b̶e̶ ̶b̶y̶ ̶h̶e̶r̶s̶e̶l̶f̶ ̶t̶h̶e̶n̶ :stuck_out_tongue:

But on a serious note, anyone who was able to MAXDTREE s̶a̶v̶e̶ ̶t̶h̶e̶ ̶p̶r̶i̶n̶c̶e̶s̶s̶ ̶(̶o̶r̶ ̶p̶r̶i̶n̶c̶e̶.̶.̶.̶? :p). I kept on getting TLE W̶A̶ for larger TCs, so I appreciate any approaches for it :slight_smile:

P.S. - If someone can write something on interpolation (s)he is most welcomed. I invite @gorre_morre and @algmyr for this task. (:frowning: Tagging here don’t send any notification.) I derived some required equations for CHEFEQUA, didn’t check the correctness of those equations because I knew even I these are correct then time left for the contest in insufficient to implement those.

Let the discussion begin!

/copy paste

4 Likes

What can be even faster way for this problem “HMAPPY1”

Problem Link: https://www.codechef.com/NOV18B/problems/HMAPPY1

My Solution: https://www.codechef.com/viewsolution/21609881

my solution was only able to get me partial points…

Can someone share his/her approach of binary string? It has really weak test cases, my brute in PYPY passed with a fast IO. In the test cases, there was a large string only, so without inserting it in the trie, one could solve it. But can someone share an approach which runs for large and strong test cases.?

1. For HMAPPY1:
I used Segment Tree. Though, it can be done with Bruteforce on Strings. Here is my


[2]

**2. For [GMEDIAN][3]:**
I used combinatorics approach as the naive submission had complexity O(2^n) which can be seen as a pattern. Here is my 

4.

3. For MAGICHF2:
This was a simple problem. All you needed is a correct direction of moves and evade some edge cases Here is my


[6].

**4. For [BINSTR][7]:**
I used Trie with Intervals for this problem. The main issue with this problem is different lengths with larger differences between max length and second max length and the larger number of zeros to be appended which I saved beforehand to prevent again and again traversal. Here is my 

8.

If you feel like I should comment the code, or you have any queries in the code, you are free to ping me here :slight_smile:

1 Like

0.14 sec, same with my solution. I don’t remember why I wrote so much code, but still fastest Python solution belongs to me :stuck_out_tongue:
https://www.codechef.com/viewsolution/21381609

2 Likes

I so wanted to get 5 points from CHEFEQUA. I understood it requires something like FFT but still tried hard with Gaussian elimination, then tested my solution with n=10 custom test and it failed. FFT solutions looks too scary but I guess it’s time to familiarize with it.

1 Like

even i used combinatorics for GMEDIAN but getting TLE: Can someone help…?

My Solution Link: https://www.codechef.com/viewsolution/21612107

1 Like

@tushar2899 try to use some naive code as tester for your code. If your code was on the right direction it should not have failed for task 1 atleast. Check your approach and use some naive code for checking your direction of the code. I have included a naive checker below in my code :slight_smile:

Please suggest some test case for which my HMAPPY1 solution should fail, because I am only able to pass few test cases, and others are showing wrong answer.I tried all the possible combination of arrays but still many test cases showing wrong answer.

Problem Link

My solution

HMAPPY1 can also be solved like this https://www.youtube.com/watch?v=T47EFVOJbgc

This may help you https://www.youtube.com/watch?v=T47EFVOJbgc

https://www.codechef.com/viewsolution/21550313

My solution to HMAPPY1… segment tree not used… is based completely on analysis

Considering I didn’t compete this time I’ll let gorre_morre make comments on CHEFEQUA if he wishes to. :stuck_out_tongue:

I know he had a blast with the problem. It boils down to speeding up polynomial calculations with NTT for quick convolutions and some cleverness, both of which are up his alley.

His last submission on the problem has rather clean code, so it’s worth looking at: https://www.codechef.com/viewsolution/21514506

3 Likes

here is what I did :

  • made an array of all the strings that have length > THRESHHOLD
  • made the trie with interval for all other string that have length < THRESHOLD

For every query compute 2 results -

  • one from the array (elems that fit in [L, R] inteval)
  • one from trie
    Output the max out of those 2.

Link - https://www.codechef.com/viewsolution/21508887

@tieros we are switching “fastest” for different tasks, but you get the lowest maximum. my code

1 Like

nice solution joffan, you’re even not using something like deque

“HMAPPY1”
first find 2 max size substring and store their first and last pointer and when shift queries come you just move 4 points and for length query you just need to check size of both substring both query thake O(1) time

https://www.codechef.com/viewsolution/21397995

“GMEDIAN”
Its simple observation you for making odd length subset you have 2^(n-1) possible way i proved that with equation (l+r) C (l) way to choose elements in array at (l+1) position where (l+r+1) = n

Now for even length we need to check frequency of number and after some observations you can find solutions with O(n²) so total time complexity O(n²)

https://www.codechef.com/viewsolution/21483295

“MAGICHF2”
If N is even than we need to divide N like after devide N is two part one part still can divide by 2
But for odd we need to add one into it
And after logN/K iteration you can find its probability.

https://www.codechef.com/viewsolution/21521761

"CHEF and Eq "
First i tried with Gaussian elimination in O( n³ ) but after reading some papers i can make in O(n²)
Its known as vandermonde matrix.
And i read about FFT i think that it will be solutions of it
May be using MOD root of unity.
I can’t solve it for 100 point.

O( N²) for more information

" MaxDigit "

For subtask 1 we just need to know how many paths are passing from node 1 in s using dfs an after than remove node from distance 3 and ( Children of root C 2 ) from ans…

I didn’t paste partially point solutions you can check

For prime tree and Chef and recipe i used brute force approach for partially point
I got TLE in BinXor

3 Likes

Gaussian elimination trick gives 5pts for CHEFEQUA. My Soln

1 Like

The test cases for Binary Strings were very weak, I have seen many PYPY solutions where just brute force was applied and they got AC. It just kills the main motive behind the problem and a language advantage is the last thing I want to see on Codechef. I myself was not able to solve the problem and seeing so many people get AC using only brute force is saddening :frowning:

I am eagerly waiting for Editorial of CHEFEQUA , RECIPIES, and MAXDTREE. I was only able to grab partial points.

RECIPES: These type of Half-second question are really interesting. (CPCOMP) Last time. One can definitely relate merging of elements. @bciobanu or @gorre_morre anyone else who could enlighten about variants of these kinds of problems would be help to all. I am really eager to know different approach to solve such merging question.

CHEFEQUA: A Math-Mamoth I would say. One could easily figure out 20 point solution using Vandermonde Matrix to solve Linear System of Equation. After some more efforts one could relate it with FFT and Interpolation. The giant Task lies in connecting it question. I spent a lot of time going through different articles and Tutorial about FFT and Interpolation. Unfortunately, I couldn’t figure out the solution for question. @taran_1407 expecting a gem from you again.

MAXDTREE: One can check the length of patterns with occurrence of 2 using program to generate series and easily deduce that pattern for 2 exist for all, but length 3. I am totally blank about that 100pt approach. Waiting for editorials.

An awesome contest, I would say. Learnt a lot ( though couldn’t implement everything :stuck_out_tongue: ).

3 Likes