10038 - Jolly Jumpers

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

Moderator: Board moderators

panda_coder
New poster
Posts: 7
Joined: Mon Jun 08, 2009 4:02 am

Re: 10038 - Jolly Jumpers

Post by panda_coder »

to mf


Thank you, I finally got accepted! I know it's such an easy problem, but the runtime error has really really frustrated me.
I even thought that uva online judge does not simply give Java programs accept. (I know it's lame...)

Anyway, since I know one of the reasons I do wrong in my program (using an old procedure guessing input size, and null exception error...
Does that br.readLine() != null routine always work? Because i have an experience that it did not work, so for some reasons I tried that way that checks the length, and then it worked.

Anyway, I can not thank you enough for helping me!

Marcel Hernandez
New poster
Posts: 7
Joined: Wed Mar 04, 2009 4:00 pm
Location: Barcelona, Spain

Re: 10038 - Jolly Jumpers

Post by Marcel Hernandez »

I'm also getting WA despite of passing the sample input and everything I could think of (including n = 1)
My code (C++):

Code: Select all

Removed after AC
Edit: Ok I finally found myself a set of test cases that didn't generate a correct answer ("3 0 0 6", "4 0 0 0 10", etc. printed "Jolly") and solved the issue rewritting the whole algorithm into a more simple one.

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 10038 - Jolly Jumpers

Post by asif_khan_ak_07 »

what is the problem with the program......what m i supposed to do.....plz help me im new in this

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10038 - Jolly Jumpers

Post by Obaida »

There are 15 pages of discussion available..
so i think you can get ur desired info by visiting them carefully..
i also got acc by the help from these posts. :)
try_try_try_try_&&&_try@try.com
This may be the address of success.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Re: 10038 - Jolly Jumpers

Post by mf »

asif_khan_ak_07 wrote:what is the problem with the program......what m i supposed to do.....plz help me im new in this
Read the problem statement again, It asks you to check that "absolute values of the difference between successive elements take on all the values 1 through n-1". And what does your program do? It sums those absolute differences and compares the sum to n(n-1)/2. These two things aren't equivalent.

But first I suggest you take time to read some English style guide, and enable a spell checker in your favorite browser.

asif_khan_ak_07
New poster
Posts: 25
Joined: Fri Apr 17, 2009 8:24 am

Re: 10038 - Jolly Jumpers

Post by asif_khan_ak_07 »

thanks a lot for ur help......i got AC :D

arquiros
New poster
Posts: 1
Joined: Sat Jul 18, 2009 8:23 am

Re: 10038 - Jolly Jumpers

Post by arquiros »

I got WA and i don't know why... i've tried every test case here, and i've tried changing the output and nothing worked... here is my C code.

EDIT:

now i know why... don't use memset ever hehehe

noor_aub
New poster
Posts: 26
Joined: Sat Aug 22, 2009 12:16 pm

10038 - Jolly Jumpers

Post by noor_aub »

What an easy problem.

Absolute value and search.

I was a gadha.
Last edited by noor_aub on Wed Nov 11, 2009 7:37 pm, edited 1 time in total.

jpsan
New poster
Posts: 1
Joined: Tue Sep 15, 2009 4:57 am

Re: 10038 - Jolly Jumpers

Post by jpsan »

Please Help me... I've read every single post so far and still don't know how to fix my problem... I also tried the samples and i got always the 'correct' answer. Please.

Code: Select all

#include <stdio.h>
#include <stdlib.h>



int main()
{
    int tamSeq,i,ok;
    long long int bfr,now,diff,fingerPrint;
    int marked[3002];
    char line[100000];
    fingerPrint=1;
    ok=1;

    for(i = 0; i < 3002; i++){
        marked[i] = fingerPrint-1;
    }
   while (scanf("%d",&tamSeq) == 1){
            scanf("%lld",&bfr);
        for (i = 0; i < tamSeq-1; i++){

            scanf("%lld",&now);

            diff = bfr-now;

            if (diff < 0){
                diff = 0-diff;
            }

            if ( diff > 0 && diff < tamSeq && marked[diff] != fingerPrint ){
                marked[diff] = fingerPrint;
                bfr = now;
            }else{
                ok=0;
                break;
            }
        }

        if(ok==1){
            printf("Jolly\n");
        }else{
            printf("Not Jolly\n");
        }
        gets(line);
        ok=1;
        fingerPrint=fingerPrint+1;

   }

    return 0;
}

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 10038 - Jolly Jumpers

Post by arifcsecu »

try to use build in qsort algorithm

hope it helps
Try to catch fish rather than asking for some fishes.

george3456
New poster
Posts: 5
Joined: Tue Sep 15, 2009 11:16 am

Re: 10038 - Jolly Jumpers

Post by george3456 »

Help plzzzz ... do you have any idea why this code is getting CE??

code removed after acc
OKK sorted it out
i thought

Code: Select all

 int abs( int x) 
is in the header <math.h>
infact it is in <stdlib.h> header
The most important thing is never stop questioning ~ Albert Einstein

thelostknight
New poster
Posts: 1
Joined: Wed Nov 18, 2009 4:59 am

Re: 10038 - Jolly Jumpers

Post by thelostknight »

Hi

im getting toruble with this problem and i wanna know if the following input is "JOLLY"

9 10 5 1 4 6 12 19 27 26

because according to the uva toolkit its JOLLY, and I still cannot understand why?

can anyone help me? plis

:)

jenovaforum
New poster
Posts: 2
Joined: Sun Feb 14, 2010 12:05 am

Re: 10038 - Jolly Jumpers

Post by jenovaforum »

Words of general advice from correcting my WA into an AC:
In my original algorithm, I just read in numbers, took differences as I read them in, and trashed the rest of the line if I found something bad before the end of the sequence. I switched over to reading them *all* into an ADT, and then taking differences, and magically, my algorithm started working. Also at this time, rather than relying on my general formula (which should have been closed for a sequence of one number), I added an additional clause for a sequence only one number in length.

General tips:
Why sort when you can use something much more like hashing? O(n) vs. O(n lg(n)) Not to mention it's cleaner...
All operations stay within the bounds of 32-bit integers.

As for recent specific advice...
thelostknight:

The test case of...
9 10 5 1 4 6 12 19 27 26

This sequence is jolly because there are 9 numbers in the sequence, so the absolute differences between consecutive numbers in the sequence must make up the set {1,2,3,4,5,6,7,8}, but in no particular order.

|10 - 5| = 5
|5 - 1| = 4
|1 - 4| = 3
|4 - 6| = 2
|6 - 12| = 6
|12 - 19| = 7
|19 - 27| = 8
|27 - 26| = 1

Since the set {1,2,3,4,5,6,7,8} has been constructed from these differences, you would call this sequence of nine integers "Jolly"

tristanx9
New poster
Posts: 4
Joined: Mon Mar 08, 2010 11:35 pm

Re: 10038 - Jolly Jumpers

Post by tristanx9 »

Hi everybody! I? trying to solve jolly jumpers but UVa keeps on "Runtime error". I really don't know what is going on, someone could please look my code I give a sugestion?

Code: Select all

import java.io.*;

class jolly_jumpers{

    public static void main(String[] args) throws IOException{
    
        boolean[] validar;
        int n,indice;
        int passou;

        BufferedReader	inReader;
        inReader = new BufferedReader(new InputStreamReader(System.in));
        String line;

            while((line = inReader.readLine())!= null) {

                String [] numeros = line.split("\\s");

                n = Integer.parseInt(numeros[0]);
                
                validar = new boolean[n];

               passou = 1;

                for(int i=0;i<n;i++){

                    validar[i]=false;

                }

                for(int i=0; i<n-1; i++){

                    indice = Math.abs(Integer.parseInt(numeros[i+1]) - Integer.parseInt(numeros[i+2]));

                    //conferir se indice se encaixa na faixa permitida 

                    if(indice==0 || indice>=n){

                    	passou = 0;

                    	break;

                    }

                    validar[indice] = true;

                }

                if(passou == 1){

		        for(int i=1;i<n;i++){

		           if(validar[i]==false){ passou = 0;}

		        }
                }

                if(passou==1){System.out.println("Jolly");}

                else{System.out.println("Not jolly");}  


            }    
    }
}


I'm using this input:

4 1 4 2 3
5 1 4 2 -1 6
6 3 2 4 3 2 1
4 1 3 0 -1
4 1 3 2 -2
1 2000
2 1999 1998
3 1 2 4
3 4 2 1
3 104 102 101
3 -5 -7 -6
3 4 1 3
200 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200
10 1 2 3 4 5 6 7 8 9 10
10 1 2 4 7 11 16 22 29 37 46
10 -1 -2 -4 -7 -11 -16 -22 -29 -37 -46
10 -1 -1 -4 -7 -11 -16 -22 -29 -37 -46
1 1
2 1 2
2 2 1
4 0 4 2 3
4 1 3 2 4
1 2
6 1 4 3 7 5 10
5 3 4 2 3 5
9 5 6 4 1 -3 2 8 15 7
9 10 5 1 4 6 12 19 27 36
9 10 5 1 4 6 12 19 27 26

Ginving me:

Jolly
Not jolly
Not jolly
Jolly
Not jolly
Jolly
Jolly
Jolly
Jolly
Jolly
Jolly
Not jolly
Not jolly
Not jolly
Jolly
Jolly
Not jolly
Jolly
Jolly
Jolly
Not jolly
Not jolly
Jolly
Jolly
Not jolly
Jolly
Not jolly
Jolly

fj.iglesias
New poster
Posts: 1
Joined: Fri Jun 18, 2010 1:00 pm

Re: 10038 - Jolly Jumpers

Post by fj.iglesias »

Hi tristranx9,

I've tested in my program the case you posted and I get exactly the same output :-?
I cannot find any error in both your code and mine's. Here is my code:

Code: Select all

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

class Main implements Runnable{

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

    public void run() {
        new JollyJumpers().run();
    }
    
}

class JollyJumpers implements Runnable {
	
	static boolean[] DIFFERENCES = new boolean[3000];
	
    public void run() {
    	
    	String line;
    	boolean jolly;
    	int ant;
    	int sig;
    	int absdif;
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	try {
	    	while ( (line = br.readLine()) != null && line.length() > 0 ) {
	    		jolly = true;
	    		String[] tokens = line.split(" ");
	    		int n = Integer.parseInt(tokens[0]);
	    		// The definition implies that any sequence of a single integer 
	    		// is a jolly jumper.
	    		if (n > 1) {
	    			initDifferences(DIFFERENCES, n);	
		    		for (int i = 1; i < n; i++) {
		    			// n-1 differences
		    			ant = Integer.parseInt(tokens[i]);
		    			sig = Integer.parseInt(tokens[i+1]);
		    			absdif = Math.abs(sig-ant);
		    			if (absdif > n-1 || absdif < 1) {
		    				jolly = false;
		    				break;
		    			} else {
		    				if (DIFFERENCES[absdif]) {
		    					jolly = false;
		    					break;
		    				} else
		    					DIFFERENCES[absdif] = true;
		    			}
		    		}
	    		}
	    		if (jolly)
	    			System.out.println("Jolly");
	    		else
	    			System.out.println("Not jolly");
	    	}
    	} catch (IOException ioe) {
    		ioe.printStackTrace();
    	}
    	
    }
    
    void initDifferences(boolean[] differences, int n) {
    	for (int i = 1; i < n; i++)
    		differences[i] = false;
    }
    
    // You can insert more classes here if you want.
}
Some help would be very grateful, I've tried many test cases in the forum and the judge in programming-challenges always replies me Wrong Answer.

Post Reply

Return to “Volume 100 (10000-10099)”