Assalamualaikum everyone. A couple of weeks ago, I got a copy of PROMED 2012 questions and dataset. I’m not exactly sure what is PROMED, but it seems that it is like ACM ICPC national level, but not the official national level for Malaysia. Anyway, I got hold of it, and after some time, I manage to answer them all.

Generally, I would put this kind of problem analysis in iiumicpcteam.com . However, considering that this have almost nothing to do with IIUM, I don’t think it is proper for me to put this in that blog. Otherwise, iiumicpcteam.com would be like my personal blog. That is why you are reading this on my personal blog. Also, regarding the question and the dataset, I was told to put a citation for UITM Perak. So thank you UITM Perak for releasing the dataset. There are 9 question in total. Here are the dataset and question:

Also, this time, I will not remove my template, because I’m lazy. Also, I won’t put too much comment, because of the same reason. So with that in mind, lets get started with the questions.

A. P-LOCK

This question is a straight implementation. No trick detected.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

// To enable debugging macro, when compiling with g++ use the parameter -DDEBUG
#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cerr << msg << endl;
#define var(v) cerr << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cerr << msg << endl;
#define var(v) //cerr << #v << " = " << v << endl;
#endif

bool solve(){
string line;
getline(cin,line);

// var is debugging macro
var(line);

bool done[26];

// REP is a loop macro
REP(i,26) done[i] = false;

int size = line.size();

// Beware of different between Unix and Windows endline
if(line[size-1] == ‘\r’){
size–;
}

// To small
if(size < 3){
return false;
}

bool ok = true;
REP(i,size){

char c = line[i];
if(c >= ‘A’ && c <= ‘Z’){
if(done[c-‘A’]){
ok = false;
dbgp("NOTOK");
var(c);
break;
}else{
done[c-‘A’] = true;
}
}else{
ok = false;
dbgp("NOTOK");
var(c);
break;
}

}

return ok;
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t;
cin >> t;

// Due to problem reading line
// This is needed before getline
cin.ignore(100,’\n’);

REP(i,t){
if(solve()){
printf("Case #%lld: VALID\n",i+1);
}else{
printf("Case #%lld: INVALID\n",i+1);
}
}

return 0;
}
[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static boolean solve(){
String line = in.nextLine();
err.println("Line is "+line);

if(line.length() < 3){
return false;
}

boolean done[] = new boolean[26];
for(int i=0;i<done.length;i++){
done[i] = false;
}

boolean ok = true;
for(char c: line.toCharArray()){
if(c >= ‘A’ && c <= ‘Z’){
if(done[c-‘A’]){
ok = false;
break;
}else{
done[c-‘A’] = true;
}
}else{
ok = false;
break;
}
}

return ok;
}

public static void main(String[] args){

int t = in.nextInt();

// Java has the same getline problem
in.nextLine();

for(int i=0;i<t;i++){
if(solve()){
out.println("Case #"+(i+1)+": VALID");
}else{
out.println("Case #"+(i+1)+": INVALID");
}
}
}
}
[/java]

B. THE MATRIC RELOADED!

This question is also a straightforward implementation. However, I think question is unclear and misleading. The output statement said to output “-1” if the data range is invalid. However, the question did not mention clearly how would it be considered invalid. And in the input declaration, it said that “Each test case contains a series of ones and zeros of length between 101 and 65534 inclusive.”. That is misleading, because each test case CAN have length outside the range. In fact the question did not specify the possible range of length of input. In could be 1 billion character, who knows. If the length is outside the range, THEN it is considered invalid.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#ifdef DEBUG
#define dbg(msg) msg
#define dbgp(msg) cerr << msg << endl;
#define var(v) cerr << #v << " = " << v << endl;
#else
#define dbg(msg) //msg
#define dbgp(msg) //cerr << msg << endl;
#define var(v) //cerr << #v << " = " << v << endl;
#endif

