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:
- 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 : CodeChef: Practical coding for everyone
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 : CodeChef: Practical coding for everyone
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 : CodeChef: Practical coding for everyone
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(Sprague-Grundy theorem. Nim - Algorithms for Competitive Programming).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")
}