How to solve Challenge problems..

general
, ,
1

How can I solve challenge problems using rand seeds… I have seen various good solution use rand seeds…
Can anyone elaborate please?

2

I’m not quite sure with your challenge problem however I can give you reference about rand seeds.

http://www.cplusplus.com/reference/cstdlib/srand/
http://php.net/manual/en/function.srand.php
http://www.cplusplus.com/reference/cstdlib/rand/

2 Likes
3

The first thing to understand it that computer-generated “random” numbers aren’t really random, but instead “pseudo-random” in the sense that they are difficult to predict. The way they are generated is that there is a certain initial large number (called “seed”) that is fed to a complex function which generates a series of bits that depend on this number. Whenever you invoke rand() (or Math.random() or any of java.util.Random()'s methods in Java), it returns you some of the next bits in the sequence. An important outcome of this method is that if the initial “seed” is the same, the bits generated by the function will be the same, and so a program using rand() with the same seed will behave identically.

Now, when you have a randomized solution (one that uses rand()), some seeds will result in better solutions than others for certain inputs (you might even stumble into a seed that generates the optimal solution for a particular input, although that is exceedingly unlikely). The trick is instead of blindly trying different seeds, remember which seed gives you a good solution for a certain input and then reuse that for that input.

1 Like
4

thanks @webdesign

5

@msasha it means that ,the participants with good scores who use rand seed approach can actually get to the original set of inputs (official test cases) by choosing random seed everytime … m i right??? and as @mugurelionut stated in FAULT editorial that @winger used random seed everytime, is it possible that winger actually got actual set of inputs??? If yes then its so cooool…???

6

btw thanks for the reply… :slight_smile:

7

How would you get the set of inputs by choosing a random seed every time? I’m completely baffled how my answer could make you think that.

While it is possible to get the set of inputs, it’s quite tedious (unless you automate the process). @winger merely got the hashes of the inputs (their last few bits, in fact) and then mapped each hash to a seed that delivers a good result for that input.

8

@msasha I thought that choosing a seed to produce input cases and then solving problem according to that input