int solve(){
string s;
cin >> s;

ll size = s.size();

if(size < 101 || size > 65534){
return -1;
}

ll count = 0;
bool in_one = false;
REP(i,size){
char c=s[i];
if(c==’1′){
if(!in_one){
in_one = true;
count++;
}
}else{
if(in_one){
in_one = false;
}
}
}
return count;
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int n;
cin >> n;
REP(i,n){
printf("Case #%lld: %d\n",i+1,solve());
}

return 0;
}

[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static int solve(){
String s = in.next();
int size = s.length();

if(size < 101 || size > 65534){
return -1;
}

int count = 0;
boolean in_one = false;

for(int i=0;i<size;i++){
char c = s.charAt(i);
if(c==’1′){
if(!in_one){
in_one = true;
count++;
}
}else{
if(in_one){
in_one = false;
}
}
}
return count;

}

public static void main(String[] args){
int t = in.nextInt();

for(int i=0;i<t;i++){
out.println("Case #"+(i+1)+": "+solve());
}
}
}

[/java]

C. HAIL-FAST TAXI

This question is a bit challenging, but still relatively easy. Maybe a bit hard for those who are not familiar with what C++ or Java have to offer. But not as straightforward as previous question. The question involve finding the closest taxi from the customer. And, an implicit taxi location is at (0,0). The major reason to got a wrong verdict for this question is that, if there are more than one choice, there are specific priority on which taxi got the customer. My solution involve, sorting the taxi first based on the priority, then find the closest taxi.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

ll edistance(pii p1,pii p2){
return (p1.first-p2.first)*(p1.first-p2.first) + (p1.second-p2.second)*(p1.second-p2.second);
}

bool compare(pii p1,pii p2){
if(p1.second == p2.second){
return p1.first < p2.first;
}
return p1.second < p2.second;
}

void solve(){
pii customer;
cin >> customer.first >> customer.second;

set<pii,bool(*)(pii,pii)> taxis(compare);
while(true){
pii cur;
cin >> cur.first >> cur.second;
if(cur.first == 10001 && cur.second == 10001){
break;
}
taxis.insert(cur);
}

taxis.insert(MP(0,0));

pii closest = *taxis.begin();
var(closest.first);
var(closest.second);

ItREP(it,taxis){
pii cur = *it;
if(edistance(cur,customer) <= edistance(closest,customer)){
closest = cur;
}
}

printf("%d %d",closest.first,closest.second);

}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t;
cin >> t;
REP(i,t){
printf("Case %lld: ",i+1);
solve();
printf("\n");
}

return 0;
}

[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static class Point implements Comparable<Point>{
long x = 0;
long y = 0;

Point(){
}

Point(long x,long y){
this.x = x;
this.y = y;
}

@Override
public int compareTo(Point p){
if(y – p.y != 0){
return (int)(y – p.y);
}

if(x – p.x != 0){
return (int)(x – p.x);
}

return 0;
}

long distance(Point p){
return (x-p.x)*(x-p.x) + (y-p.y)*(y-p.y);
}
}

static void solve(){
Point customer = new Point(in.nextLong(),in.nextLong());

ArrayList<Point> taxis = new ArrayList<>();
while(true){
Point taxi = new Point(in.nextLong(),in.nextLong());
if(taxi.x == 10001 && taxi.y == 10001){
break;
}
taxis.add(taxi);
}
taxis.add(new Point(0,0));

Collections.sort(taxis);

Point closest = taxis.get(0);

for(Point taxi: taxis){
if(taxi.distance(customer) <= closest.distance(customer)){
closest = taxi;
}
}

out.print(""+closest.x+" "+closest.y);
}

public static void main(String[] args){
int t = in.nextInt();

for(int i=0;i<t;i++){
out.print("Case "+(i+1)+": ");
solve();
out.println();
}
}
}

[/java]

D. COUNTING SUBSEQUENCES

