Codeforces Round #116 (Div. 2, ACM-ICPC Rules), E. Cubes

Codeforces Round #116 (Div. 2, ACM-ICPC Rules)
Problem E. Cubes

Problem statement:
http://codeforces.com/problemset/problem/180/E

First, we define an array of lists where each element contains the list of the cube indexes, for example:

    List<int>[] colorIndex = new List<int>[m + 1];

Since the number of colors is m <= 10^5, and the total number of cubes is n <= 2.10^5, we could make a fixed size array of (m+1). The space needed will be O(n+m).

Let's see for this input:
10 3 2
1 2 1 1 3 2 1 1 2 2

n=10, m=3, k=2

We could see it as a table of:
Index: 0 1 2 3 4 5 6 7 8 9
Color: 1 2 1 1 3 2 1 1 2 2

Then contents of the array colorIndex will be:
    colorIndex[0]: null

    colorIndex[1]: {0,2,3,6,7}

    colorIndex[2]: {1,5,8,9}

    colorIndex[3]: {4}

The codes will be something like:
            for ( int i = 0; i < n; i++ )
            {
                int clr = c[i];
                if ( colidx[clr] == null )
                    colidx[clr] = new List<int> ( );
                colidx[clr].Add ( i );

            }

Then we could calculate the score for each color by using 2 pointers: the first one points to the start of a sequence, and the second one points to the end of the sequence. Let's call them iStart and iEnd.

For example, if we look at color #1, where the indexes are {0,2,3,6,7}.
First we will set iStart and iEnd to 0.
Then we shift iEnd to the right repeatedly until the number of cubes needed to remove is greater than k, or until the end of the list.
In each iteration we could calculate the score of color #1 (the number of cubes with color #1) as:

    score = iEnd - iStart + 1;

The total number of cubes (all colors included) between iStart and iEnd, inclusive, is:

    numAllCubes = colidx[col][iend] - colidx[col][istart] + 1;

Then we calculate the number of cubes with different color that we need to remove as:

    numCubesToDelete = numAllCubes - score;

As long as numCubesToDelete <= k, the score is valid and we could update the maximum score with the current score.
Once numCubesToDelete > k, the score is not valid anymore and we need to shift the left pointer, iStart, to the right, by increasing its value by 1.
Then we calculate again the value of score, numAllCubes, and numCubesToDelete, and update the maximum score as needed.

Codeforces Round #209 (Div. 2) A Table

