10298 - Power Strings

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

Moderator: Board moderators

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

10298 - Power Strings

Post by soyoja » Wed Jun 05, 2002 8:28 pm

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:

Post by Stefan Pochmann » Wed Jun 05, 2002 10:27 pm

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

Post by Alam » Thu Jun 06, 2002 4:56 pm

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

He He

Post by shahriar_manzoor » Thu Jun 06, 2002 6:12 pm

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 :oops: :lol:

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Fri Jun 07, 2002 1:30 pm

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:

Post by gvcormac » Sun Jun 09, 2002 4:31 am

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:

Post by gvcormac » Mon Jun 10, 2002 5:17 am

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:

Post by Stefan Pochmann » Mon Jun 10, 2002 9:59 am

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

Post by ithamar » Mon Jun 10, 2002 10:18 pm

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 :wink:

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

Post by ftomi » Thu Jun 13, 2002 9:08 am

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. :evil:
Ok, I see that this limit 10303 is more interesting, but you should decided it before setting problem. :-?

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

Preventing cheating

Post by shahriar_manzoor » Thu Jun 13, 2002 11:25 pm

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

Post by Sneeze » Sat May 03, 2003 10:28 am

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

Post by DJWS » Sat Oct 11, 2003 3:55 pm

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

Post by Maarten » Sat Oct 11, 2003 7:39 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:

Post by DJWS » Mon Oct 13, 2003 3:33 am

I got it :o

Post Reply

Return to “Volume 102 (10200-10299)”