July 18- Problem Discussion

general
,
22

Regarding subway,

I got 100 pts,though my solution fails in one task that my friend said ,but the idea is the same for the correct solution with just minor modification to my solution.

first we need to know that reducing the edges to atmost 3,doesn’t change the ans -why?(just try it,if u dont get it ask(u will get it anyway :slight_smile: ))

What i did was just stored 2 edges (correct solution stores 3 edges anyway).

Let dp[i][j][a][b] denote the maximum possible cost on the path from vertex i to 2^jth parent of i such that the path starts with the a^{th} edge of i,and ends at the b^{th} edge to j.

we can now calculate dp[i][j+1][a][b] by merging paths,i mean in order to find max cost to 2^{j+1}th parent of i,it is basically sum of max cost from i to 2^jth parent ,and 2^jth parent to 2^{j+1}th parent.

let us say i wanna calculate dp[i][j+1][0][1],

let par=2^jth parent of i,

dp[i][j+1][0][1]=max(dp[i][j][0][0]+dp[par][j][0][1]+(0th edge to j!=0th edge from j),

dp[i][j][0][1]+dp[par][j][1][1]+(1st edge to j!=1st edge from j),

dp[i][j][0][0]+dp[par][j][1][1]+(0th edge to j!=1st edge from j),

dp[i][j][0][1]+dp[par][j][0][1]+(1st edge to j!=0th edge from j),
)

edge to j means edge ending at j along the path i to 2^{j+1}th,and starting means edge starts at j along the path i to 2^{j+1}th.

Now u can easily answer the query (u,v),

calculate ans for path (u,lca(u,v)),(v,lca(u,v)) using similar strategy ,

And then merge it again taking that 0,1 cases like before.

For the correct code u probably would have to consider all cases for 3 edges.

My solution:

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

3 Likes
23

Could anyone plz provides some insights for gears problem

24

Regarding Tom and jerry,

the best thing to do was consider different graph and see the pattern,u could find that the ans was the maximum clique.

Though this was kinda research problem known as visible cops and robbers game.And it has a huge proof ,saying that the answer for visible cops and robber’s game is (treewidth of the graph)+1,

Here’s the paper if u want to read about it,

http://logic.las.tu-berlin.de/Members/Kreutzer/Publications/11-games-survey.pdf

(At page 19,it is given that ans is treewidth +1)

However finding treewidth is NPC,but since this graph is special(chordal graph),we can do something.

In this :

It is given the treewidth of chordal graph+1=maximum clique

And maximum clique of chordal graph can be easily found using perfect elimination order.

U can read it here:

My solution:

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

3 Likes
25

For EQUILIBR, why don’t we calculate the probability when one magnitude is greater than k/2 ???

26

Did anyone solve the GEARS problem using DSU?
If so, a detailed approach will be appreciated!

27

Hi @vijju123 ,Kindly explain why (mod-1) is used, while calculating nCr() and mod is used while calculating power?

In response to:
https://discuss.codechef.com/questions/131430/july-18-problem-discussion/131461

28

Hi @coldfire8549!
The coder has used Fermat’s Little Theorem.
a^(m-1)=1(mod m) when a and m are co-prime.
If you want to calculate a^b mod m where b is very large and you can calculate b only modulo some p, then you can do so by setting p= m-1.

29

Problem : Gears

For the query of type 3, speed depends only on u and v.
And the sign of answer depends on whether it is connected to other vertex by odd length or even length path. Because in the connected gear system there will be alternate +ve and -ve signs of answer from given vertex.

In short you have to color the graph in two colors.

I had maintained graph and used disjoint set data structure and array for gear teeth and when you have to change the teeth value you can just change value of array.

Maintain different color for each gear and when you connect two gears just change the color of other gear.

Note: Gears will be blocked when there is odd length cycle.
for query of type 3,
Suppose you have two components in which each components may contain several connected gears.
When query of type 2 occurs and you have to connect these two components then use disjoint set data structure and change the color of smaller component according to bigger components For e.g you had used colors 2,3 for 1st component and 4,5 for other component then change color of second component (if 2nd is smaller component).

while connecting two vertices from same component just check if one of them is blocked or by connecting these vertices will there be any odd length cycle ? i.e do they have same color ? because now you cant connect them if they have same color and after connecting they must have different colors hence all the vertices from component will be blocked.

Last while answering type 3 you can check color of both vertices if they are same color : use + sign answer else negative answer.

My solution https://www.codechef.com/viewsolution/19233845

1 Like
30

NMNMX:
For each element of the array, I calculated no. of subsequences in which that element was min and in which it was max by using simple nCr logic. Subtracted it from the total no. of subsequences of each element(same for each). Then raised that element to this no., which could be huge so used Modular Exponentiation.
I got 20 points(AC in subtask 1).
I’m getting Runtime error SIGFPE in subtask 2. Please help, I’m a beginner coder. Please help.
Here’s the link- CodeChef: Practical coding for everyone
Thanks.

31

Can someone share some good resources on Lichao segment tree and convex hull trick? Thanks in advance…

32

It is great way to clear doubts about different approaches for problems and share approaches in a thread form as it more interactive way.

1 Like
33

Problem: NSA

My Solution: CodeChef: Practical coding for everyone

This problem requires a strict time complexity for complete AC solution.
I have used 2 2D arrays(S and G) of size 26*(10^5) and 1 1D array(freq) of size 26.

In the arrray S,I traversed the string from the start and stored the frequency of all the characters which have come before the ith character into the ith column of the array.

In the arrray G,I traversed the string from the last and stored the frequency of all the characters which have come after the ith character into the ith column of the array.

Both of these operations has complexity of order 26*(length of string).

For calculation of Y in initial configuration of string I have summed up all the freq stored in the array G for ith column and jth row such that j>s[i]. (This is equal to number of pairs <si,sj> such that si<sj and i<j).

Now coming to modification part, I have checked all 26 combinations for every character in the string and calculated the difference which a particular change makes.
If the new Y + X is less than min value, the min value is updated.
Complexity for this is order of 26 * 26 * (length of string).

Finally,the min value gives the solution.

1 Like
34

AFAIK, it was dp+LCA. I thought if we can somehow store information about cost like we make LCA table (cost to go to {2}^{i}’th ancestor), but didnt have time to code that/ :frowning:

Who did SUBWAY here? xD

35

Please give LINK to your solution to keep discussion neat.

36

Told @mgch to have a look at it. Thanks for sharing :slight_smile:

37

c++: CodeChef: Practical coding for everyone
python: CodeChef: Practical coding for everyone

38

Yes that was it , LCA

39

Understand that answer is independent of k as your choice is only to assign directions. Look at example and see how 11 and 16 are related to 5. denominator is will something of form 2^x as there are opposite directions for vectors to cancel. Guess 2^{(n-1)} is denominator and then see numerator is exactly n less. Submit and proof by AC. Best guess problem. No idea about logic though.

1 Like
40

Tom and Jerry seemed like maximum Clique or something to me. But I am not well versed in those algorithms. PRFRUIT seemed like clear FFT. Did you try that angle?

41

fuck… I only referred one new algo for this problem… and that was LCA !!!
but didn’t worked on it thinking that would be a tougher question… :frowning: