Which Fuel is Cheaper CHEAPFUEL Solution Codechef

Which Fuel is Cheaper CHEAPFUEL Solution The current price of petrol is XX rupees, and the current price of diesel is YY rupees. At the start of each month, the price of petrol increases by AA rupees and the price of diesel increases by BB rupees. Chef is curious to know which fuel costs less at the end of the KthKth month. If petrol is … Read more

Convex Hulk CONHULK Solution Codechef

Convex Hulk CONHULK Solution Hulk has a set of distinct points PP in the 2D plane. His signature move is HulkHulk SmashSmash. He performed HulkHulk SmashSmash on the set PP which caused the points to change, and so he obtained a new set of points P′P′. More formally, HulkHulk SmashSmash makes the new set P′P′ in the following way: Initially, let P′P′ be empty. For every PiPi and PjPj such that 1≤i<j≤N1≤i<j≤N , add the mid point of PiPi and PjPj to … Read more

Functional Array FUNARR Solution Codechef

Functional Array FUNARR Solution The functional array of an array A=[A1,A2,…,AN]A=[A1,A2,…,AN] is the array fAfA of size N−1N−1, where fAi=Ai+1−AifAi=Ai+1−Ai for 1≤i<N1≤i<N. For example, if A=[2,3,9,11]A=[2,3,9,11] then fA=[1,6,2]fA=[1,6,2]. You are given two arrays B=[B1,B2,…,BN]B=[B1,B2,…,BN] and Z=[Z1,Z2,…,ZM]Z=[Z1,Z2,…,ZM] of length NN and MM respectively. Find out whether there exists an array AA such that: BB is a subsequence of AA, and fAfA is a subsequence of ZZ Print “YES” (without quotes) if such an array AA exists, and “NO” otherwise. Input Format The first line of input contains … Read more

Flip or Compress FLIPCOMP Solution Codechef

Flip or Compress FLIPCOMP Solution You are given a binary string SS. You can perform the following operations on SS: Flip: Pick an index ii (1≤i≤|S|)(1≤i≤|S|) and flip the ii-th character (i.e change 11 to 00 or 00 to 11). For e.g. 011–001→010–001011_001→010_001 Compress: Pick any non-empty substring consisting of the same character and replace it with a single occurrence of that character. For e.g. 1001111–––––10→1001–101001111_10→1001_10 You want to make … Read more

Maximise the bridges MAXBRIDGE Solution Codechef

Maximise the bridges MAXBRIDGE Solution Chef is given two integers NN and MM. Please help Chef find any connected undirected graph GG consisting of exactly NN vertices and MM edges, such that the number of bridges in GG is maximized (among all graphs with NN vertices and MM edges). GG cannot have self-loops or multiple edges. If there is more than one connected undirected graph with the maximum number of bridges, you may print any one of them. Note: A bridge is … Read more