Search found 14 matches

by Michael Goldshteyn
Mon Dec 20, 2004 4:27 pm
Forum: Volume 107 (10700-10799)
Topic: 10798 - Be wary of Roses
Replies: 58
Views: 19879

So repeating the method of solution once more

Is it true then that the solution to the problem is: 1) Take all possible minimum weight (least roses trampled) exit paths, since we don't know the choice of optimal route that the farmer will make and he can choose any optimal route, since they all have equal weight. 2) Apply them to all four possi...
by Michael Goldshteyn
Tue Dec 14, 2004 3:49 pm
Forum: Volume 107 (10700-10799)
Topic: 10798 - Be wary of Roses
Replies: 58
Views: 19879

So, if I understand this correctly. You have to try all minimal exit paths, on all four rotations of the field and print the worst case scenario?

Mike
by Michael Goldshteyn
Mon Dec 13, 2004 8:37 pm
Forum: Volume 107 (10700-10799)
Topic: 10798 - Be wary of Roses
Replies: 58
Views: 19879

10798 - Be wary of Roses

I thought the solution to this problem involved finding the worst of the least weight (fewest roses stepped on) paths starting from the four squares around the plinth ('P') square. Apparently this is not the case. My attempt at solution went something like this: 1) Find least destructive path from s...
by Michael Goldshteyn
Mon Nov 22, 2004 5:21 pm
Forum: Volume 107 (10700-10799)
Topic: 10778 - Mathemagicland
Replies: 28
Views: 11990

This problem

I refuse to even bother working on this problem for the following reasons: 1) The problem description is confusing. I don't care how mathematically rigorous it is, it is difficult to understand. 2) The messages posted so far to elaborate on the confusing mathematical definition do not offer much hel...
by Michael Goldshteyn
Mon Nov 15, 2004 8:25 pm
Forum: Other words
Topic: New idea for authors rank list
Replies: 5
Views: 1950

New idea for authors rank list

How about an authors ranked list by number of times in 1st place. This is more interesting than number of problems solved. Of course the authors that solved the most problems, would be higher on the list, having a better chance of coming in first more times.

Thanks,

Michael Goldshteyn
by Michael Goldshteyn
Fri Nov 12, 2004 12:05 am
Forum: Volume 107 (10700-10799)
Topic: 10763 - Foreign Exchange
Replies: 45
Views: 17744

Once again I rule the roost

Once again I rule the roost! (0.074 s as of this writing) And yes, the numbers can fit into a signed 32 bit integer (i.e. they are <=2 to the 31st minus 1). Nothing in the problem statement constrains the actual values. Only the total number of value sets in one exchange program is constrained, and ...
by Michael Goldshteyn
Thu Nov 11, 2004 6:17 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17188

Re: another way

I just give each char with a prim,eg: a(2) b(3) c(5)... so you can change each string to a long long int ,and use % to check! so without any cut you will get ac, and if you improve it, I think you will get a better time:) That sounds like a horribly inefficient way of doing this. Mod (%) is very ex...
by Michael Goldshteyn
Tue Nov 02, 2004 5:22 pm
Forum: C++
Topic: How to skip lines while using cin <<
Replies: 7
Views: 4281

The correct answer

The right way, use:

[cpp]
#include <iostream>
#include <string>

const size_t num_lines_to_skip=2;
std::string s;

for (size_t i=0;i<num_lines_to_skip;++i)
std::getline(cin,s);
[/cpp]
by Michael Goldshteyn
Wed Oct 20, 2004 10:05 pm
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17188

Not only that, but I'm not sure if an implementation that checked for a truly proper superset would even pass the test. But, I presume the test data and test are constant, correct? Or will the test data be changed, now? In any case, the performance penalty of proper superset vs. superset is negligib...
by Michael Goldshteyn
Tue Oct 19, 2004 9:56 pm
Forum: C++
Topic: Why not upgrade gcc to latest version and use it for new...
Replies: 2
Views: 1620

Krzysztof Duleba wrote:The case is that OJ compiles _without_ optimization.
Really?? This is silly! That means I have to unroll my own loops and use char pointers all over the place instead of indexing, for small gains. Welcome to the dark age (i.e. the 80's)...
by Michael Goldshteyn
Tue Oct 19, 2004 8:15 pm
Forum: C++
Topic: Why not upgrade gcc to latest version and use it for new...
Replies: 2
Views: 1620

Why not upgrade gcc to latest version and use it for new...

The optimization of the version used is horrible, forcing me to write horrible code sometimes to compensate. Why not use the latest stable gcc for new problems?

Thanks

Michael Goldshteyn
by Michael Goldshteyn
Tue Oct 19, 2004 5:14 am
Forum: Volume 107 (10700-10799)
Topic: 10738 - Riemann vs Mertens
Replies: 16
Views: 4480

Indeed, I'm quite interested in how you solved it with such a fast time. I guess you found a pattern I overlooked. (Of course, one major thing to speed up my program which I'm too lazy to do at the moment is to not test all the even numbers, or even leave out multiples of three - well not exactly t...
by Michael Goldshteyn
Tue Oct 19, 2004 2:13 am
Forum: Volume 107 (10700-10799)
Topic: 10738 - Riemann vs Mertens
Replies: 16
Views: 4480

10738 - Riemann vs Mertens

I thought this was a very interesting problem to solve. Also, it seems like the number of approaches to this one is huge, judging from the enormous contiguous range of times and the large number of entries.

Michael Goldshteyn
(10738 - 0.020 s)
by Michael Goldshteyn
Tue Oct 19, 2004 2:09 am
Forum: Volume 107 (10700-10799)
Topic: 10745 - Dominant Strings
Replies: 38
Views: 17188

Bah

I, on the other hand, don't think that tries are the best data structure for this problem. Any data structure used for this problem has a construction penalty, especially once you break the 1 s barrier. I think an exhaustive search with good short circuiting heuristics goes best here combined with c...

Go to advanced search