z-javelin

Can someone explain how to solve this problem. I tried simple brute-force, and there worked 17/25 test cases.

I need help, too. I've also tried simple bf and my solution passes 10/25 test cases. :-(

Official solution is to use data structures, but it can be solved in another way, IMHO, a bit simpler. However, try to solve an easier problem: for each try, let t_i = 0, so you have k_i and t1_i.

@turgond: I have solved the problem using cumulative tables, so you can look at my solution (if you have solved it already). It depends how you store information in cumulative tables.

I'll look at your soltion as soon as I get mine to work :) Your tutorial at TC really helped me understand them!

I solved it with smart brute force.

Define "smart brute force"... Maybe you're on to some inovative algorithmic method, who knows? :) Image that... BBF - Boris' Brute Force :P

Dinamicko

@ picsel:
Very... descriptive post.

Give us more hints, I can't work out a nice solution.

@boris
Can you describe your smart brute force?

Position X is possible if position X - ki (where Ki is a number from 1 to 10) is possible.

But not always, you gotta keep track of ti. For every X + ki, ti is ti-1.
Something like that :)

My solution is very simple and works for all test cases (even though it's way too slow for some cases I tested locally ).

I loop through possible distances ( from 1 to 100 000, as it's said in the problem statement ) and try if this distance can be obainted from one of the runs ( if (distance - t1i) is divisible with ki and (distance - t1i) / ki <= ti ).

Very interesting. Thx tgudlek, I will try it as soon as possible.

To turgond:
"All the forum posts should be in English"

hard getting used to, if u look at the forum u'll see everything was in serbian ;) the idea I presented was to use 45 cumulative index trees, to save by k and modulo k

@turgond: Please, post the last question in English and I will remove the previous one.

However, you don't need 90 cumulative tables. Most of those cumulative tables (in your case) will be sparse, so you need only 10 that are fully used.
That what you know is:
t1 is filled, t1 + k is filled, t1 + 2*k is filled and so on. What if you consider t1, t1+k, t1+2*k and so on as adjacent numbers? Can you divide one of your cumulative tables to store this kind of adjacent numbers?

hmm, thought of that, but it seemed to me like it would be a mess with those binary operators, will give it a try, thanks a lot!!!

You will not have a mess with binary operation. Ok, let's take an example with k = 3 and maxn = 20; and let's put numbers in this way
0, 3, 6, 9, 12, 15, 18, 1, 4, 7, 10, 13, 16, 19, 2, 5, 8, 11, 14, 17, 20

Suppose you got t1 = 4 (k = 3, of course) and t = 3. Then you need to mark 4, 7, 10, 13 and as you see those number are adjacent, just as 9, 10, 11 and 12 are in usual cumulative table. Everything you need to do is to index in different way.

@turgond: Please, do not post more times the same post. Thanks.

@boba5551:

Can you explain solution to the problem without using Cumultative tables.

omg, I am sorry, refresh resent the posts :)...

Without using cumulative tables - hint:
If you have t1_i = 0, then for fixed k = const you can take highest t that has k = const, let it be T_MAX_k. Then all marked positions for k = const will be
0, k, 2 * k, ..., T_MAX_k * k

Try to extend this and solve current version of the problem.

Can you describe solution with cummulative tables with more details? I really can't find any sense in using 90 cummulative arrays in this task... :S

Ok, i'll try it tomorrow because i'm so sleepy now. :) Thanks for the hint.

I have forgotten, sorry - for each i, let t1_i = 0, not for some of them, but for each i. So t1_i actually doesn't exist in this simplified problem.

As Sloba said, you only need 10 :)

@turgon:
That's OK, but in order to understand that version with 10, I have to understand how to utilize 90 first... Right?

well....they are basically the same, Boba's solution requires a bit more work....
basicaly, since k is <= 10,
u can divide every query by k and t1 modulo k.
Than, in the cumulative tabel for k and l, where l>=0&&l<k, where l is t1%l, you mark each field from t1 do t1+t*k, and later when checking if it is marked, u look it up for each k.
I think that's it!

@Tgudlek

First, why did you go up to 100000, wasn't it enough to go up to t1i + (ti*k) ? Second how did you do it that it works? You see my code down here and it says for all tests time-limit. A very funny thing happening to me was I submited serveral times the code for the task z-passwrd for z-javelin and there worked about 7 tests xD/

Ok, here is it:

for(int i=0; i < n; i++){
scanf("%d %d %d", &pt, &et, &k);
for(int j=pt; j <=pt+(et*k); j++){
if( !((j - pt)%k) && ((j-pt)/k) <= et && !T[j]){
T[j] = true;
res++;
}
}
}

I've done it the same way and it won't work. tgudulek can you explain us how have you done it please? :)

I did it. Thx Tgudlek, it was my fault.

Aha, i see it now. I'll write it at my uncle's place because i have to go now. Thanks for the idea. :)

I'm glad you figured it out. ;)

Well, I duno if I helped you in some way. But if you got problems with it, just ask.

@Daniel93: I belive you can see that this isn't the real solution. For example:

100000
99992 2 3
99992 2 3
99992 2 3
..
99992 2 3

It would be almost O ( N ^ 2 ), which is waaay to slow.

Ok, to help anyone who wants to do it with cumulative tables, 45 of 100000 of SHORT type gets the job done!!!!!!!!!!!!! xD hurray!!!!!

@Tgudlek
Yes, I guess I'll have to learn comulative tables xD

Ups, this should be mine post. I mean that from Amtrix, I'm on his PC, so he was logged in.

Hmm, for me it seems that the solution with the comulative tables is even slower.

Can you please take a look at my solution.

http://pastebin.com/f6381a084

I get time limit exceeded at every test case. :-(

I think that you used too much memory space.

No its not the memory. You should separate input and searching. First input the given statmnets, and then like Tgudlek said you have to go for each distance between 1 and 100000 and try to get it. I think that will help.

This post was again mine xD

@Daniel93: Do you have two accounts? That is forbidden. If you have, please e-mail to admin to remove one of them.

Nope, this is a account from my brother, I was on his PC, I'm sorry for posting on his name.

Wow, you two have very similar scores on competitions. :)

Not ony similar scores, but very close submit times... ;)

not only on this competition

How much I know ACM is a team competetion :P
http://en.wikipedia.org/wiki/ACM_International_Collegiate_Programming_Contest#Contest_rules
And I became only this link for the rules....

;) But "08/09 Quals" isn't :)

Wow, you must have some super natural powers since your codes for some tasks ( Wovels, for example ) look like some just chagned few things and uploaded them :)

But this is not of my buisness, so I'll leave this discussion :)

C'mon.....
Wovels is a so simply task....
And in Quals we didn't corporate in any way... But ok,lets end this discussion here. ;)

why the hell is it important if they cooperate? You should all try to work on improving yourself, don't judge others....