// Codeforces Round #209 (Div. 2) A Table
// Problem: http://codeforces.com/contest/359/problem/A

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
int m = in.nextInt();
int ans = 4;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
int x = in.nextInt();
if (i == 0 && j == 0)
continue;
if (i == 0 && j == m - 1)
continue;
if (i == n - 1 && j == 0)
continue;
if (i == n - 1 && j == m - 1)
continue;
if (x == 1)
if (i == 0 || j == 0 || i == n - 1 || j == m - 1)
ans = 2;
}
}
out.println(ans);
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(
new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #208 (Div. 2) B Dima and Text Messages

// Codeforces Round #208 (Div. 2) B Dima and Text Messages
// Problem: http://codeforces.com/contest/358/problem/B

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
String[] s = new String[n];
for (int i = 0; i < s.length; i++) {
s[i] = in.nextLine();
}
String msg = in.nextLine();
int pos = -1;
boolean failed = false;
for (int i = 0; i < s.length; i++) {
pos = msg.indexOf("<", pos + 1);
if (pos == -1) {
failed = true;
break;
}
pos = msg.indexOf("3", pos + 1);
if (pos == -1) {
failed = true;
break;
}
for (int j = 0; j < s[i].length(); j++) {
pos = msg.indexOf(s[i].charAt(j), pos + 1);
if (pos == -1) {
failed = true;
break;
}
}
if (pos == -1) {
failed = true;
break;
}
}
if (!failed) {
pos = msg.indexOf("<", pos + 1);
if (pos == -1) {
failed = true;
}
if (!failed) {
pos = msg.indexOf("3", pos + 1);
if (pos == -1) {
failed = true;
}
}
}
if (failed)
out.println("no");
else
out.println("yes");
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(
new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #208 (Div. 2) A Dima and Continuous Line

// Codeforces Round #208 (Div. 2) A Dima and Continuous Line
// Problems: http://codeforces.com/contest/358/problem/A

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
int[] x = new int[n];
for (int i = 0; i < x.length; i++) {
x[i] = in.nextInt();
}
boolean intersect = false;
for (int i = 0; i < n - 1; i++) {
int iL = Math.min(x[i], x[i + 1]);
int iR = Math.max(x[i], x[i + 1]);
for (int j = 0; j < n - 1; j++) {
int jL = Math.min(x[j], x[j + 1]);
int jR = Math.max(x[j], x[j + 1]);
if (i == j)
continue;
if (jL > iL && jL < iR && jR > iR)
intersect = true;
if (jL < iL && jR > iL && jR < iR)
intersect = true;
if (intersect)
break;
}
if (intersect)
break;
}
if (intersect)
out.println("yes");
else
out.println("no");
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(
new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #207 (Div. 2) B Flag Day

// Codeforces Round #207 (Div. 2) B Flag Day
// Problem: http://codeforces.com/contest/357/problem/B

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int n = in.nextInt();
int m = in.nextInt();
int[][] dance = new int[m][3];
for (int i = 0; i < m; i++) {
dance[i][0] = in.nextInt();
dance[i][1] = in.nextInt();
dance[i][2] = in.nextInt();
}
int[] color = new int[n + 1];
for (int i = 0; i < m; i++) {
int d1 = dance[i][0];
int d2 = dance[i][1];
int d3 = dance[i][2];
boolean[] colorused = new boolean[3];
for (int j = 0; j < 3; j++) {
colorused[j] = (color[d1] == j + 1 || color[d2] == j + 1 || color[d3] == j + 1);
}
for (int j = 0; j < 3; j++) {
if (color[dance[i][j]] == 0) {
for (int k = 0; k < 3; k++) {
if (!colorused[k]) {
color[dance[i][j]] = k + 1;
colorused[k] = true;
break;
}
}
}
}
}
StringBuilder sb = new StringBuilder();
for (int i = 1; i <= n; i++) {
if (i > 1)
sb.append(" ");
sb.append(color[i]);
}

out.println(sb);
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(
new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #207 (Div. 2) A Group of Students

// Codeforces Round #207 (Div. 2) A Group of Students
// Problem: http://codeforces.com/contest/357/problem/A

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
 private static MyScanner in;
 private static PrintStream out;
 private static boolean LOCAL_TEST = false;

 private static void solve() throws IOException
 {
  int m = in.nextInt();
  int[] c = new int[m + 1];
  int[] cum = new int[m + 1];
  int total = 0;
  for (int i = 1; i <= m; i++) {
   c[i] = in.nextInt();
   total += c[i];
   cum[i] = total;
  }
  int x = in.nextInt();
  int y = in.nextInt();
  for (int k = 2; k <= m; k++) {
   int lessThanK = cum[k - 1];
   int kOrHigher = total - lessThanK;
   if (lessThanK >= x && lessThanK <= y &&
     kOrHigher >= x && kOrHigher <= y) {
    out.println(k);
    return;
   }
  }
  out.println(0);
 }

 public static void main(String[] args) throws IOException {
  // helpers for input/output
  out = System.out;
  try {
   String cname = System.getenv("COMPUTERNAME");
   if (!cname.equals(""))
    LOCAL_TEST = true;
  } catch (Exception e) {
  }
  if (LOCAL_TEST) {
   in = new MyScanner("E:\\zin.txt");
  }
  else {
   boolean usingFileForIO = false;
   if (usingFileForIO) {
    // using input.txt and output.txt as I/O
    in = new MyScanner("input.txt");
    out = new PrintStream("output.txt");
   }
   else {
    in = new MyScanner();
    out = System.out;
   }
  }

  solve();
 }

 // =====================================
 static class MyScanner {
  BufferedReader bufReader;
  StringTokenizer strTok;

  public MyScanner() throws IOException
  {
   bufReader = new BufferedReader(new InputStreamReader(System.in));
   strTok = new StringTokenizer("");
  }

  public MyScanner(String inputFile) throws IOException {
   bufReader = new BufferedReader(new InputStreamReader(
     new FileInputStream(
       inputFile)));
   strTok = new StringTokenizer("");
  }

  String GetNextToken() throws IOException {
   if (!strTok.hasMoreTokens())
    strTok = new StringTokenizer(bufReader.readLine());
   return strTok.nextToken();
  }

  public int nextInt() throws IOException {
   return Integer.valueOf(GetNextToken());
  }

  public long nextLong() throws IOException {
   return Long.valueOf(GetNextToken());
  }

  public double nextDouble() throws IOException {
   return Double.valueOf(GetNextToken());
  }

  public String nextString() throws IOException {
   return GetNextToken();
  }

  public String nextLine() throws IOException {
   return bufReader.readLine();
  }

  public int countTokens() {
   return strTok.countTokens();
  }

  public boolean hasMoreTokens() {
   return strTok.hasMoreTokens();
  }
 }

}

Codeforces Round #206 (Div. 2) A Vasya and Digital Root

// Codeforces Round #206 (Div. 2) A Vasya and Digital Root
// Problem: http://codeforces.com/contest/355/problem/A

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

private static void solve() throws IOException
{
int k = in.nextInt();
int d = in.nextInt();
if (k == 1)
out.println(d);
else {
if (d == 0)
out.println("No solution");
else {
StringBuilder sb = new StringBuilder();
sb.append("1");
for (int i = 1; i < k - 1; i++) {
sb.append("0");
}
sb.append((d - 1));
out.println(sb);
}
}
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(
new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}

Codeforces Round #241 (Div. 2) C Booking System

// Codeforces Round #241 (Div. 2) C Booking System
// Problem: http://codeforces.com/contest/416/problem/C

import java.io.*;
import java.math.*;
import java.util.*;

import org.omg.CORBA.Environment;

//Codeforces
public class MainCodeforces1 {
private static MyScanner in;
private static PrintStream out;
private static boolean LOCAL_TEST = false;

public static class Visitor {
public int Size;
public int Money;
public int Index;
}

public static class VisComp implements Comparator<Visitor> {
@Override
public int compare(Visitor o1, Visitor o2) {
if (o1.Money == o2.Money)
return o1.Size - o2.Size;
else
return o2.Money - o1.Money;
}
}

public static class Table {
public int Index;
public int Size;
}

public static class TableComp implements Comparator<Table> {
@Override
public int compare(Table o1, Table o2) {
return o1.Size - o2.Size;
}
}

private static void solve() throws IOException
{
MainCodeforces1 main = new MainCodeforces1();
int nReq = in.nextInt();
ArrayList<Visitor> vis = new ArrayList<MainCodeforces1.Visitor>();
for (int i = 0; i < nReq; i++) {
Visitor v = new Visitor();
v.Size = in.nextInt();
v.Money = in.nextInt();
v.Index = i + 1;
vis.add(v);
}
Collections.sort(vis, new VisComp());
for (int i = 0; i < vis.size(); i++) {
// out.println("" + vis.get(i).Money + " - " + vis.get(i).Size);
}

int kTables = in.nextInt();
ArrayList<Table> tables = new ArrayList<MainCodeforces1.Table>();
boolean[] tblFilled = new boolean[kTables];
for (int i = 0; i < kTables; i++) {
Table tbl = new Table();
tbl.Index = i + 1;
tbl.Size = in.nextInt();
tables.add(tbl
);
}
Collections.sort(tables, new TableComp());

ArrayList<String> str = new ArrayList<String>();
int nAccepted = 0;
int sum = 0;
for (int i = 0; i < vis.size(); i++) {
Visitor v = vis.get(i);
for (int j = 0; j < tblFilled.length; j++) {
Table t = tables.get(j);
if (!tblFilled[j] && t.Size >= v.Size) {
nAccepted++;
sum += v.Money;
tblFilled[j] = true;
str.add("" + v.Index + " " + t.Index);
break;
}
}
}

out.println("" + nAccepted + " " + sum);
for (String s : str) {
out.println(s);
}
}

public static void main(String[] args) throws IOException {
// helpers for input/output
out = System.out;
try {
String cname = System.getenv("COMPUTERNAME");
if (!cname.equals(""))
LOCAL_TEST = true;
} catch (Exception e) {
}
if (LOCAL_TEST) {
in = new MyScanner("E:\\zin.txt");
}
else {
boolean usingFileForIO = false;
if (usingFileForIO) {
// using input.txt and output.txt as I/O
in = new MyScanner("input.txt");
out = new PrintStream("output.txt");
}
else {
in = new MyScanner();
out = System.out;
}
}

solve();
}

// =====================================
static class MyScanner {
BufferedReader bufReader;
StringTokenizer strTok;

public MyScanner() throws IOException
{
bufReader = new BufferedReader(new InputStreamReader(System.in));
strTok = new StringTokenizer("");
}

public MyScanner(String inputFile) throws IOException {
bufReader = new BufferedReader(new InputStreamReader(
new FileInputStream(
inputFile)));
strTok = new StringTokenizer("");
}

String GetNextToken() throws IOException {
if (!strTok.hasMoreTokens())
strTok = new StringTokenizer(bufReader.readLine());
return strTok.nextToken();
}

public int nextInt() throws IOException {
return Integer.valueOf(GetNextToken());
}

public long nextLong() throws IOException {
return Long.valueOf(GetNextToken());
}

public double nextDouble() throws IOException {
return Double.valueOf(GetNextToken());
}

public String nextString() throws IOException {
return GetNextToken();
}

public String nextLine() throws IOException {
return bufReader.readLine();
}

public int countTokens() {
return strTok.countTokens();
}

public boolean hasMoreTokens() {
return strTok.hasMoreTokens();
}
}

}