11258 - String Partition

[Jan]

You are using some sort of greedy. Greedy will not work I think. Try the cases.

Input:

Code: Select all

2
12147483647
92000000000

Output:

Code: Select all

2147483648
2000000009

Hope these help.

[mak(cse_DU)]

hi

i m getting wrong ans with 11258 i cant find why ?
can any one help me i am giving the code here.

Ferfous ,
this is not a greedy problem.
You have to think in dp.
Suppose....

long long split(int i){


for(int k=1;k<=10;k++) MAXIMIZE num[k]+split(i+k);
}
i means from i'th position to end of input string .
k means we take k digit number which is maximum 10 digit.
I first implement 2D dp . BUT TLE. so 1D dp is essential.

[dormant]

Hi ,
I am getting runtime error in this question.
http://uva.onlinejudge.org/index.php?o ... ID+7557502

I am not able to figure it out.

Help please.

here is the code.

Code: Select all

#include<iostream>
#include<string>
#include<vector>
#include<sstream>
#include<algorithm>
#include<stdio.h>
//#include<climits>
using namespace std;
long long sum[501];
long long int tonum(string s){
	long long int ans=0;
	int i;
	for(i=0;i<s.size();i++){
		ans=10*ans+s[i]-48;
	}
	return ans;
}
int main(){
	string s;
	int t;
	long long int prev,next;
	cin>>t;
	getline(cin,s);
	long long int num;
	int i;
	while(t--){
		getline(cin,s);
		int sz=s.size();
		for(i=0;i<sz;i++){
			if(i>=9){
				num=tonum(s.substr(i-9,10));
				if(num <= 2147493647LL){
						
					if(i-10<0){
						sum[i]=num;
					}
					else{
						int j=1;
						prev=sum[i-j]+tonum(s.substr(i-j+1,j));
						next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
						while(next>prev){
							prev=next;
							j++;
							next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
						}
					//	cout<<"kk"<<i<<" "<<prev<<"\n";

						sum[i]=max(num+sum[i-10],prev);
					}
				}
				else{
					num=tonum(s.substr(i-9,9));
					if(i-9<0){
						sum[i]=num;
					}
					else{
						int j=1;
						prev=sum[i-j]+tonum(s.substr(i-j+1,j));
						next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
				//		cout<<"pp"<<prev<<" "<<next<<"\n";
						while(next>prev){
							prev=next;
							j++;
							next=sum[i-j-1]+tonum(s.substr(i-j,j+1));
						}

						sum[i]=max(num+sum[i-9],prev);
					}
				//	}
				}
			}
			else
				sum[i]=tonum(s.substr(0,i+1));
		}
		if(sz>0)
		cout<<sum[i-1]<<"\n";
	}
	return 0;
}

One more question related to c++

when i use INT_MAX present in climits
instead of number
if(num <= INT_MAX); // in this case it is not entering if condition when num=2147493647.why?? here num is long long
if(num <= 2147493647LL)//here it is OK

[call2]

I am getting a run-time error for StringPartiotion Problem. I have followed all the submission conventions like
no class is public the class having main method is named Main, and classes are not inside any package and I
removed spaces from each line before processing it.
Also I have tested it on random input and also on the sample input given and it works correctly.
Here is the code...Can somebody please give a hind what I am missing here.

Code: Select all

import java.util.Scanner;
class Main {
	long maxValue = Long.MIN_VALUE;

	Main(int logLength, int[] marks) {
		long comp[][] = new long[marks.length][marks.length];
		for (int k = 0, l = 0; l < marks.length; ++l) {
			for (int i = k, j = l; i < marks.length && j < marks.length; ++i, ++j) {
				if (i == j) {
					comp[i][j] = marks[i];
					continue;
				}
				if (i == j - 1) {
					comp[i][j] = 10 * marks[i] + marks[j];
					continue;
				}
				if (marks[i] == 0) {
					comp[i][j] = comp[i + 1][j];
					continue;
				}
				long max = this.arrayToNumber(marks, i, j);
				for (int m = i + 1; m <= j; ++m) {
					long current = comp[i][m - 1] + comp[m][j];
					if (max < current) {
						max = current;
					}
				}
				comp[i][j] = max;
			}
		}
		this.maxValue = comp[0][marks.length - 1];
	}

	private long arrayToNumber(int[] marks, int low, int high) {
		long sum = 0;
		for (int i = low; i <= high; ++i) {
			sum = 10 * sum + marks[i];
			if (sum > Integer.MAX_VALUE || sum < Integer.MIN_VALUE) {
				return -1;
			}
		}
		return sum;
	}

	public long getMinCost() {
		return this.maxValue;
	}

	public static void main(String args[]) {

		Scanner scan = new Scanner(System.in);
		scan.useDelimiter("\n");
		String s = scan.next();
		s = s.replaceAll("\\s", "");
		int l = Integer.parseInt(s);
		while (l-- > 0) {
			s = scan.next().replaceAll("\\s", "");
			int digits[] = new int[s.length()];
			for (int i = 0; i < digits.length; ++i) {
				digits[i] = Character.digit(s.charAt(i), 10);
			}
			Main m = new Main(digits.length, digits);
			System.out.println(m.getMinCost());
		}
		System.exit(0);
	}
}