Help needed in Codekaze's Problem

3 years ago, # ^ |

Thanks.

→ Reply

prashar32

3 years ago, # ^ |

+17

Implemented the same and passed 90% of the testcases rest TLED. But this can be done 100% with this approach.

→ Reply

3 years ago, # ^ |

+22

You will be shocked to know that I used brute force and 90% passed

→ Reply

3 years ago, # ^ |

I think that the testcases were very weak for 5th and 6th problem .

→ Reply

3 years ago, # ^ |

Can u tell your approach for problem 5?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

let mx[i] = maximum character in the string s[i....n] Notice that since we need to reverse only 1 substring so we should reverse the string starting at index i and ending at index j , s.t. (s[i]!=mx[i] and s[j]=mx[i] and i<j and i is as small as possible ) Now value of i can be found in O(N) and value of all j's can be found in O(N) as well.
Time complexity is O(N^2) passed because of Weak TC
So , now we can check for all j by traversing on the length x of the new string and comparing character which will be at x'th position for the new strings .New string are string formed after reversing substring from i to j .

→ Reply

3 years ago, # ^ |

First I thought of O(n^2) solution but didn't implemented as it would give tle

→ Reply

3 years ago, # ^ |

There is O(NlogN) as well which uses string Hashing and Binary search . Let there be 2 values l,m in the vector containing j , so now we can binary search the first element that differs after reversing s[i...l] and s[i...m] , hash value can be used to check whether string of length mid are equal or not .
P.S.: This one is what I thought at first , but I just went for O(N^2) solution at first

→ Reply

3 years ago, # ^ |

Were you able to solve the 4th problem ?
Problem Statement:
Given a tree consisting of N nodes , find minimum no. of edges to be removed to get atleast one component of size K for all(1<=K<=N).
1<=N<=1000

→ Reply

3 years ago, # ^ |

I was only able to solve 2 problems with all the test cases passed

→ Reply

shawchandankumar20

3 years ago, # ^ |

How the subsequence with product's unit digit is k would be solved???¿????

→ Reply

3 years ago, # ^ |

← Rev. 2 →

It's a Dynamic programming problem , for the ith element there are two option only , either this element can be included or it can't be .
dp[i][j] denotes no. of subsequences considering first i element that have value at unit digit equal to j .
Transition are : dp[i+1][(j*(a[i]%10))%10]+=dp[i][j]; (i.e. current element is included )
dp[i+1][j]+= dp[i][j]; (i.e. current element isn't included )

→ Reply

Amanr11314

3 years ago, # ^ |

← Rev. 2 →

Hey did you solved that problem in which chalk was to be divided into pieces by k children's in which we had to find the minimized maximum chalk length

and also for this subsequence with product's unit digit is k can you please provide the code.

→ Reply

shawchandankumar20

3 years ago, # ^ |

Minimum maximum chalk length can be solved by binary search on answers

→ Reply

OmShivamR24

3 years ago, # ^ |

I found some of the test cases were giving faulty results. For ex, N = 3 and K = 0 with Arr = { 2 , 6 , 0 } should return value as 6 but the judge was considering value = 3 for such case.

Also N = 2 and K = 2 with Arr = {7 , 17} . The return value should be 8 but the judge was expecting 7.

I tried using maps but was getting caught up in test cases like this.

→ Reply

sam1tejch

3 years ago, # ^ |

for n = 2 k = 2 a = {7,17} return value is 7. 7,17 7,10,7 (17 = 7+10) k = 1 7,5,5,7 (10 = 5+5) k = 2

→ Reply

ssc_2001

3 years ago, # ^ |

← Rev. 2 →

They were not allowing to use max heap(priority queue). So I had to use vector & sort it again & again that's why it resulted in TLE. Still, 72% of the test cases passsed.

→ Reply

3 years ago, # ^ |

U should have just included it's header file . It might have worked .

→ Reply

3 years ago, # ^ |

← Rev. 8 →

Yes it can be done by applying dp on the flattened tree.

First flatten the tree using euler tour and then take dp[i][num_removed] which means we have covered all the subtrees with exit time less than i and total nodes removed is num_removed.
LHS means Left hand side of the equation

Like for the first example given there euler tour is something like
n=6, edges={0,1},{0,2},{2,3},{2,5},{3,4}
euler tour: 0 1 2 3 4 5
(here coincidence is in_time is same as node number(not necessary))
initially

$$$dp[i][j]=1e9$$$

for all

$$$i,j$$$

initialise

$$$dp[0][0]=0$$$

if we take the first subtree at that start at time 0
then transition

$$$if(i==0){ add=-1;}$$$

(I rooted the tree at node 0)}

$$$dp[i+out_time[node_at[i]]+1][k+sub_t_size[node_at[i]]]=min(LHS,dp[i][k]+1+add);$$$

if we not cut current subtree that start at time i

$$$dp[i+1][k]=min(LHS,dp[i][k]);$$$

and ith ans is

$$$min(dp[n][i],dp[n][n-i])$$$

//dp[n-i] is excluded when i=n

in[],out[] times and node_at[] can be calculated with simple DFS

70% test cases passed

The test cases which were not passing because of some validator error like this, incorrect and is shown even when right ans is outputted

Images

→ Reply

3 years ago, # ^ |

What is LHS ?

→ Reply

3 years ago, # ^ |

Plz check the lastest edit and LHS is left hand side

→ Reply

3 years ago, # ^ |

Okkk .
So in this solution of yours u r considering that if we delete an edge from i->j such that j is a descendent of i , we don't need to delete any other edge in the subtree of j ?

→ Reply

3 years ago, # ^ |

← Rev. 2 →

Right if we deleted an edge , that would delete a complete subtree and we won't be able to delete any other edge in the deleted subtree

And state defining choices are we delete a subtree ofcouse by deleting an edge or not

→ Reply

3 years ago, # ^ |

Ok , thanks

→ Reply

3 years ago, # ^ |

Hey plz look at the images in spoiler and
can you tell why even correct output is marked incorrect?
and
one more thing I wanna add is when I downloaded the testcases even they were downloading not the same question

→ Reply

3 years ago, # ^ |

U returned a vector of size n+1 rather than of the the size n , maybe that's the reason . I have no idea about testcases , I too faced same issue.

→ Reply

3 years ago, # |

Can someone help me with this

→ Reply

SubZero369

3 years ago, # |

+18

Did anyone get a mail regarding placements from codekaze ? Could you mention your national rank, graduation year and graduation year rank if you did receive a mail regarding placements?

→ Reply

3 years ago, # ^ |

They asked to fill Google form National rank 497 Graduation year rank 104

→ Reply

SubZero369

3 years ago, # ^ |

← Rev. 2 →

What year are you in and when did you get the mail?

→ Reply

tanishq_code_c

3 years ago, # ^ |

← Rev. 2 →

I haven't received any details about placements from codekaze.

National rank: 393

Graduation rank: 252

Pre-final year

→ Reply

aditya_01

3 years ago, # |

is there any way i can test my approach for this and other problem that were asked in the contest.(I cannot took part in the contest but want to upsolve)?.

Thanks in advance.

→ Reply