Ow, this is my favorite. It is hard. Among D and I which I think are the hardest, I like this more as I feel it is a bit new for me, hard, yet can be solved given enough thinking. The question involve counting how many common subsequence between two string. Sounds familiar? That is because it sounds like the famous longest common subsequence problem. My solution have a similar approach with the LCS dynamic programming solution, but instead of storing the longest subsequence at a particular state, it store the number of subsequence. The method is getting the value from smaller subproblem is also different. In a LCS algorithm, we consider the maximum between the upper, left and upper-left+1 (if the last character is the same) cell. In this counting solution, we consider the sum of the left and upper cell. Since the left and upper cell would both already contain the left-upper count (as they themselves consider left and upper of them) we would have a duplicate count of the upper-left cell. Therefore, we need to subtract the result in upper-left cell. This is the case when the last character is not the same. If the last character is the same, then we add one new subsequence, which is the character itself, plus all the upper-left subsequence appended with the new subsequence. As a result, we do not have to subtract the upper-left cell because we would add them back anyway. I’m not making much sense right? Yea, I know… It is a bit hard to understand. Most DP problem are. Maybe the following code can help.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

#define MOD 1000000003

ll dp[1010][1010];

ll solve(){
string s1;
string s2;
cin >> s1 >> s2;

// Just debugging
var(s1);
var(s1.size());
var(s2);
var(s2.size());

// Clear to 0
REP(i,s1.size()){
REP(i2,s2.size()){
dp[i][i2] = 0;
}
}

// Two loop
REP(i,s1.size()){
REP(i2,s2.size()){

if(i == 0){

// If on boundary but not on 0,0, use neighbour value as initial value
if(i2 == 0){
}else{
dp[i][i2] = dp[i][i2-1];
}

// If the character is the same, add one more subsequence
if(s1[i] == s2[i2]){
dp[i][i2] += 1;
}
dp[i][i2] %= MOD;

}else if(i2 == 0){

// Same thing as previous one, but different side
if(i == 0){
}else{
dp[i][i2] = dp[i-1][i2];
}

if(s1[i] == s2[i2]){
dp[i][i2] += 1;
}
dp[i][i2] %= MOD;

}else{

if(s1[i] == s2[i2]){
// If the character is the same,
// Add another subsequence
// And the number of subsequence onf i-1 and i2-1
// But since we are going to subtract it anyway, we just skip the subtraction
dp[i][i2] += 1;

// Count from above and side is added
dp[i][i2] %= MOD;
dp[i][i2] += dp[i-1][i2];
dp[i][i2] %= MOD;
dp[i][i2] += dp[i][i2-1];
dp[i][i2] %= MOD;

// Skip subtraction
//dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
//dp[i][i2] %= MOD;

}else{
// If the character is not the same,
// We add the number of subsequence above and on size
// But because both of them contain the number of subsequence from the diagonal i-1 and i2-1,
// We need to remove minus that.
// Remember the formula |A union B| = |A| + |B| – |A intersect B|

dp[i][i2] += dp[i-1][i2];
dp[i][i2] %= MOD;
dp[i][i2] += dp[i][i2-1];
dp[i][i2] %= MOD;

dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
dp[i][i2] %= MOD;
}
}

}
}

// Just debugging
dbg(
REP(i,s1.size()){
REP(i2,s2.size()){
cerr << dp[i][i2] << " ";
}
cerr << endl;
}
)

return (dp[s1.size()-1][s2.size()-1]+1)%MOD;
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;
REP(i,t){
printf("Case #%lld: %lld\n",i+1,solve());
}

return 0;
}

