10298 - Power Strings

[soyoja]

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]

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]

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.

[shahriar_manzoor]

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]

You should change the judge data a bit. The time 0.00 is very annoying at the top of the ranklist.

[gvcormac]

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]

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]

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]

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.

Thanxs in advance

[ftomi]

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]

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]

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

[DJWS]

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]

[Maarten]

nothing wrong with the problem; obviously the judge input doesn't include the test case you described.

[DJWS]

I got it