| Show all threads Hide all threads Show all messages Hide all messages |
| Actually p and q cannot be very big,right? | wangbicheng1 | 1175. Strange Sequence | 18 Nov 2015 19:30 | 1 |
I tried a number of tests, and neither of p,q is very big(Many of them beyond 1000). Maybe there's some mathematical property of the f function? |
| A person even solved it by using only 53K memory. Can you talk about it? | helin | 1175. Strange Sequence | 24 Apr 2009 15:10 | 3 |
If you know that 'n' is on period, you may find 'q' by checking n+1, n+2, n+3, ... till you hit identical to 'n' state. Then, when you know 'q', you may iterate from states '1' and '1+q' till they match, this way you'll find 'p'.
This relies on a guess that iteratively you won't get TL. I used value of 1'500'000, but I don't know if it has a proof or if it means weak tests. For A1>0 there is a proof as there are only ~1M distinct Xi, Xi+1 pairs whose product does not overflow 100'000. But as for A1=0 case - I don't know... Theoretically p or q can be as large as ~100'000^2. Is is possible not to set limitation on number of different pairs in solution.
I remembered last pair (x_s, x_{s+1}) where s is the biggest power of two less than current position. And I compared all pairs till the next power of two to this remembered pair. |
| Clarification | Fyodor Menshikov | 1175. Strange Sequence | 24 Apr 2009 15:00 | 1 |
It is not clear from problem statement, but is true for all tests: B1 >= B2.
Where it is required to subtract C, C is positive.
Edited by author 24.04.2009 15:03 |
| Important fix! | Denis Koshman | 1175. Strange Sequence | 7 Sep 2008 13:32 | 1 |
"You may assume that all intermediate values of H and all values of F fit in range [0..100000]"
This should be put to problem statement, rather than to input description. Otherwise claim about periodicity is wrong.
Consider the following sequence:
X1=0, X2=2
A1=0, A2=0, A3=2, A4=0
B1=3, B2=2, C=5
0 2 -1 -2 -4 -8 -16 ... -(2^n) ...
It's not periodic, but all coefficients (as well as initial elements) are non-negative. |
| I think the data size of this problem is quite large. Any hint to this problem? | AOY++ | 1175. Strange Sequence | 14 Aug 2008 18:39 | 3 |
Ok.. here is my hint: Choose p large enough to be sure you are in period of the given sequence and try findind q.
Edited by author 07.09.2008 13:47 |
| What is the maximum value of p? | Andriy Kozachuk(VNTU) | 1175. Strange Sequence | 14 Aug 2008 18:36 | 2 |
What is the maximum value of p? |
| Strange... | Alias (Alexander Prudaev) | 1175. Strange Sequence | 10 Apr 2007 21:58 | 2 |
Strange... Alias (Alexander Prudaev) 10 Apr 2007 21:51 I have two programs 1st - a right one wich have WA#2
and second - gets AC
if you remove comment you get WA#2
WHY? I realy can't understand, anybody please help me!
struct point
{
int ID;
double x,y;
};
int Chet(point a)
{
// if (a.x > 0 && a.y >=0)
return 0;
// if (a.x <=0 && a.y > 0)
// return 1;
// if (a.x < 0 && a.y <=0)
// return 2;
// if (a.x >=0 && a.y < 0)
// return 3;
}
inline bool Tr(const point &a, const point &b)
{
return a.x*b.y-a.y*b.x > 0;
}
inline bool operator < (const point &a, const point &b)
{
int ca = Chet(a);
int cb = Chet(b);
return ca < cb || ca==cb && Tr(a,b);
} Oh sorry, I mean problem 1175, admins you can correct it |
| Can someone give me some tests? I got wa on test#6 | funny_story | 1175. Strange Sequence | 23 Oct 2005 17:49 | 1 |
Can someone give me some tests? I got wa on test#6 |
| Can you tell me how to solve it fast?My search pro is slow,and... | Yu Yuanming | 1175. Strange Sequence | 10 Apr 2005 18:08 | 1 |
Although it got AC, but I doubt whether it will give an correct answer on all test... :(
My algo is simply find a large num,assume it is on the cycle,and to find the periods...
I think it exist a maths way......or at least, have a good search method use something like hash and so on... |
