Editorials for "Mystery Language" contest (MYL2020)

Contest Link: Mystery Language

This contest was organised by NJACK. Now, we have made it public. You can check it out. Here is the explanation & solution for every problem statement.

Contest Manager: hackcyborg

Organiser: NJACK,Not Just Another Computer Science (K)Club
Indian Institute of Technology (IIT) Patna

Problem Setters: hackcyborg , Ashsihanjan1 , & hrishb10

Tester: ravik1

1. STICKY CARS (STICKY)

Problem Setter: hackcyborg

Problem Link : https://www.codechef.com/MYL2020/problems/STICKY

Explanation:
Answer is the sum of (final position of each car - initial position of each car).
After collision, the car will move with the speed of the left car(with position less than the current one’s), but for the collision to happen, the left car at position ‘b’ and velocity ‘vb’ and the cars in front of it with position ‘i’ and velocity ‘vi’ should satisfy the condition (vb - vi)t >= (xi-xb). The final position would then be vbt+b for all the collided cars.

Solution:

import java.util.Scanner;
object Main extends App {
    var scanner = new Scanner(System.in);
    var n=scanner.nextInt();
    var r=scanner.nextLong();
	var x : Array[Long] = new Array[Long](n);
	var v : Array[Long] = new Array[Long](n);
	for(i <- 0 to n-1)
	{
	    x(i)=scanner.nextLong();
	    v(i)=scanner.nextLong();
	}
	var sum=x(0)
	var co =1L
	var num=0
	var ans=0L
	for(i<- 1 to n-1)
	{
	    if(x(i)-x(num)>r*(v(num)-v(i)))
	    {
	        ans=ans+co*(r*v(num)+x(num))-sum
	        co=1L
	        num=i
	        sum=x(i)
	    }
	    else
	    {
	        co=co+1l
	        sum =sum + x(i)
	    }
	}
	ans=ans+co*(r*v(num)+x(num))-sum
	println(ans);
}

2. Alex and Chocolates (ALEX)

Problem Setter: Ashishanjan1

Problem Link : https://www.codechef.com/MYL2020/problems/ALEX

Explanation:
This problem is quite similar to that of finding the nth Fibonacci number. But here the first two numbers might not necessarily be 1. Also the the nth number is some linear combination of the previous two. Since n can be very large we use a technique called Matrix Exponentiation. We first write the linear recurrence in Matrix form ( F_N = X * F_(N-1) where X, F_N and F_(N-1) are all matrices).

Clearly, F_N = (X ^ (N - 2)) * F_0
Where, X = (( A B ), ( 0 1))
F_0 =(D C )

So raise the power of the matrix to n-2 using binary Exponentiation technique to find the required answer. If n is less than two print the answer directly as the value of first and second terms of the series is already known to you.

Solution:

import java.util.Scanner;
object Main extends App{
       var MOD = 1000000007L;
        var scanner = new Scanner(System.in);
  def multiply(A : Array[Array[Long]], B : Array[Array[Long]]) : Array[Array[Long]] = {
      var res = Array(Array(0L, 0L), Array(0L, 0L));
      for(i <- 0 to 1) {
          for(j <- 0 to 1){
              for(k <- 0 to 1) {
                  res(i)(j) += A(i)(k) * B(k)(j);
                  res(i)(j) = (res(i)(j) % MOD);
              }
          }
      }
       
      return res;
  }
   
  def exp(At : Array[Array[Long]], bt : Long) : Array[Array[Long]] = {
      var res = Array(Array(1L, 0L), Array(0L, 1L));
      
      var b = bt ;
      var A = At;
      while(b > 0L){
          if(b % 2L == 1L){
              res = multiply(res, A);
          }
          b = b / 2L;
          A = multiply(A, A);
      }
       
      return res;
  }
   
 
 
    val n = scanner.nextLong();  
    var a = scanner.nextLong();
       
    var b = scanner.nextLong();
    var x = scanner.nextLong();
    var y = scanner.nextLong();
    var mat = Array(Array(a, b), Array(1L, 0L));
    
    if(n == 1)  {
        print(x);
    }
    else if(n == 2){
        print(y);
    }
    else{
        var one : Long = 0L;
        var zero : Long = 0L;
        var res = exp(mat, n - 2);
        var ans = (res(0)(0) * y + res(0)(1) * x) % MOD;
        println(ans)
    }
}

3. Problem with Cubics ( PQBIC)

Problem Setter: hrisbh10

Problem Link : https://www.codechef.com/MYL2020/problems/PQBIC

Explanation:

  1. The problem can be solved by Binary search, if you know how is the monotonicity, in different ranges, of the polynomial function(f(x)).If a < 0, then multiply the function with (-1). Solve for this function now.If the derivative of the function has a discriminant <= 0 then it’s surely a monotonic function over (-inf,inf). If the discriminant > 0 then there ar different cases:

1->The local maxima(f(a)) and local minima(f(b)) are on the opposite sides of the x-axis.Apply binary search on range (a,b)