[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;
static long MOD = 1000000003;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static long solve(){
String s1 = in.next();
String s2 = in.next();

// Making the jagged array
long dp[][] = new long[s1.length()][];
for(int i=0;i<s1.length();i++){
dp[i] = new long[s2.length()];
Arrays.fill(dp[i],0);
}

// Two loop
for(int i=0;i<s1.length();i++){
for(int i2=0;i2<s2.length();i2++){

if(i == 0){

// If on boundary but not on 0,0, use neighbour value as initial value
if(i2 == 0){
}else{
dp[i][i2] = dp[i][i2-1];
}

// If the character is the same, add one more subsequence
if(s1.charAt(i) == s2.charAt(i2)){
dp[i][i2] += 1;
}
dp[i][i2] %= MOD;

}else if(i2 == 0){

// Same thing as previous one, but different side
if(i == 0){
}else{
dp[i][i2] = dp[i-1][i2];
}

if(s1.charAt(i) == s2.charAt(i2)){
dp[i][i2] += 1;
}
dp[i][i2] %= MOD;

}else{

if(s1.charAt(i) == s2.charAt(i2)){
// If the character is the same,
// Add another subsequence
// And the number of subsequence onf i-1 and i2-1
// But since we are going to subtract it anyway, we just skip the subtraction
dp[i][i2] += 1;

// Count from above and side is added
dp[i][i2] %= MOD;
dp[i][i2] += dp[i-1][i2];
dp[i][i2] %= MOD;
dp[i][i2] += dp[i][i2-1];
dp[i][i2] %= MOD;

// Skip subtraction
//dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
//dp[i][i2] %= MOD;

dp[i][i2] += dp[i-1][i2];
dp[i][i2] %= MOD;
dp[i][i2] += dp[i][i2-1];
dp[i][i2] %= MOD;

dp[i][i2] = MOD+dp[i][i2]-dp[i-1][i2-1];
dp[i][i2] %= MOD;
}
}

}
}

return (dp[s1.length()-1][s2.length()-1]+1)%MOD;
}

public static void main(String[] args){
int t = in.nextInt();

for(int i=0;i<t;i++){
out.println("Case #"+(i+1)+": "+solve());
}
}
}

[/java]

E. DASH PATTERN

Hmm, sounds like a straightforward implementation. But then you realize, it do not specify the number of dash pattern in the input. You need to get the whole line, then figure out the number of dash pattern yourself. Those who do not know the use of C++ sstringstream would have problem with this. For java solution, the String class have a built in splitter. Also, the number of dash pattern is not necessarily even like in the sample input. There can be only one number, or three.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

using namespace std;

void solve(){

string line;
getline(cin,line);

// How do we know if the line ended?
// With stringstream we can.
stringstream sin(line);

// Get the length
int length;
sin >> length;

vector<int> patterns;

// As long as the number still exist, add to patterns
int d;
while(sin >> d){
patterns.PB(d);
}

// Now print it out
int cur_pattern = 0;
printf("|");
while(length){
int cd = patterns[cur_pattern];

// In case we don’t have enough length
if(length < cd){
cd = length;
}
length -= cd;

REP(i,cd){
// If underscore or space?
if(cur_pattern%2 == 0){
printf("_");
}else{
printf(" ");
}
}

cur_pattern++;
cur_pattern = cur_pattern%patterns.size();
}
printf("|");

}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;

// Problem with getline
cin.ignore(100,’\n’);

REP(i,t){
printf("Case #%lld: ",i+1);
solve();
printf("\n");
}

return 0;
}
[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static void solve(){
String line = in.nextLine();

// We can easily split in Java
String splitted[] = line.split(" ");

// Then get it one by one
int length = Integer.parseInt(splitted[0]);
ArrayList<Integer> patterns = new ArrayList<Integer>();
for(int i=1;i<splitted.length;i++){
patterns.add(Integer.parseInt(splitted[i]));
}

// Now print it out
int cur_pattern = 0;
out.print("|");
while(length > 0){
int cd = patterns.get(cur_pattern);

// In case we don’t have enough length
if(length < cd){
cd = length;
}
length -= cd;

for(int i=0;i<cd;i++){
// If underscore or space?
if(cur_pattern%2 == 0){
out.print("_");
}else{
out.print(" ");
}
}

cur_pattern++;
cur_pattern = cur_pattern%patterns.size();
}
out.print("|");

}

public static void main(String[] args){
int t = in.nextInt();
in.nextLine();

for(int i=0;i<t;i++){
out.print("Case #"+(i+1)+": ");
solve();
out.println();
}
}
}

[/java]

F. LEGOLAND TICKETS

Straightforward implementation, nothing particularly interesting here. Move along…

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

using namespace std;

int solve(){
int n;
cin >> n;

int adult = 0, child = 0, elder = 0, voucher = 0;

REP(i,n){
int d;
cin >> d;
if(d <3){
//baby?
}else if(d < 12){
child++;
}else if(d < 60){
adult++;
}else{
elder++;
}
}

cin >> voucher;

child -= min(min(child,adult),voucher);

return adult*140 + child*110 + elder*110;
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;
REP(i,t){
printf("Case #%lld: RM%d.00\n",i+1,solve());
}

return 0;
}
[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static int solve(){
int n = in.nextInt();

int adult = 0, child = 0, elder = 0, voucher = 0;

for(int i=0;i<n;i++){
int d = in.nextInt();
if(d <3){
//baby?
}else if(d < 12){
child++;
}else if(d < 60){
adult++;
}else{
elder++;
}
}

voucher = in.nextInt();

child -= min(min(child,adult),voucher);

return adult*140 + child*110 + elder*110;
}

public static void main(String[] args){
int t = in.nextInt();
for(int i=0;i<t;i++){
out.println("Case #"+(i+1)+": RM"+solve()+".00");
}
}
}

[/java]

G. EVEN (OR ODD) WINS!

The hardest part in this question is probably, converting back the number to String. Oh wait, you don’t need to do so, you can loop and divide by 10. Hmm.. Did not think about that before. Still, if it works it works.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

using namespace std;

void solve(){
ll num;
cin >> num;
num = num*num*num;

// This is one way to convert it to string
stringstream ss;
ss << num;
string number;
ss >> number;

bool hasodd = false;
bool haseven = false;

REP(i,number.size()){
int n = number[i] – ‘0’;
if(n%2){
hasodd = true;
}else{
haseven = true;
}
}

if(hasodd && haseven){
printf("MIXED");
}else if(hasodd){
printf("ODD");
}else{
printf("EVEN");
}
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;

REP(i,t){
printf("Case #%lld: ",i+1);
solve();
printf("\n");
}

return 0;
}
[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

static void solve(){
long num = in.nextLong();
num = num*num*num;

// Convert to string
String number = Long.toString(num);

boolean hasodd = false;
boolean haseven = false;

// Iterate through all character
for(char c:number.toCharArray()){
int n = c – ‘0’;
if(n%2 == 1){
hasodd = true;
}else{
haseven = true;
}
}

if(hasodd && haseven){
out.print("MIXED");
}else if(hasodd){
out.print("ODD");
}else{
out.print("EVEN");
}
}

public static void main(String[] args){
int t = in.nextInt();
for(int i=0;i<t;i++){
out.print("Case #"+(i+1)+": ");
solve();
out.println();
}
}
}
[/java]

H. STRUCTURE OF WORD

I’d say, also a straightforward implementation. Check each character. Nothing special.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

using namespace std;

bool is_vowel(char c){
switch(c){
case ‘a’:
case ‘e’:
case ‘i’:
case ‘o’:
case ‘u’:
case ‘A’:
case ‘E’:
case ‘I’:
case ‘O’:
case ‘U’:
return true;
default:
return false;
}

}

bool solve(){
string s1,s2;
cin >> s1 >> s2;
if(s1.size() != s2.size()){
return false;
}

REP(i,s1.size()){
if(is_vowel(s1[i]) != is_vowel(s2[i])){
return false;
}
}

return true;
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;

REP(i,t){
if(solve()){
printf("Case #%lld: same\n",i+1);
}else{
printf("Case #%lld: different\n",i+1);
}
}

return 0;
}

[/cpp]

Java Solution

[java]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

using namespace std;

}

bool solve(){
string s1,s2;
cin >> s1 >> s2;
if(s1.size() != s2.size()){
return false;
}

REP(i,s1.size()){
if(is_vowel(s1[i]) != is_vowel(s2[i])){
return false;
}
}

return true;
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;

REP(i,t){
if(solve()){
printf("Case #%lld: same\n",i+1);
}else{
printf("Case #%lld: different\n",i+1);
}
}

return 0;
}

[/java]

I. INSEPARABLE LUQ & RUQ

