ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1706. Cipher Message 2

it answers perfectly right on my machine !
Posted by Esmaeil Ashrafi 31 Mar 2010 05:02
I don't know whay this system returnes "wrong answer" !!!
I ran my program several times,both in windows console and Netbeans IDE and every time i got the expected result.
but here neither sending source file nor pasting source code doesnt accept !

and here is the code,if anyone interested :

/*
 * this class implements the encoding requested in problem #1706
 */
/**
 * @author Esmaeil Ashrafi <s.ashrafi@gmail.com>
 */
import java.util.ArrayList;

public class StierlitzCipher {

    private static String input; // the string suppose to be ciphered
    private static int k;        // the length of sub strings
// temporary variable for query substrings
    private static StringBuffer temp = new StringBuffer();
// an array to store substrings of each query string
    private static ArrayList<String> sub = new ArrayList<String>();

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        /* if ran in command line console,first argument willl be the
         * string to cipher and second considered as the key
         */
        if (args.length == 2) {
            input = new String(args[1]);
            k = Integer.parseInt(args[0]);
        } // otherwise use of default values of problem
        else {
            input = new String("abaccc");
            k = 3;
            // prompt the user to using default values
            System.out.println("doing encrypt by default values:"
                    + "\nString : \"abaccc\"\nKey : 3");
        }
        query(input, k);
        System.out.println(); // just for trimming the output !
    }//end of main

    /**
     * gets the entire string and splits it to substrings in length
     * of "len" and sends each substring to method compute
     * for calculating the number of different non-empty substrings
     * could obtained from them.there will be substrings(and
     * consequent call to compute method)call as much as the length
     * of parameter str
     * @param str - the string to be cipher
     * @param len - the length of substrings(the key)
     */
    private static void query(String str, int len) {
        int m, strLen = str.length();
        for (m = 0; m <= strLen - len; m++) {
            compute(str.substring(m, m + len));
        }
        for (m = m; m < strLen; m++) {
            compute(str.substring(m).concat(str.substring(0, len - (strLen - m))));
        }
    }//end of query

    /**
     * queries queryString to calculate number of its different and
     * non-empty substrings and prints the count to the standard output
     * @param queryStr - the string to be queried
     */
    private static void compute(String queryStr) {
        int qLen = queryStr.length();
        for (int i = 0; i < qLen; i++) {
            for (int j = i + 1; j <= qLen; j++) {
                if (!sub.contains(temp.replace(
                        0, temp.length(), queryStr.substring(i, j)).toString())) {
                    sub.add(temp.toString());
                }
            }
        }
        System.out.print(" "+sub.size());
        sub.clear();
    }//end of compute
}//end of class

Edited by author 31.03.2010 05:29
Re: it answers perfectly right on my machine !
Posted by Sandro (USU) 31 Mar 2010 11:38
1. Read FAQ. Programs should read and write data using standard input and output. You shouldn't use command line arguments to input data.

2. Don't output any debugging info and user prompt, like this:

System.out.println("doing encrypt by default values:"
+ "\nString : \"abaccc\"\nKey : 3");
Second version
Posted by Esmaeil Ashrafi 1 Apr 2010 01:07
Thank you

but there are more than 20 times i attempt to make my prog acceptable and EveryTime i got that "time limit exceeded".
I have no idea after changing my code to the following (and this is just the last,i used any combination of String,StringBuffer you would think) how can make an acceptable answer while since the first time i ran my program i got the right answer ( but seems too late! )

And here is the last source code(the strategy is same as the first) :

import java.io.*;

public class StierlitzCipher2 {

    String input; // the string suppose to be ciphered
    int key;        // the length of sub strings
    PrintWriter out ;
    StreamTokenizer in ;
    CharSequence temp ;

    public static void main(String[] args) throws IOException {

        new StierlitzCipher2().run();
    }

    void run() throws IOException {

        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        key = (int) in.nval;
        in.nextToken();
        input = in.sval;
        out = new PrintWriter(new OutputStreamWriter(System.out));
        query(input, key);
        out.flush();
    }//end of run

    void query(String str, int len) {
        int m, strLen = str.length();
        for (m = 0; m <= strLen - len; m++) {
            compute(str.subSequence(m, m + len));
        }
        for (m = m; m < strLen; m++) {
            compute(str.substring(m).concat(str.substring(0, len - (strLen - m))));
        }
    }//end of query

    void compute(CharSequence queryStr) {
        int qLen = queryStr.length(), subCounter = 0;
        CharSequence[] sub = new CharSequence[(qLen * (qLen + 1)) / 2];

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

            for (int j = i + 1; j <= qLen; j++) {
                breakPoint :{
                temp = queryStr.subSequence(i, j);
                for (int k = 0; k < subCounter; k++) { // comparing the temp to elements of sub
                    if (sub[k].equals(temp)) {
                        subCounter--;
                        break breakPoint ;
                    }
                    }
                sub[subCounter] = temp ;}
                ++subCounter;
                }
            }
            out.print(subCounter);
            out.print(" ");
        }//end of compute
    }//end of class

Does anyone have any idea how to make it ?
Shouldn,t i use String objects  (nor CharSequence) and please dont talk about StringBuffer,i used that ...

Thanks in advance

Edited by author 01.04.2010 13:23
third version
Posted by Esmaeil Ashrafi 1 Apr 2010 12:51
and here is the third version :

package stierlitzCipher;

// in this version i use String and String[] in method compute
// instead of StringBuffer and Array<String>
// and iteration in array "sub" is more more sufficent :
// it doesn't itrate whole array,just compares the temporary substring
// to elements with same length
import java.io.*;

public class StierlitzCipher3 {

    String input; // the string suppose to be ciphered
    int key;        // the length of sub strings
    PrintWriter out;
    StreamTokenizer in;

    public static void main(String[] args) throws IOException {

        new StierlitzCipher3().run();
    }

    void run() throws IOException {

        in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        key = (int) in.nval;
        in.nextToken();
        input = in.sval;
        out = new PrintWriter(new OutputStreamWriter(System.out));
        query(input, key);
        out.flush();
    }//end of run

    void query(String str, int len) {
        int m, strLen = str.length();
        for (m = 0; m <= strLen - len; m++) {
            compute(str.substring(m, m + len));
        }
        for (m = m; m < strLen; m++) {
            compute(str.substring(m).concat(str.substring(0, len - (strLen - m))));
        }
    }//end of query

    void compute(String queryStr) {
        int subCounter = key, begin;
        String[] sub = new String[3*((key * (key + 1)) / 2)/2];
        String temp;
        // initially inserting key subs as the least count
        for (int i = 1; i < key; i++) {
            sub[i-1] = (queryStr.substring(0, i));
        }
        for (int i = 1; i < key; i++) {
            for (int j = i + 1; j <= key; j++) {

                temp = queryStr.substring(i, j);
                // comparing the temp to proper elements of sub
                begin = j - i-1 ;
            breakPoint:
                {
                    do {
                        if (temp.equals(sub[begin]))
                            break breakPoint;
                    } while (sub[(begin += key - 1)] != null);
                    ++subCounter;
                    sub[begin] = temp;
                }
            }
        }

        out.print(subCounter);
        out.print(" ");
    }//end of compute
}//end of class
/****************************************/
And(Again) the result is : time limit exceeded :(
I don't know the problem is with algorithm i use or something about java i shoul consider...
I think i should just leave it for the moment !

But i will be so thankful if anyboby guide me,cos i know there are submissions accepted programmed in java for this problem.
This problem i walking on my nerve !!!


Edited by author 01.04.2010 12:52