## 10298 - Power Strings

Moderator: Board moderators

soyoja
Experienced poster
Posts: 106
Joined: Sun Feb 17, 2002 2:00 am
Location: Seoul, South Korea
Contact:

### 10298 - Power Strings

I think that the simple soultion is only calculate all input character

numbers, and check each character, return the minimum number of

character. I believe that it was the solution. ( Because,

when concatenate string, there are some looping patterns. So if it is

a concatenate string, there should be two or more char will be appread.

So I programmed it. But I got a WA.

My solution is wrong? Give me a hint.

Thanks.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Maybe it's just me, but I don't understand what you're saying. For example, what do you mean with "calculate all input character numbers"?

Alam
New poster
Posts: 4
Joined: Fri Apr 26, 2002 8:42 am
This problem is as like as periodic string(455). The only difference is that if he output of 455 is K then at 10298 the output is strlen(s)/K.
Last edited by Alam on Fri Feb 07, 2003 4:46 pm, edited 2 times in total.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### He He

If you print the judge data after seeing it and send it to judge and get accepted and then say that judge data is poor then what can we say but

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
You should change the judge data a bit. The time 0.00 is very annoying at the top of the ranklist.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
uva could change the data, but that wouldn't change the fact that the solution is available at the same place as the data.

gvcormac
Problemsetter & Reviewer
Posts: 194
Joined: Fri Mar 15, 2002 2:00 am
Contact:
The problem is the same as 455, but with a different maximum input size. (1 million vs. 80). The larger size rules out stupid brute force algorithms.

Stefan Pochmann
A great helper
Posts: 284
Joined: Thu Feb 28, 2002 2:00 am
Location: Germany
Contact:
Then I guess my brute force algorithm is not stupid enough, since it got accepted after 3.1 seconds
Was there a tighter time limit during the contest?

ithamar
Learning poster
Posts: 56
Joined: Mon May 13, 2002 11:58 pm
Location: Venezuela
I dont see why sare posting the solutions here.

The whole Valladolid idea behind this site is to simulate a contest enviroment and they do a great job so please lets try to keep it that way.

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:
gvcormac wrote:uva could change the data, but that wouldn't change the fact that the solution is available at the same place as the data.
Uva don't mind if one knows the judge data, but change it if somebody boosting with precalculated data for all answers.
(The limits was changed in 10303)
So the boosting is prevented, but the cheating not.
Ok, I see that this limit 10303 is more interesting, but you should decided it before setting problem.

shahriar_manzoor
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

### Preventing cheating

Hello,
Actually, preventing precomputing is not the issue here. During real time contest pre-computing is allowed but there one don't find any advanced calculating tool such as mathematica. But here the people who precompute may have done it with a language like C/Java/Pascal but some may have used other tools (which is I am afraid is not allowed in real time contest). That's why we prevent tables for the sake of the contestants.

As we want to maintain a standard contest environment we often change many things. It is difficult for us to predict everything. I generally tend to use large judge data to prevent precomputing (even if the data is known, even I cannot send a printf() submission for my own problems )
but it is not always possible as often the all possible input is small. Also we cannot prevent use of internet, cut copy etc. So after setting a particular problem we often have to search the internet to see if there is a full readymade code/solution ready. Although we cannot always do that eiher.

Sneeze
New poster
Posts: 13
Joined: Thu Jan 30, 2003 4:04 am

### 10298-Run Time Error

Invalid memory reference!!
I declared a char array that contains 1 million units.
I wonder if it caused the error!

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:

### 10298

Hi,

I used such input : abaaababaaab
, and my program will output : 1

I think the output is wrong, and it should be 2 anyway
Strangely, after sending my code to online-judge, I got AC

BTW, I found this problem when i was handling p455
p455 is very similar with p10298
but online-judge will detect the such case: abaaababaaab

Here is my code (C++), p10298
----------------------------------------------------------------------------
[cpp] Code Deleted [/cpp]
Last edited by DJWS on Thu May 06, 2004 2:16 pm, edited 1 time in total.

Maarten
Experienced poster
Posts: 108
Joined: Sat Sep 27, 2003 5:24 pm
nothing wrong with the problem; obviously the judge input doesn't include the test case you described.

DJWS
Learning poster
Posts: 100
Joined: Sat Oct 11, 2003 3:30 pm
Location: Taiwan
Contact:
I got it