Codechef 2019 Challenge java solutions

Codechef 2019 Challenge java solutions

January Challenge

Chef and Modulo Game

https://www.codechef.com/problems/MGAME

Chef is playing a game with two of his friends. In this game, each player chooses an integer between 11 and PP inclusive. Let’s denote the integers chosen by Chef, friend 1 and friend 2 by ii, jj and kk respectively; then, Chef’s score is(((Nmodi)modj)modk)modN.(((Nmodi)modj)modk)modN.

Chef wants to obtain the maximum possible score. Let’s denote this maximum score by MM. Find the number of ways to choose the triple (i,j,k)(i,j,k) so that Chef’s score is equal to MM.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains two space-separated integers NN and PP.

Output

For each test case, print a single line containing one integer — the number of ways to obtain the maximum score.

Constraints

  • 1≤T≤1061≤T≤106
  • 1≤N≤P≤1061≤N≤P≤106

Subtasks

Subtask #1 (10 points):

  • 1≤T≤1001≤T≤100
  • 1≤N≤P≤1001≤N≤P≤100

Subtask #2 (90 points): original constraints

Example Input

2 4 4 3 4

Example Output

9 13

Explanation

Example case 1: Chef’s maximum possible score is M=1M=1. All possible values of (i,j,k)(i,j,k) such that the score is 11 are (3,2,2)(3,2,2), (3,2,3)(3,2,3), (3,2,4)(3,2,4), (3,3,2)(3,3,2), (3,3,3)(3,3,3), (3,3,4)(3,3,4), (3,4,2)(3,4,2), (3,4,3)(3,4,3), (3,4,4)(3,4,4).

Solution:

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be “Main” only if the class is public. */
class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
// your code goes here

BufferedReader r = new BufferedReader(new InputStreamReader(System.in));

int t1 = Integer.parseInt(r.readLine());

while(t1– > 0)
{
String k = r.readLine();
String data[] = k.split(” “,2);
long n = Long.parseLong(data[0]);
long p = Long.parseLong(data[1]);

// System.out.println(n);
// System.out.println(p);

long m=0;
m= (n-1)/2;
// m= n%((n/2)+1);
long num_ways =0;
//System.out.println(m);
if(n <=2)
System.out.println(p*p*p);
else if(n ==p)
{
// one way to select i which gives max modulous
// j , k can be any value between m & P which will not change modulous

num_ways+= 1 *(p-m) * (p-m);

System.out.println(num_ways);


}
else
{
//case 1
// select i > n , j one way , k will be left with (p-m)
num_ways+= (p-n)*1 * (p-m);

// System.out.println(num_ways);
// case 2

// select i > n , j > n , k=1
num_ways+= (p-n)*(p-n)*1;

// System.out.println(num_ways);

// case 3
// select i=1 , j/k as (p-m)
num_ways += 1* (p-m)*(p-m);

System.out.println(num_ways);
}
}


}
}

February Challenge

Deputy Chef

https://www.codechef.com/FEB19B/problems/DEPCHEF

A battle is going to begin in the kingdom of Airland. There are NN soldiers in the kingdom, numbered 11 through NN and standing in a circle in such a way that for each valid ii, the soldier directly to the right of the ii-th soldier is soldier i+1i+1, and the soldier directly to the right of the NN-th soldier is soldier 11.

Each soldier holds a sword and a shield. The sword is used to attack other soldiers and the shield is used to defend from attacks. Let’s denote the attack value of the ii-th soldier’s sword by aiai and the defense value of the ii-th soldier’s shield by didi.

In the battle, each soldier picks one of the soldiers standing to his left and right, and attacks that soldier. The choices of the soldiers are completely independent, so each soldier can be attacked by the soldier to his left, by the soldier to his right (the power of such an attack is the attack value of the attacking soldier’s sword), by both of them (then, the power of the resulting attack is the sum of the attack values of these soldiers’ swords) or by nobody. A soldier remains alive if the defense value of his shield is strictly greater than the power with which he is attacked. Everyone attacks simultaneously and there is only one round of attacks. Each soldier that remains alive at the end is awarded a laurel.

The king of Airland likes these fights, so the host of the battle promised the king that he can pick one soldier and if the soldier he picks survives the battle, the king receives the shield of that soldier.

Chef is the deputy of the king and you want to help him pick a soldier for the king in such a way that the king receives the best shield (with the greatest defense value). However, if Chef picks a soldier and that soldier does not survive, Chef will be thrown in a snake pit. Therefore, it should be guaranteed that the chosen soldier will survive regardless of the decisions of the other soldiers.

Can you help Chef make the best choice and tell him the defense value of the shield which the king gets, or decide that he can be thrown in the snake pit no matter which soldier he picks?

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first line of each test case contains a single integer NN.
  • The second line contains NN space-separated integers a1,a2,…,aNa1,a2,…,aN.
  • The third line contains NN space-separated integers d1,d2,…,dNd1,d2,…,dN.

Output

For each test case, print a single line containing one integer ― the best defense value of the shield the king gets, or −1−1 if Chef can be thrown in the snake pit.

Constraints

  • 1≤T≤1001≤T≤100
  • 3≤N≤1003≤N≤100
  • 1≤ai,di≤1041≤ai,di≤104 for each valid ii

Subtasks

Subtask #1 (100 points): original constraints

Example Input

[sourcecode language=”csharp”] 2 4 1 1 4 1 3 4 2 1 7 5 4 5 4 5 4 5 3 2 4 7 2 5 9 [/sourcecode]

Example Output

[sourcecode language=”csharp”] 3 -1 [/sourcecode]

Explanation

Example case 1: Soldier 11 can be attacked by soldier 22 and/or soldier 44. If only soldier 22 attacks him, the power of the attack is 11. If only soldier 44 attacks him, the power of the attack is 11 again. If they attack together, the power of the attack is 22. In each of these cases, soldier 11 will live.

Soldier 22 can be attacked by soldier 33, with attack power 44. His shield has defense value 44, which is not enough, so in this case, soldier 22 would die. The best safe choice is soldier 11, with defense value 33.

Example case 2: No soldier is guaranteed to survive the battle, so the answer is −1.

Solution

[sourcecode language=”java”]

/* package codechef; // don’t place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

import java.util.HashMap;

class DEPCHEF {
public static void main(String[] args) throws java.lang.Exception {
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
int t1 = Integer.parseInt(r.readLine().toString());
while (t1– > 0) {
int n = Integer.parseInt(r.readLine().toString());
HashMap<character, integer=””> hm = new HashMap<>();
int count = 0;
String k = r.readLine();
String a[] = k.split(” “,n);
String l = r.readLine();
String d[] = l.split(” “,n);
int max = 0;</character,>

// if(Integer.parseInt(d[0]) > Integer.parseInt(a[n-1]) ||
// Integer.parseInt(d[0]) > Integer.parseInt(a[1]) ||
if( Integer.parseInt(d[0]) >(Integer.parseInt(a[n-1]) + Integer.parseInt(a[1])) )
{
if(Integer.parseInt(d[0]) > max)
max = Integer.parseInt(d[0]);

}

for(int i =1 ; i < n ; i++) { // if(Integer.parseInt(d[i]) > Integer.parseInt(a[i-1]) ||
// Integer.parseInt(d[i]) > Integer.parseInt(a[(i+1)%n]) ||
if(Integer.parseInt(d[i]) >(Integer.parseInt(a[i-1]) + Integer.parseInt(a[(i+1)%n])) )
{
if(Integer.parseInt(d[i]) > max)
max = Integer.parseInt(d[i]);

}
}
if(max !=0)
System.out.println(max);
else
System.out.println(-1);
}
}
}

[/sourcecode]

Appy and Contest 

Appy and Chef are participating in a contest. There are NN problems in this contest; each problem has a unique problem code between 11 and NN inclusive. Appy and Chef decided to split the problems to solve between them ― Appy should solve the problems whose problem codes are divisible by AA but not divisible by BB, and Chef should solve the problems whose problem codes are divisible by BB but not divisible by AA (they decided to not solve the problems whose codes are divisible by both AA and BB).

To win, it is necessary to solve at least KK problems. You have to tell Appy whether they are going to win or lose.

Input

  • The first line of the input contains a single integer TT denoting the number of test cases. The description of TT test cases follows.
  • The first and only line of each test case contains four space-separated integers NN, AA, BB and KK.

Output

For each test case, print a single line containing the string "Win" if they can solve at least KK problems or "Lose" otherwise (without quotes).

Constraints

  • 1≤T≤151≤T≤15
  • 1≤KN≤10181≤K≤N≤1018
  • 1≤A,B≤1091≤A,B≤109

Subtasks

Subtask #1 (15 points):

  • 1≤T≤151≤T≤15
  • 1≤KN≤1061≤K≤N≤106
  • 1≤A,B≤1031≤A,B≤103

Subtask #2 (85 points): original constraints

Example Input

[sourcecode language=”java”]

1 6 2 3 3

[/sourcecode]

Example Output

[sourcecode language=”java”]
Win
[/sourcecode]

Explanation

Example case 1: Appy is solving the problems with codes 22 and 44, Chef is solving the problem with code 33. Nobody is solving problem 66, since 66 is divisible by both 22and 33. Therefore, they can solve 33 problems and win.

Solution in java :

[sourcecode language=”java”]
/* package codechef; // don’t place package name! */
import java.util.; import java.lang.;
import java.io.*;
import java.math.BigDecimal;
import java.math.BigInteger;

class HMAPPY2 {
static int i=1;
public static BigInteger lcm(String a, String b)
{
// convert string ‘a’ and ‘b’ into BigInteger
BigInteger s = new BigInteger(a);
BigInteger s1 = new BigInteger(b);

// calculate multiplication of two bigintegers
BigInteger mul = s.multiply(s1);

// calculate gcd of two bigintegers
BigInteger gcd = s.gcd(s1);

// calculate lcm using formula: lcm * gcd = x * y
BigInteger lcm = mul.divide(gcd);
return lcm;

public static void main(String[] args) throws java.lang.Exception {
java.io.BufferedReader r = new java.io.BufferedReader(
new java.io.InputStreamReader(System.in));
int t1 = Integer.parseInt(r.readLine().toString());
while (t1– > 0)

{

String k = r.readLine();
i=1;
String a[] = k.split(” “, 4);
BigInteger b = new BigInteger(a[0]).divide(new BigInteger(a[1]));
BigInteger c = new BigInteger(a[0]).divide(new BigInteger(a[2]));
BigInteger d = new BigInteger(a[0]).divide(lcm(a[1],(a[2])));

BigInteger e = b.add(c).subtract(d.multiply(new BigInteger(“2”)));
if(e.subtract(new BigInteger(a[3])).compareTo(new BigInteger(“0”))== 0 ||
e.subtract(new BigInteger(a[3])).compareTo(new BigInteger(“0”))== 1)
System.out.println(“Win”);
else
System.out.println(“Lose”);

}

}

}

}


[/sourcecode]

Expression Processor :

[sourcecode language=”java”]
import java.io.*;
import java.lang.reflect.Type;
import java.text.ParseException;
import java.util.*;
import com.google.gson.Gson;
import com.google.gson.reflect.TypeToken;
import org.json.JSONObject;

//[“AND”,
// {“var1” : “value1”},
// [“OR”,
// { “var2” : “value2” },
// { “var3” : “value3” }
// ]
// ]

public class ExP {
// The function can be extended for n number of oprtators
public static String performOp(String optr , String s1 , String s2)
{
if(optr.equals(“AND”))
{
Boolean b = Boolean.parseBoolean(s1) && Boolean.parseBoolean(s2);
return b.toString() ;
}
else{ //OR operator
Boolean b = Boolean.parseBoolean(s1) || Boolean.parseBoolean(s2);
return b.toString() ;

}
}

public static String transform( Map expMap)
{
Stack orandS = new Stack<>();
for(String optr : expMap.keySet()) //oprator is always key
{
Object jA=expMap.get(optr);
for(int i=0 ; i <((ArrayList)jA).size();i++) { Object s= ((ArrayList)jA).get(i); // Instead of boolean , conditions like x > y can be given,
// for that cdde can be modifed
if(s.toString().equals(“true”) || s.toString().equals(“false”))
{
if(orandS.size() > 0 ) {
String s1= orandS.peek();
orandS.pop();
orandS.push(performOp(optr,s.toString(),s1));
}
else
orandS.push(s.toString());
}
else
{
Gson gson = new Gson();
Type type = new TypeToken>(){}.getType();
Map myMap = gson.fromJson(s.toString(), type);

orandS.push(transform(myMap));

}

}

}
return orandS.peek();
}

public static void pritnt(String jsonObject) throws IOException, ParseException {
// Parse a JsonObject into a JSON string
StringWriter stringWriter = new StringWriter();
String json = “”;
Reader inputString = new StringReader(jsonObject);
BufferedReader br = new BufferedReader(inputString);
String line;
StringBuilder builder=new StringBuilder();
while ((line = br.readLine()) != null) {
builder.append(line);

}
Gson gson = new Gson();
Type type = new TypeToken>(){}.getType();
Map myMap = gson.fromJson(builder.toString(), type);

Map ob = (Map ) myMap.get(“e”);
// Parse a JSON string into a JsonNode
JSONObject js = new JSONObject(jsonObject);
Iterator keys = js.keys();
StackoprS = new Stack<>();
StackorandS=new Stack<>();

while(keys.hasNext()) {
String key = keys.next();
Object jso= js.get(key);
Map expMap = gson.fromJson(jso.toString(), type);
System.out.println(transform(expMap));

}

}

public static void main (String[] args) throws ParseException,IOException
{

// Code can be modified to check x > 7 instead of sample boolean values
// String jo = “{\n” +
// “\t\”e\”: {\n” +
// “\t\t\”AND\”: [\”x > y\”,\n” +
// “\t\t\t\”y > 7 \”,\n” +
// “\t\t\t{\n” +
// “\t\t\t\t\”OR\”: [\”x > y\”,\n” +
// “\t\t\t\t\t\”y > 7 \”\n” +
// “\t\t\t\t]\n” +
// “\t\t\t}\n” +
// “\n” +
// “\t\t]\n” +
// “\n” +
// “\t}\n” +
// “}”;
// Can be mock tested for any level of nesting
String jo = “{\n” +
“\t\”e\”: {\n” +
“\t\t\”AND\”: [\”true\”, \”true\”,\n” +
“\t\t\t{\n” +
“\t\t\t\t\”OR\”: [\”false\”, \”false\”]\n” +
“\t\t\t}\n” +
“\t\t]\n” +
“\t}\n” +
“}”;
pritnt(jo);
}
}
[/sourcecode]