10332 - The Absent Minded Professor

[oker]

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

[wyvmak]

i'd like to give a hint.

let sequence be A[1],A[2],...,A[N]. with A[1]=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]

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]

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]

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]

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]

Oh, I see... Thank you!

[cothevacothe]

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[0]+1];
bx=new int[b[0]+1];
for (int i=0;i<b.length;i++)
bb[b]++;
a[0]=0;
a[n-1]=b[0];
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

[cothevacothe]

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[0]+1];
bx=new int[b[0]+1];
for (int i=0;i<b.length;i++)
bb[b]++;
a[0]=0;
a[n-1]=b[0];
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

[Adrian Kuegel]

You must name your class always class Main, not class Sum

[Moni]

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.

[Jalal]

Its C++ corner.
not to bother for ur JAVA
Stupid!!!!!!!!!!

[ithamar]

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.

[Moni]

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..."

[Adil]

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[0]+1));
bx = malloc(sizeof(int)*(b[0]+1));

for (i=0;i<blength;i++) bb[b]++;
a[0]=0;
a[n-1]=b[0];
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]