This is the hardest question according to the number of line of code. At first, you would think, this is a bit hard, as they consider both location and state. And at the same time, you need to track the university code. And you might figure-out to test all possible combination. However, the number of university for each test case can be up to 100,000. An O(n^2) solution is simply not fast enough. One observation that give clues to the solution is that, this problem can be reduced to a shortest distance pair problem by considering universities on the same state as having infinite distance from each other. Once you realize that, you can google a relatively popular algorithm on solving shortest distance pair problem in logarithmic time. See this for more information. I would think this is, in fact the hardest question, as it is error prone and lengthy to implement. But the logarithmic algorithm is a quite famous divide and conquer algorithm, so personally I like question D more.

C++ Solution

[cpp]
#include<bits/stdc++.h>
using namespace std;

#define SET(t,v) memset((t), (v), sizeof(t))
#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize( unique( ALL(c) ) – (c).begin() )
#define REP(i,n) for(ll i=0;i<n;i++)

#if __cplusplus > 199711L
#define ItREP(it,c) for(auto it = (c).begin(); it!= (c).end(); it++)
#else
#define ItREP(it,c) for(typeof((c).begin()) it = (c).begin(); it!= (c).end(); it++)
#endif

#define IREP(in,i,n) for(ll i=in;i<n;i++)
#define IN(a,b) ( (b).find(a) != (b).end())
#define PB push_back
#define FILL(a,v) memset(a, v, sizeof a)
#define MP make_pair

typedef long long ll;
typedef long double LD;
typedef pair<int,int> pii;

#define NDEBUG

using namespace std;

#define INF LLONG_MAX

class Uni;
bool byx(const Uni &u1,const Uni &u2);
typedef pair<Uni,Uni> puu;

class Uni{
public:
ll x;
ll y;
char state;
int ucode;
bool operator<(const Uni &u) const{
if(this->state == u.state){
return byx(*this,u);
}
return this->state < u.state;
}
};

bool byx(const Uni &u1,const Uni &u2) {
if(u1.x == u2.x){
if(u1.y == u2.y){
if(u1.ucode == u2.ucode){
return u1.state < u2.state;
}
return u1.ucode < u2.ucode;
}
return u1.y < u2.y;
}
return u1.x < u2.x;
}

bool byy(const Uni &u1,const Uni &u2) {
if(u1.y == u2.y){
if(u1.x == u2.x){
if(u1.ucode == u2.ucode){
return u1.state < u2.state;
}
return u1.ucode < u2.ucode;
}
return u1.x < u2.x;
}
return u1.y < u2.y;
}

ll edistance(Uni u1,Uni u2){
if(u1.state == u2.state){
return INF;
}
return (u1.x-u2.x)*(u1.x-u2.x) + (u1.y-u2.y)*(u1.y-u2.y);
}

pair<ll, puu> find_shortest_brute(vector<Uni> &uss){
pair<ll,puu > shortest = MP(edistance(uss[0],uss[1]),MP(uss[0],uss[1]));

// Just try every combination
for(int i=0;i<uss.size();i++){
for(int i2=i+1;i2<uss.size();i2++){
pair<ll,puu > cur = MP(edistance(uss[i],uss[i2]),MP(uss[i],uss[i2]));
if(cur < shortest){
shortest = cur;
}
}
}

return shortest;
}

pair<ll,puu > find_shortest_clever(vector<Uni> &uss){
// If size of uss is too small, use brute force.
if(uss.size() <= 3){
return find_shortest_brute(uss);
}

vector<Uni> p1;
vector<Uni> p2;

// Divide the list into two
copy(uss.begin(),uss.begin()+uss.size()/2,back_inserter(p1));
copy(uss.begin()+uss.size()/2,uss.end(),back_inserter(p2));

// Run it separately
pair<ll,puu> r1 = find_shortest_clever(p1);
pair<ll,puu> r2 = find_shortest_clever(p2);

// Get the shorter one
pair<ll,puu> shorter = r1 < r2 ? r1 : r2;

// Get the middle x
ll midx = (uss.begin()+uss.size()/2)->x;

// This will contain the university within shortest distance from the middle point.
vector<Uni> midstripe;
REP(i,uss.size()){
Uni cur=uss[i];
if(abs(cur.x – midx) <= shorter.first){
midstripe.PB(cur);
}
}

// Short the list by y
sort(ALL(midstripe),byy);

for(int i2=i+1;i2<midstripe.size() && abs(midstripe[i2].y – midstripe[i].y) < shorter.first;i2++){
if(edistance(midstripe[i2],midstripe[i]) < shorter.first){
shorter = MP(edistance(midstripe[i2],midstripe[i]),MP(midstripe[i2],midstripe[i]));
}
}

}

return shorter;

}

void solve(){
int n;
cin >> n;

vector<Uni> universities;
REP(i,n){
Uni u;
cin >> u.x >> u.y >> u.state;
u.ucode = i+1;
universities.PB(u);
}

// Short them byx
sort(ALL(universities),byx);

// Call the shortest clever
pair<ll,puu > shortest = find_shortest_clever(universities);
if(shortest.first == INF){
printf("NO SOLUTION");
}else{
if(shortest.second.second < shortest.second.first){
printf("%d %c %d %c",shortest.second.second.ucode, shortest.second.second.state, shortest.second.first.ucode, shortest.second.first.state);
}else{
printf("%d %c %d %c",shortest.second.first.ucode, shortest.second.first.state, shortest.second.second.ucode, shortest.second.second.state);
}
}
}

int main(int argv, char** argc){
cin.sync_with_stdio(0);

int t = INT_MAX;
cin >> t;

REP(i,t){
printf("Case #%lld: ",i+1);
solve();
printf("\n");
}

return 0;
}

[/cpp]

Java Solution

[java]
import java.io.PrintStream;
import java.util.*;
import java.io.*;
import static java.lang.Math.*;

public class Main{
static Scanner in;
static PrintStream out;
static PrintStream err;
static final long INF = Long.MAX_VALUE;

static {
in = new Scanner(System.in);
out = System.out;
err = System.err;

err = new PrintStream(new OutputStream(){
public void write(int b){
// NO-OP
}
});
}

public static <T> void dbg(String s,T val){
err.print(s+": ");
err.println(val);
}

class Uni implements Comparable<Uni>{
long x;
long y;
char state;
int ucode;

@Override
public int compareTo(Uni u){
if(state != u.state){
return state – u.state;
}
return new ByXCompare().compare(this,u);
}

public long distanceTo(Uni u){
if(u.state == state){
return INF;
}
return (x-u.x)*(x-u.x) + (y-u.y)*(y-u.y);
}

public void dbg(){
err.println(""+x+" "+y+" "+state+""+ucode);
}
}

class ByXCompare implements Comparator<Uni>{
@Override
public int compare(Uni u1,Uni u2){
if(u1.x != u2.x){
return u1.x – u2.x > 0 ? 1 : -1;
}
if(u1.y != u2.y){
return u1.y – u2.y > 0 ? 1 : -1;
}
if(u1.ucode != u2.ucode){
return u1.ucode – u2.ucode > 0 ? 1 : -1;
}
return u1.state – u2.state;
}
}

class ByYCompare implements Comparator<Uni>{
@Override
public int compare(Uni u1,Uni u2){
if(u1.y != u2.y){
return u1.y – u2.y > 0 ? 1 : -1;
}
if(u1.x != u2.x){
return u1.x – u2.x > 0 ? 1 : -1;
}
if(u1.ucode != u2.ucode){
return u1.ucode – u2.ucode > 0 ? 1 : -1;
}
return u1.state – u2.state;
}
}

class Result{
long distance;
Uni u1;
Uni u2;
Result(long d,Uni u1,Uni u2){
distance = d;
this.u1 = u1;
this.u2 = u2;
}
}

Result findShortestBrute(List<Uni> uss){
Result shortest = new Result(uss.get(0).distanceTo(uss.get(1)), uss.get(0), uss.get(1));

// Just try every combination
for(int i=0;i<uss.size();i++){
for(int i2=i+1;i2<uss.size();i2++){
Result cur = new Result(uss.get(i).distanceTo(uss.get(i2)), uss.get(i), uss.get(i2));
if(cur.distance < shortest.distance){
shortest = cur;
}
}
}

return shortest;
}

Result findShortestClever(List<Uni> uss){
// If size of uss is too small, use brute force.
if(uss.size() <= 3){
return findShortestBrute(uss);
}

// Divide the list into two
List<Uni> u1 = uss.subList(0,uss.size()/2);
List<Uni> u2 = uss.subList(uss.size()/2,uss.size());

// Run it separately
Result r1 = findShortestClever(u1);
Result r2 = findShortestClever(u2);

// Get the shorter one
Result shortest = r1.distance < r2.distance ? r1 : r2;

// Get the middle x
long midx = u2.get(0).x;

// This will contain the university within shortest distance from the middle point.
List<Uni> midstrip = new ArrayList<>();
for(Uni u:uss){
if(abs(u.x – midx) <= shortest.distance){
midstrip.add(u);
}
}

// Short the list by y
Collections.sort(midstrip,new ByYCompare());

// Then for all in the stripe,
// Check for possible combination that is lower.
// Note that this run in linear time instead of quadratic because of
// abs(midstripe[i2].y – midstripe[i].y) < shorter.first
// There is a geometric proof that there can be a maximum of 6 point that is in range
for(int i=0;i<midstrip.size();i++){
for(int i2=i+1;i2<midstrip.size() && midstrip.get(i2).y <= shortest.distance;i2++){
Result cur = new Result(midstrip.get(i).distanceTo(midstrip.get(i2)), midstrip.get(i), midstrip.get(i2) );
if(cur.distance < shortest.distance){
shortest = cur;
}
}
}

return shortest;
}

void solve(){
int n = in.nextInt();

ArrayList<Uni> universities = new ArrayList<>();

for(int i=0;i<n;i++){
Uni u = new Uni();
u.x = in.nextLong();
u.y = in.nextLong();
u.state = in.next().charAt(0);
u.ucode = i+1;
universities.add(u);
}

for(Uni u: universities){
u.dbg();
}

Collections.sort(universities,new ByXCompare());

Result shortest = findShortestClever(universities);
if(shortest.distance == INF){
out.print("NO SOLUTION");
}else{
if(shortest.u1.compareTo(shortest.u2) < 0){
out.print(""+shortest.u1.ucode+" "+shortest.u1.state+" "+shortest.u2.ucode+" "+shortest.u2.state);
}else{
out.print(""+shortest.u2.ucode+" "+shortest.u2.state+" "+shortest.u1.ucode+" "+shortest.u1.state);
}
}
}

public static void main(String[] args){
int t = in.nextInt();
for(int i=0;i<t;i++){
out.print("Case #"+(i+1)+": ");
new Main().solve();
out.println();
}
}
}
[/java]

Conclusion

PROMED 2012 seems to be a nice competition. However, personally I think, too many of the question are more about implementation rather than problem solving. It seems to require the use of getline which can be troublesome. And some question did not specify the number of input or size of input. It is clear that it test the team’s programming skill more than their problem solving skill. Those who want to sharpen their programming skill should try this out. But for those who would prefer a more problem-solving-like question, I suggest going straight to D and I.

4 replies on “PROMED 2012 Questions and Answer”

For Problem D at line 51-56, I found out using memset() is much faster than manually zero-ing all array elements to 0 using 2 for loops. It’s also much cleaner to use memset() from my opinion.

So here is performance test using your code solution + judges data set.

Without memset() :

user@user:~/Desktop$ time ./d d.out; diff DATA/D.out d.out

real 0m0.331s
user 0m0.331s
sys 0m0.000s

With memset() :

real 0m0.298s
user 0m0.298s
sys 0m0.000s

Cool, can you share the whole source code?

Yes sure, here it is : http://pastebin.com/xVk9cuNN

Thanks

A. P-LOCK

B. THE MATRIC RELOADED!

C. HAIL-FAST TAXI

D. COUNTING SUBSEQUENCES

E. DASH PATTERN

F. LEGOLAND TICKETS

G. EVEN (OR ODD) WINS!

H. STRUCTURE OF WORD

I. INSEPARABLE LUQ & RUQ

Conclusion

4 replies on “PROMED 2012 Questions and Answer”

Leave a Reply Cancel reply