## 10332 - The Absent Minded Professor

All about problems in Volume 103. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

### 10332 - The Absent Minded Professor

This problem seems so hard. I don't know what algorithm to use. Please help me! Thanks!

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
i'd like to give a hint.

let sequence be A,A,...,A[N]. with A=0, then
1. there must be an input number k, where k=A, 2<=i<=N
2. and, the largest input number must be A[N].

i think my approach is not very fast, anyway.

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm

### 10332 - A question with the problem description

I have a question with the problem: In the sample #1 (0,2,3) and (0,1,3) are both solutions .Why say (0,2,3) is the correct solution and (0,1,3) is the 'image' ? Why cannot (0,2,3) be the 'image' of (0,1,3)?

wyvmak
Experienced poster
Posts: 110
Joined: Thu Dec 13, 2001 2:00 am
in my opinion, they're the same sentence. 'A is similar to B' is same as 'B is similar to A'. just which one you want to place more emphasis, giving you the feeling that A is derived from B.

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm
But the correct answer for this test case is (0,2,3) and (0,1,3) is not correct. (I took a look at the problem index and this problem is single-answered.) How to explain this? Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
It has something to do how you get the image.
0 1 3 has first as difference between two numbers 1, then 2, and 0 2 3 has first 2, then 1. An image has always the differences exchanged, and the solution which is wanted has the smaller difference between the last two numbers, not between the first two.

oker
New poster
Posts: 16
Joined: Tue Apr 09, 2002 1:23 pm
Oh, I see... Thank you!

cothevacothe
New poster
Posts: 3
Joined: Sun Oct 06, 2002 9:49 pm

### Could anybody change my code to C++ and submit it????

I got some unknown stupid compiled error...

// @JUDGE_ID: 9318RY 10332 Java "Easy algorithm"
import java.io.*;
import java.util.*;

class Sum
{
static String readLn (int maxLg) {
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

String input;
StringTokenizer idata;
boolean eof=false;

public static void main (String args[]){
Sum myWork = new Sum();
myWork.Begin();
}

int readInt() {
while (idata==null||!idata.hasMoreTokens()) {
input=Sum.readLn(1000);
if (input==null) {
eof=true;
return Integer.MIN_VALUE;
}
idata=new StringTokenizer(input);
}
return Integer.parseInt(idata.nextToken());
}

int n;
int[] b;
int[] a;
boolean ok,found;
int[] bb;
int[] bx;
void Begin() {
while (true) {
n=readInt();
if (n<0) break;
a=new int[n];
b=new int[n*(n-1)/2];
for (int i=0;i<n*(n-1)/2;i++)
b=readInt();
for (int i=0;i<n;i++) a=-1;
for (int i=0;i<b.length;i++)
for (int j=i+1;j<b.length;j++)
if (b<b[j]) {
int t=b;
b=b[j];
b[j]=t;
}
bb=new int[b+1];
bx=new int[b+1];
for (int i=0;i<b.length;i++)
bb[b]++;
a=0;
a[n-1]=b;
found=false;
vet(1,n-2,1);
if (found) {
for (int i=0;i<n;i++)
System.out.print(a+" ");
System.out.println();
}
else
System.out.println("Incorrect Balance.");
}
}

void vet(int i,int x,int y) {
if (found) return;
if (i==n-1) {
found=true;
return;
}
a[x]=b;
ok=true;
if (a[x]<a[x-1]) ok=false;
else
for (int j=0;j<n;j++)
if (j!=x&&a[j]>=0) {
int t=(int) Math.abs(a[j]-a[x]);
bx[t]++;
if (bx[t]>bb[t]) ok=false;
}
if (ok) vet(i+1,x-1,y);
if (found) return;
for (int j=0;j<n;j++)
if (j!=x&&a[j]>=0)
bx[(int) Math.abs(a[j]-a[x])]--;
a[x]=-1;
a[y]=(int) Math.abs(a[n-y]-b);
ok=true;
if (a[y]>a[y+1]&&a[y+1]>0) ok=false;
else
for (int j=0;j<n;j++)
if (j!=y&&a[j]>=0) {
int t=(int) Math.abs(a[j]-a[y]);
bx[t]++;
if (bx[t]>bb[t]) ok=false;
}
if (ok) vet(i+1,x,y+1);
if (found) return;
for (int j=0;j<n;j++)
if (j!=x&&a[j]>=0)
bx[(int) Math.abs(a[j]-a[y])]--;
a[y]=-1;
}
}
//@END_OF_SOURCE_CODE
A gentle man is a patient wolf.

cothevacothe
New poster
Posts: 3
Joined: Sun Oct 06, 2002 9:49 pm

### Yarin!!!

tried to submit this problem in java but no success, got some compiled errors that I could never understand x-(
help me to change this code to C++
:-p
// @JUDGE_ID: 9318RY 10332 Java "Easy algorithm"
import java.io.*;
import java.util.*;

class Sum
{
static String readLn (int maxLg) {
byte lin[] = new byte [maxLg];
int lg = 0, car = -1;
String line = "";

try
{
while (lg < maxLg)
{
car = System.in.read();
if ((car < 0) || (car == '\n')) break;
lin [lg++] += car;
}
}
catch (IOException e)
{
return (null);
}
if ((car < 0) && (lg == 0)) return (null);
return (new String (lin, 0, lg));
}

String input;
StringTokenizer idata;
boolean eof=false;

public static void main (String args[]){
Sum myWork = new Sum();
myWork.Begin();
}

int readInt() {
while (idata==null||!idata.hasMoreTokens()) {
input=Sum.readLn(1000);
if (input==null) {
eof=true;
return Integer.MIN_VALUE;
}
idata=new StringTokenizer(input);
}
return Integer.parseInt(idata.nextToken());
}

int n;
int[] b;
int[] a;
boolean ok,found;
int[] bb;
int[] bx;
void Begin() {
while (true) {
n=readInt();
if (n<0) break;
a=new int[n];
b=new int[n*(n-1)/2];
for (int i=0;i<n*(n-1)/2;i++)
b=readInt();
for (int i=0;i<n;i++) a=-1;
for (int i=0;i<b.length;i++)
for (int j=i+1;j<b.length;j++)
if (b<b[j]) {
int t=b;
b=b[j];
b[j]=t;
}
bb=new int[b+1];
bx=new int[b+1];
for (int i=0;i<b.length;i++)
bb[b]++;
a=0;
a[n-1]=b;
found=false;
vet(1,n-2,1);
if (found) {
for (int i=0;i<n;i++)
System.out.print(a+" ");
System.out.println();
}
else
System.out.println("Incorrect Balance.");
}
}

void vet(int i,int x,int y) {
if (found) return;
if (i==n-1) {
found=true;
return;
}
a[x]=b;
ok=true;
if (a[x]<a[x-1]) ok=false;
else
for (int j=0;j<n;j++)
if (j!=x&&a[j]>=0) {
int t=(int) Math.abs(a[j]-a[x]);
bx[t]++;
if (bx[t]>bb[t]) ok=false;
}
if (ok) vet(i+1,x-1,y);
if (found) return;
for (int j=0;j<n;j++)
if (j!=x&&a[j]>=0)
bx[(int) Math.abs(a[j]-a[x])]--;
a[x]=-1;
a[y]=(int) Math.abs(a[n-y]-b);
ok=true;
if (a[y]>a[y+1]&&a[y+1]>0) ok=false;
else
for (int j=0;j<n;j++)
if (j!=y&&a[j]>=0) {
int t=(int) Math.abs(a[j]-a[y]);
bx[t]++;
if (bx[t]>bb[t]) ok=false;
}
if (ok) vet(i+1,x,y+1);
if (found) return;
for (int j=0;j<n;j++)
if (j!=x&&a[j]>=0)
bx[(int) Math.abs(a[j]-a[y])]--;
a[y]=-1;
}
}
//@END_OF_SOURCE_CODE A gentle man is a patient wolf.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
You must name your class always class Main, not class Sum

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
I don't know Java well but I can say you two things:
• Always use simple code which is easy to understand and readable.
Don't use exception handleing tech. in any code.
I am now trying to solve the 10332 prob. in C++ if I get acc. I will PM it to you. We are all in a circular way, no advances, only moving and moving!

Jalal
Learning poster
Posts: 65
Joined: Sun Jun 02, 2002 8:41 pm
Location: BANGLADESH
Contact:
Its C++ corner.
not to bother for ur JAVA
Stupid!!!!!!!!!! ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
Jalal wrote:Its C++ corner.
not to bother for ur JAVA
Stupid!!!!!!!!!! Wow. This is what we need in our world: People that ofend others when they are asking for help. Maybe cothevacothe ask the question in the wrong thread but this is not excuse to be irrespectful to him.

Thanxs for ALL your help Jalal i am sure that it was very useful to cothevacothe. He is using this board (as a lot of us) to kindly ask for help and u offend him. Maybe your are right and he must not bother with java in the C++ corner but that's not the way to say it.
Last edited by ithamar on Mon Oct 21, 2002 11:36 pm, edited 1 time in total.
Those Who Don't Know History are doomed to repeat it

Moni
Experienced poster
Posts: 202
Joined: Fri Mar 22, 2002 2:00 am
Location: Chittagong. CSE - CUET
Contact:
Yes! Jalal ! you should not use the word "Stupid"! That's very rough and I think you are from my country, so partner try to avoid yourself using these types of word and made us a fair friends. This mail is also not for C++ so don't tell me "Stu..."  We are all in a circular way, no advances, only moving and moving!

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

### Code converted from JAVA to C

hello there cothevacothe. i guess this is what you wanted.

as you can see, i have tried to convert your JAVA prog to C prog. it compiles fine, and gives correct result for the sample inputs of this prob. but cheak it first for your sample inputs before submitting. i have just converted from JAVA to C, but i didn't cheak the algorithm. actually, i haven't given it much thought. it would be best if you explain your algorithm.

i have tried to keep your original code intact as much as possible. hope this helps you out.

[cpp]// @JUDGE_ID: 9318RY 10332 C "Easy algorithm"

#include <stdio.h>
#include <malloc.h>
#include <math.h>

#define false 0
#define true 1

#define bool int

void Begin();
void vet(int i,int x,int y);

void main ()
{
Begin();
}

int n;
int *b;
int *a;
bool ok,found;
int *bb;
int *bx;
void Begin()
{
while (true)
{
int i,j;
int blength;
if(scanf("%d", &n) != 1) break;
if (n<0) break;

a = malloc(n*sizeof(int));
b = malloc(sizeof(int)*n*(n-1)/2);
blength = n*(n-1)/2;

for (i=0;i<n*(n-1)/2;i++)
scanf("%d", b+i);

for (i=0;i<n;i++) a=-1;
for (i=0;i<blength;i++)
for (j=i+1;j<blength;j++)
if (b<b[j])
{
int t=b;
b=b[j];
b[j]=t;
}
bb = malloc(sizeof(int)*(b+1));
bx = malloc(sizeof(int)*(b+1));

for (i=0;i<blength;i++) bb[b]++;
a=0;
a[n-1]=b;
found=false;
vet(1,n-2,1);
if (found)
{
for (i=0;i<n;i++)
printf("%d ",a);
printf("\n");
}
else
printf("Incorrect Balance.\n");
free(a);
free(b);
free(bb);
free(bx);
}
}

void vet(int i,int x,int y) {
int t,j;
if (found) return;
if (i==n-1)
{
found=true;
return;
}
a[x]=b;
ok=true;
if (a[x]<a[x-1]) ok=false;
else
{
for (j=0;j<n;j++)
if (j!=x&&a[j]>=0)
{
t=(int) abs(a[j]-a[x]);
bx[t]++;
if (bx[t]>bb[t]) ok=false;
}
}
if (ok) vet(i+1,x-1,y);
if (found) return;
for (j=0;j<n;j++)
if (j!=x&&a[j]>=0)
bx[(int) abs(a[j]-a[x])]--;
a[x]=-1;
a[y]=(int) abs(a[n-y]-b);
ok=true;
if (a[y]>a[y+1]&&a[y+1]>0) ok=false;
else
{
for (j=0;j<n;j++)
if (j!=y&&a[j]>=0)
{
t=(int) abs(a[j]-a[y]);
bx[t]++;
if (bx[t]>bb[t]) ok=false;
}
}
if (ok) vet(i+1,x,y+1);
if (found) return;
for (j=0;j<n;j++)
if (j!=x&&a[j]>=0)
bx[(int) abs(a[j]-a[y])]--;
a[y]=-1;
}[/cpp]