any SPOJ users?

[saltpro15]

Hey guys,

I'm going to hope this thread is in the right forum. Anyone here do the SPOJ's? I know Hanson's on there but he's not on this forum. I forgot my account/password a while ago, so my new ID is dr3w. I find the difficulty of them to be rather high, and some of the questions are translated from other languages to English, making them a little odd to understand.

[bbi5291]

Sure, I have almost as many problems solved as Hanson, although he solves much harder problems than I (accounting for the discrepancy in score).

One of the nice things about SPOJ is that you can look at the solved problems lists of other users. So pick a user such that you know you're better than him (her), and solve all the problems on their solved problem list. (I did this A LOT in my earlier days in SPOJ.)

Also, you can sort the problem list by number of users who have solved it.

If you need help, post on the SPOJ forum: http://spoj.pl/forum .

Note on I/O: eschew cin >> and cout << , they're SLOW. Actually, more specifically:
* If you're not going to R/W more than around 10KB-100KB of data, they are acceptable (but I can assure you that you'll get in the habit of not using them). However, TLE often occurs when you try to read 1MB of data or that sort of thing.
* You can use cin.sync_with_stdio(false) if you are going to use only cin functions and not touch stdin (even indirectly through calls such as scanf, which have an implied stdin). The same applies for cout/stdout. This seems to be anywhere from 1.5 to 2 times slower than scanf/printf themselves currently. (In the newest version of g++ this is faster, which it should be, since cin/cout use overloaded operator selection at compile time and scanf/printf determine types at runtime - but SPOJ doesn't have this version yet.) As you might guess by the name sync_with_stdio, if you use stdio functions when this is false, you'll get strange results, as cin/cout and stdin/stdout won't be synchronized.
* getline has acceptable speed. (cin.getline does too, but it writes to a C string, and if that's what you want, why not just use gets?)
* cin.read() and cout.write() are fast but offer no distinct advantage over their corresponding stdio functions fread and fwrite. (Also, you almost never want to use those functions except when trying to get the best runtime on the ranklist.)

[saltpro15]

ah, I see. Thanks Brian. Can you recommend any problems for a beginner to SPOJ?

[A.J]

Hey Drew. I am a SPOJ user too. Although, I don't use it much nowadays. I am more into other stuff (like doing the Iranian Olympiad, and the Bulgarian one for fun )

[saltpro15]

cool A.J. I like SPOJ for the fact that I can test my code at anytime, and there's a helpful forum. But the questions are in random order, and it's hard to find one's that aren't very difficult...
care to recommend any?

[Analysis Mode]

yes, I use SPOJ too. you can find me here on the Canadian rankings page.

Note: this list is bbi5291's.

For easy to code and easy to solve problems,

ADDREV ARITH ARMY CANDY CANDY3 CPRMT CUBES DIVSUM FASHION FAVDICE GNY07A GNY07B HANGOVER KROW NSTEPS OFFSIDE PERMUT2 POKER PQUEUE STPAR TOANDFRO TOE1 TOE2 TWOSQRS WSCIPHER

for easy to code, but perhaps more mathematically challenging

ARCTAN ARRANGE BAISED BINSTIRL BMJ CANTON CATM DRINK EASYPROB EIGHTS EQBOX FAVDICE FCTRL HUBULLU ICODER LEONARDO MINCOUNT NGM POLYGAME QUADAREA STONE TCOUNT2 TCOUNT3 TRICOUNT TRICENTR

as for harder problems, I highly recommend this link

[bbi5291]

Also, here's a list of SPOJ problems that involve DP. Analysis Mode may be able to provide more, as he's been keeping up with new problems better than I have.
Warning: Several of these problems are non-trivial. LEXBRAC, for example, requires a great deal of thought (you can find hints on my blog for this problem if you get really stuck.) For the most part though, hard DP problems are hard to come by, and on a difficult archive such as SPOJ, they are comparatively rare. Most SPOJ problems are fairly ad hoc, if truth be told.
ACODE
AIBOHP
BYTESM2
CHOCOLA
GNY07H
INUMBER
LEXBRAC (requires bignums)
LSORT
MBEEWALK
MINUS
MIXTURES
MTILE
MUSKET
ROCK
SQRBR
SUMITR (warning source code limit, requires hax)
THREECOL
TRT
TWENDS

There are also harder ones that I have not solved, such as AEROLITE.

[saltpro15]

have any of you done fctrl2? I can't think of any way to represent 100! in C++. Would python be more suitable?

[DemonWasp]

You can't think of any way to represent 100 factorial in C++? How about your own custom integer type? You'd just have to define arithmetic operations on it.

[Analysis Mode]

You have to code your own bignum multiplication, using strings.

edit: don't bother learning some python just to do this problem. coding up bignums yourself will be helpful in the future, and in more complex problems for which you don't want to use python.

[bbi5291]

Analysis Mode hasn't actually solved this problem, I notice.
Advice: When you're coding up your bignums, create a class so you can re-use this code for future SPOJ problems. Also, don't store the bignums as strings. Why?
Well, storing as strings sure makes it easy to read them in and print them out. However, if you do this, you're effectively treating each number as a sequence of individual digits. Let's say you want to add two 1000-digit bignums together, then 1000 operations are required. On the other hand, if you store them in a vector or list with, say, 4 digits per element, you only need to do 250 operations. With the naive method of multiplying numbers, time taken is O(N^2). So in this case your multiplication would become 16 times faster!
Also, notice that in this problem you'll never multiply by anything greater than 100. Using the multiple-digits-per-record representation simplifies this greatly, because you can simply start at the end and multiply, then shift one record left, carry, and multiply again, and so on, rather than having to iterate through the two digits as well if you mutiply by a two-digit number.

[saltpro15]

I'm a little confused as to how the scores work... I've solved 3 classical and 3 challenge problems, yet they aren't showing up, and my score hasn't changed. Anyone know why?

[bbi5291]

The scoring works as follows:
For solving a classical problem you earn 80/(40+N) points, where N is the number of users (including yourself) that have solved it. So if a lot of people have solved a particular problem, you won't get a lot of points for it.
The top scorer in a challenge problem earns 3 points. If higher scores are better, your score will be 3 * (your score) / (high score). If lower scores are better, your score will be 3 * (high score) / (your score).
Also, challenge problems don't show up on your solved problem list.

Tutorial problems don't contribute to your score or show up on your solved list - they are exactly that, tutorials. And partial problems don't count for points either, although that may change, who knows.

In the classical problemset listing hover your mouse over the link in the Users column and alt-text should appear telling you how many points you would get for solving that particular problem.

Problem ranklists:
* Classical and tutorial problems - you appear in the ranklist as long as you got an Accepted status. Entries are sorted first in increasing order of time and then in increasing order of date.
* Challenge problems - you appear in the ranklist as long as you didn't get an error, such as Wrong Answer, Time Limit Exceeded, or Runtime Error. The list is sorted first by score and then by date (and not by time). The same goes for partial score problems.

You don't get any points for having a solution faster than somebody else's - you just get glory.

[saltpro15]

I see, thanks Brian.

edit : woo! 87th:D hopefully be top 70 after this summer

[Analysis Mode]

@bbi5291: It's M3TILE, not MTILE

Other DP problems, off the top of my head and searching dynamic programming on the forums.

DTT
JEDNAKOS
PIGBNK
ININT
SEQPAR
PERMUT1