Invitation to CodeChef April Lunchtime 2018!

Editorial - Expected Time ??

For me, understanding Triple Tree Decomposition proved really difficult. IDK, the meaning just didnt strike me- to that extent, that I dont know WHY I got 80 points. I could just vaguely get that setter wants us to check if each node has 3*k edges to divide into sets…? Can anyone elaborate?

This is one of the question where explanation of sample Input Output would be a great convenience. If its not really necessary, please dont skip that section.

EDIT- Also please explain what should be the output for cases when N\le 3. I was assuming that its “Yes” because of vacuous truth, but solutions printing “No” for these are accepted.

2 Likes

How to solve TREE3?

My approach

Find any node having number of adjacent nodes divisible by 3. Then check if it’s Triple-tree decomposition using this as root.

My WA Code

gcddiv was easy peasy,fft was nice problem,tree3 was confusing and last 2 were unapproachable for me atleast:)

I was not getting any idea for GCDDIV. How did you guys got the idea to solve it.

@admin is this contest unrated? i see that the ratings are reverted.

2 Likes

I have no karma points and I want to ask a question that Question is related to April Lunchtime 2018 The problem code is GCDDIV I found two submissions which got 100 points One is CodeChef: Practical coding for everyone and the second is CodeChef: Practical coding for everyone The first submission got 100 points event thought It does not deserve 100 points because that fails for the test cases like

1 
3 6 
101 10201 1030301

For this the solution 18380850 gives its answer as “YES” but the right answer is “NO” solution 18375921 gives correct answer as “NO” for the above test case

Now I want this to be looked upon by the codechef

1 Like

Wrong judgement for GCDDIV
For Example test case:

1

3 10

18 36 72

Returns ‘YES’ for some submissions and ‘NO’ for other but both are marked as correct by the judge.

From my point of view, ‘YES’ will be correct answer as gcd of above number will be 18 which can be represented as 2*9 (both 9 and 2 being less than 10).
Link to both solution are:

my solution: CodeChef: Practical coding for everyone

other solution: CodeChef: Practical coding for everyone

2 Likes

3rd problem was quite confusing, so i started doing it on paper. Since it was written that we’re required to print (N-1)/3 lines of output for each testcase, and later i found out why is it so.
So, for 1st subtask, i.e. N<=10 answer is YES for N=4,7,10 and that is also in some cases. I figured that out and wrote code for these special cases to get Partial Score. I know this is not how we should deal with the questions, but just for the sake of my curiosity, i am asking this here.
However, I found out that for 1st subtask the input value of N in TestFile is just 10.
If anyone of you have some time, plz give my solution a glance, i don’t know why i got WA.

My WA

Editorials for the contest?

Same with me. Testcases are definitely weak for last 2 substasks.

I can confirm that. My solution had a really pathetic bug- if root has only 1 child, it would mistake it as a leaf and return back, doing nothing XD

Try this case-


1
7
1 2
1 3
1 4
5 4
5 6
5 7

If you draw this one, you can find that the special thing here is that node 4 is shared. Anyone terminating search at node 4 (on getting condition like number of edges from this node is not a multiple of 3) will suffer a WA here. Didnt check your solution, but I will say try for yourself once for smaller cases. :slight_smile:

1 Like

Got it. Thanks! :slight_smile:

if N<=3 , the number of edges would be less than 3 and you can’t partition the edges into groups of 3, so the answer would obviously be ‘NO’

2 Likes

They will be calculated after LoC.

2 Likes

The goal was to make the GCD of the array 1, to do that, just find the GCD of the array and divide it with each element and thats it,but now if the GCD is greater than K you can’t divide it directly so divide with the prime factors of GCD, if its not possible then its “NO”.

1 Like

I used topological sort approach. I modified this algorithm( Kahn's algorithm for Topological Sorting - GeeksforGeeks ) such that all the sources are those nodes which have degrees in multiple of 3. Afterward, I used the above algorithm to propagate further.
My AC Java solution CodeChef: Practical coding for everyone

Soon it will be posted in threads for each problem independently

2 Likes

Hello all,

All the editorials of this contest are now released. We regret the delay in editorials and hope such instances dont occur in future. Thank you :slight_smile: