4

Trilogy Innovations OA Questions and Intuitions

 1 year ago
source link: https://codeforces.com/blog/entry/119105
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
By bin_2u, 17 hours ago, In English

Hello everyone,

Yesterday,Trilogy Innovations OA was held. There were 4 Questions and the time limit was 120 minutes. I am attaching all the questions. It would be really helpful, If we discuss the intuitions and Approaches to the problems. I felt Problems were Quite Interesting.

Change permutation
SubArray - AND - OR
Is It possible
Segment points

I personally felt first 2 problems were a bit challenging.

Thank You,

16 hours ago, # |

Thanks for sharing...!!

14 hours ago, # |

In 4th problem i used difference array concept on map what did you do?

  • 14 hours ago, # ^ |

    Yeah, Same

    • 11 hours ago, # ^ |

      Can you give me idea about how you did segment points.please

  • 10 hours ago, # ^ |

    Can you give me idea about how to approach question 4 if possible

14 hours ago, # |

Solution sketches

A, write permutation as product of cycles, note that number of moves to change to identity is M = sum(c_i — 1), and doing a swap will change this value by +/- 1.

B, do each bit separately, now suppose A[i] <= 1. segment tree, state S[i..j] stores the answer to query type-3 and length of prefix/suffix of ones. operations are set=0, set=1, or nothing.

C, greedy, earlier due date has higher priority

D, sweep line (iterate over each interval-endpoint in sorted order)

  • 14 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Can u explain more on the solution for B ?

  • 9 hours ago, # ^ |

    In problem B how would you combine the answers of multiple intervals while querying??

12 hours ago, # |

Can I code these problems in any coding platform?

8 hours ago, # |

← Rev. 2 →  

+16

2nd problem can be solved using lazy propagation. It's given that A[i] <= 31, which means we only need to consider first 5 bits. so let's solve the problem bit by bit. for any bit the array A will be a binary array. To find the number of subarrays in a range L, R satisfying the 3rd query, we only need to consider the subarrays having only 1's. This can be solved using segment trees. we just need to make a node to store the number of prefix 1's, suffix 1's, length of the range, and the number of subarrays having only 1's. The main task is to make a merge function for merging the left and right nodes of a segment tree. This would be easy if you are comfortable with segment trees. To solve the 1st query, you only need to assign a particular value to a given range which is a current bit of a given number that can be either 0 or 1. For the second query, think if a current bit is 0, this won't affect the range because x OR 0 gives you x. So update the range, only if a current bit is 1. To answer the 3rd query, iterate from 0th bit to the 4th bit and calculate the number of subarrays in a range having only 1's for a current bit. For a particular bit 'b', your answer will be (1 << b) * (the number of subarrays with only 1's). You need to add this answer for every bit ranging from 0 to 4.

  • 5 hours ago, # ^ |

    Very nice. Love and support from Nepal.

  • 5 hours ago, # ^ |

    Either I am missing something terribly simple or you might have left out a case for the query of 3rd type for this segment tree for some bit 'b'.

    Consider this query of the third type: 3 2 6 0

    There isn't a node that will cover exactly this range and the nodes that will return their answers will be [2-2], [3-4], and [5-6](I recommend looking at the segment tree I have drawn).

    Wouldn't we need the following?

    • suffix 1's in [2-2]
    • prefix 1's in [3-4]
    • suffix 1's in [2-4]
    • prefix 1's in [5-6]

    Of course, prefix 1's and suffix 1's in [2-2], [3-4] and [5-6] would be maintained in the segment tree but, what about the suffix 1's in [2-4]? Let me know if I am missing something or if you intended this will be handled in your solution, when you said:
    "...The main task is to make a merge function for merging the left and right nodes of a segment tree. This would be easy if you are comfortable with segment trees..."

    • 4 hours ago, # ^ |

      Merging the nodes (1, 2) and (3, 4) will handle the case.

      • 4 hours ago, # ^ |

        So, we can just use values of the [1-4] node to get the suffix 1's for [2-4]. Now I understand, thanks for responding!

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK