OJ Board

Yes, but I guess the test data wasn't that comprehensive--even though my solution was wrong, it somehow got AC.

Regardless, I still get this problem. In your earlier posts, you said that if

j > k > l

and n is large enough, then the actual values of j k and l don't matter. Why is that?

Hi,

I can't think of the real/intended way to solve this problem. I managed to make an AC solution by trying the vectors

(n,1,1) (n,2,1) .... (n,n,1).....(n,n,n)

so basically, I try to change each component from 1 to n. This means I try a total of n^3 different vectors.

Clearly, this wasn't the ...

junbin, I seriously doubt a brute force approach would even bring you within the 10s time limit. I find it hard to believe that memoization would get you top 25.

Perhaps you would care to explain your approach?

Finally got AC!!!! Kinda surprised no one spotted my error.

I got TLE as well. I had pretty much the same algorithm as yours, but I tried to speed it up by removing the duplicate words in the dictionary, and I used a boolean array instead of an int array to keep track of visited nodes.

This is supposed to be a simple BFS graph problem but for some reason I keep getting TLE.

My program first stores the dictionary into a sorted, unique vector. Then for each pair of words in a test case I just use a simple BFS with the first word as the source vertex. For each word in the chain, I ...

I agree. But next_permutation should still be faster than using a recursive algorithm. Is there a faster way to do permutations/combinations?

For permutation:

Dictionary:
dog
cat
web

Encrypted String:
xyz abc pqr

I need to try
dog->xyz cat->abc web->pqr
dog->xyz web->abc cat->pqr
cat->xyz web->abc dog->pqr
etc.. (so I need to permutate the dictionary words)

For combination:

Dictionary:
dog
cat
web
boy

Encrypted String:
xyz ...

I know in STL you can use the next_permutation algorithm to get permutations in linear time, but how do you get QUICK combinations in C++? e.g. how can I find all the different ways to choose 10 things out of 500 things in less than a few seconds, when the order doesn't matter?

I ask because I am ...

For some reason my program keeps getting WA. I've tried the test cases from the previous post, and my I/O does what the previous posts suggested:


Upon closer inspection of my name-reading routine, I see that it was slightly more complicated than I described yesterday. Here's a detailed ...

How did anyone solve something like this in less than 3 hours??

After coding and re-coding for some time I finally managed to write a C++ program that accepts the test cases from

http://plg.uwaterloo.ca/~acm00/S98-1/

But it takes about 15 MINUTES. My design is backtracking, so my code should be ...

In the STL, is there a default function that sorts a rectangular 2D array based on a specified column? For instance, if I have:

Array-Index studentID grades
0 5 90
1 6 8

How do I get a list of the students based on grades ranking (i.e. Sort the grades column)? This should be a fairly common task ...