2->The local maxima(f(a)) and local minima(f(b)) are above x-axis, apply binary search on (-inf,a)

3->The local maxima(f(a)) and local minima(f(b)) are below x-axis, apply binary search on (b,inf).

  • Note: Keep in mind, the monotonicity of the function (increasing/decreasing).

Solution:

import java.util.Scanner
import scala.math.sqrt
object Main {
   def main(args: Array[String]) {
      var scanner = new Scanner(System.in);
      var a:Double = scanner.nextDouble()
      var b:Double = scanner.nextDouble() 
      var c:Double = scanner.nextDouble()
      var d:Double = scanner.nextDouble()
      
      if(a < 0){
          a = -a
          b = -b
          c = -c
          d = -d
      }
      def poly(x:Double):Double = {
          return ((a*x*x*x) + (b*x*x) + (c*x) + d)
      }
      
      def bin_sc(low:Double,high:Double,sgn:Int):Double = {
          var lo = low
          var hi = high
          while(hi - lo > 0.000001){
              var mid:Double = (lo+hi)/2
              if(sgn*poly(mid)<=0){
                  lo = mid
              }
              else
                  hi = mid
          }
          return lo
      }
      //coeffiecients of Derivative of polynomial
       var A:Double = 3*a
       var B:Double = 2*b
       var C:Double = c
       
       val disc = (B*B) - (4*A*C)
       var ans:Double = 0
       if(disc<=0){
           ans = bin_sc(-100000,100000,1)
       }
       else{
       	//roots of derivatives
           val x:Double = (- B - sqrt(disc))/(2*A)
           val y:Double = (- B + sqrt(disc))/(2*A)
           if((poly(y)>0 && poly(x)>0) || (poly(y)<0 && poly(x)<0)){
           		if(poly(y)>0)
               		ans = bin_sc(-100000,x,1)
               	else
               		ans = bin_sc(y,100000,1)
           }
            else
                ans = bin_sc(x,y,-1)
       }
      println("%.5f".format(ans))
   }
}

4. Sunny and Bitland ( EXPAND)

Problem Setter: hackcyborg

Problem Link : https://www.codechef.com/MYL2020/problems/EXPAND

Explanation:
An Efficient Solution can solve this problem in O(n) time. The assumption here is that integers are represented using 32 bits.

The idea is to count number of set bits at every i’th position (i>=0 && i<=31). Any i’th bit of the AND of two numbers is 1 iff the corresponding bit in both the numbers is equal to 1.

Let k be the count of set bits at i’th position. Total number of pairs with i’th set bit would be kC2 = k*(k-1)/2 (Count k means there are k numbers which have i’th set bit). Every such pair adds 2i to total sum. Similarly, we work for all other places and add the sum to our answer.

This answer can be divide by nC2 in order to get expected value which is our Final answer.

Solution:

import java.util.Scanner;
import scala.math.BigDecimal;
object Main extends App {
   var mod=1000000007.toLong
    def binpow (a:Long , b:Long ) : Long = {
   if (b == 0)
        return 1;
    var re = binpow(a, b / 2)
    if (b % 2==1)
        return ((re * re)%mod * a)%mod
    else
        return (re * re)%mod
}
    def modinv (n:Long) : Long = {
   return binpow(n,mod-2)
}
   var scanner = new Scanner(System.in);
   var n=scanner.nextInt();
   var a : Array[Long] = new Array[Long](n);
   for(i <- 0 to n-1)
	{
	    a(i)=scanner.nextLong();
	}
	var ans=(0).toLong
	for(i <- 0 to 30)
	{   var co=0.toLong
	    for(j <- 0 to (n-1))
	    {
	        if((a(j)&(1.toLong<<(i).toLong))>0.toLong)
	        co=(co+1).toLong
	    }
	    ans=ans+((co*(co-1.toLong))/2.toLong)*(1.toLong<<(i).toLong);
	    ans=ans%mod
	}
	val u=((ans*2.toLong).toLong)
	val v=(((n-1).toLong*(n).toLong).toLong)
    println((u*modinv(v))%mod);
}

5. Ashish and Holidays (ASHISH)

Problem Setter: hackcyborg

Problem Link : https://www.codechef.com/MYL2020/problems/ASHISH

Explanation:
In this problem you have to iterate in whole matrix and see if it is already visited or barren land.if it is not then use dfs or bfs to calculate total sum of all connected cells also mark cells visited while iterating through dfs or bfs and store the value and sort them and take sum of last k values if there are more than k component else take sum of all components which will be our final answer.

Solution:

import java.util.Scanner;
import scala.util.control.Breaks._
object Main extends App {
    def sortTraditionl(xs: Array[Long]) {
    def swap(i: Int, j: Int) {
      val t = xs(i);
      xs(i) = xs(j);
      xs(j) = t;
    }

    def sort1(l: Int, r: Int) {
      val pivot = xs((l + r) / 2)
      var i = l;
      var j = r;
      while (i <= j) {
        while (xs(i) < pivot) i += 1
        while (xs(j) > pivot) j -= 1
        if (i <= j) {
          swap(i, j)
          i += 1
          j -= 1
        }
      }
      if (l < j) sort1(l, j)
      if (j < r) sort1(i, r)
    }
    sort1(0, xs.length - 1)
  }
var scanner = new Scanner(System.in);
var n=scanner.nextInt();
var m=scanner.nextInt();
var k=scanner.nextInt();
var a=Array.ofDim[Long](n,m)
var b=Array.ofDim[Int](n,m)
var ans : Array[Long] = new Array[Long]((2*n*m));
var su=0L
def dfs (i:Int,j:Int) : Int = {
   b(i)(j)=1;
   if(a(i)(j)==(-1L))
   return 0
   su=su+a(i)(j)
   if(i>0 && b(i-1)(j)==0)
   {
    dfs(i-1,j)
   }
   if(i<n-1 && b(i+1)(j)==0)
   {
       dfs(i+1,j)
   }
   if(j>0 && b(i)(j-1)==0)
   {
       dfs(i,j-1)
   }
   if(j<m-1 && b(i)(j+1)==0)
   {
       dfs(i,j+1)
   }
   return 0
}
   var l=2*n*m
   for(i <- 0 to n-1)
    {
        for(j <- 0 to m-1)
        {
            a(i)(j)=scanner.nextLong();
            b(i)(j)=0
        }
    }
    for(i <- 0 to l-1)
    {
       ans(i)=0L
    }
    var g=0
    for(i <- 0 to n-1)
    {
        for(j <- 0 to m-1)
        {
            if(b(i)(j)==0 && a(i)(j)!=(-1L))
              { su=0L
                 dfs(i,j)
                 ans(g)=su
                  g=g+1
              }
        }
    }
    var ti=0L
    sortTraditionl(ans)
    breakable
    {
        for(i <-  l-1 to 0 by -1)
        { 
            k=k-1
            ti=ti+ans(i)
            if(k==0)
            break
        }
    }
        println(ti);
}

6. A Game of Palindromes (GAMP)

Problem Setter: hackcyborg

Problem Link : https://www.codechef.com/MYL2020/problems/GAMP

Explanation:
This Problem Can be easily solved using bitmasking and dp.We will use sparge-grundy theorem to solve question use can read about it here(https://cp-algorithms.com/game_theory/sprague-grundy-nim.html).First we will calculate Grundy number of each string separately then we will xor of Grundy value in order to reach our answer.In oder to calculate grundy value first take bitmask of 0 to (2^10)-1 in which ‘i’-th bit will tell you that number ‘i’ is present in string or not then check if such a mask can be formed by the string after remove 0 or more numbers then check if the string is palindrome.if it is a palindrome then grundy value will be 0 else grundy value will be the mex of all the grundy values of the sub-masks in which exactly one ON bit of original mask is OFF.In this way you can calculate grundy values of all the strings.

Solution:

import java.util.Scanner;
import scala.util.control.Breaks._
object Main extends App {
    var scanner = new Scanner(System.in);
    var n=scanner.nextInt();
	var s : Array[String] = new Array[String](n);
	def checkup (i:Int, e:Int) : Boolean = {
    val g=new StringBuilder("")
    var f = s(i).length();
    for(x<-0 to f-1)
    {
        var d=(s(i)(x))-('0')
        if((e&(1<<d))>0)
               g+=s(i)(x)
    }
    var w=true
    var r=g.length()
    for(x<-0 to r-1)
    {
        if(g(x)!=g(r-x-1))
            w=false
    }
    return w;
  }
	for(i <- 0 to n-1)
	{
	    s(i)=scanner.next();
	}
   	var g=1024
	var r=0
	for(x <- 0 to n-1)
	{
	    var gi=0
	    var ti=s(x).length()
	    for(i <- 0 to ti-1)
	    {
	        var f=s(x)(i)-'0'
	        gi=gi|(1<<f)
	    }
	    var grundy : Array[Int] = new Array[Int](g);
	    for( y<- 0 to g-1)
	    {
	        if((gi|y)==gi)
	        {
	            if(checkup(x,y))
	              grundy(y)=0
	            else
	            {
	                var ar : Array[Boolean] = new Array[Boolean](12);
	                for(j<-0 to 11)
	                  ar(j)=false;
	                for(j <- 0 to 9)
	                {
	                    if((y&(1<<j))>0)
	                      ar(grundy(y^(1<<j)))=true 
	                }
	                var d=0
	         breakable
            {   for(it <- 0 to 9)
	            {
	                if(ar(it))
	                d+=1
	                else
	                break
	            }
	        }
	        grundy(y)=d
	            }
	        }
	    }
	    r=r^grundy(gi)
	}
	if(r!=0)
	println("Merlin")
	else
	println("Arthur")
}

1 Like