|
|
| Show all threads Hide all threads Show all messages Hide all messages | | Hints? | Zergatul | 2124. Algebra on Segment | 29 May 2021 18:42 | 3 | Hints? Zergatul 28 May 2021 19:19 We want to use segment tree, but we need to know how express some segment in order to preserve validity of multiplication and order calculation.
I noticed any segment can be expressed by just 2 integers. I cannot proof this, my math background is not good here.
Multiplication is trivial.
Now we need ability to merge 2 segments (expressed by 1-2 integers) and get 2 another integers. I spent tens of hours thinking on this, but cannot come up with correct merge algorithm.
Tried this:
merge(x1, x2, x3, x4):
if exists such i,j,k: where x[i]*x[j]%p=x[k], then we can remove x[k] if we preserve order
else try to set x[i] = x[i]*x[j]%p for some random i,j
repeat
My merge procedure is not correct. Am I heading in the right direction?
I don't remember the problem quite well, but I think the main data structures you need in this problem are those that query for sum of segment and gcd on segment; maybe lcm. There are several approaches, some of which use discrete logarithm while others don't. In any case you would need some optimizations. I'm not sure what you are trying to do, so sorry if my comment is misleading and is stopping you from coming up with your own original solution. I already stuck with my solutions at least 5 times, it's ok, I need fresh ideas :)
One of my first ideas was with segment tree and LCM.
1) We calculate order for every element.
2) It is easy to combine 2 segments. order(combined) = LCM(order(segment1), order(segment2))
3) But it hard to do multiplication.
If we multiply by m, we cannot just do order=LCM(order(m), order(segment)). Counterexample:
p=17
segment=[2] order(segment)=8
m=2
after multiplication
segment=[4] order(segment)=4
4 != LCM(order(2), order(segment)) = 8
I am trying to find a way how to express segment of any length in a short way (lets call it segment_data), so it has next properties:
1) I can calculate order quickly
2) I can create multiplication procedure over segment_data
3) Multiplication over segment_data leads to the same order as multiplication over raw segment
4) I can combine 2 segment_data into 1 (so I can build segment tree)
If segment_data is just order of a segment, I cannot make it work (example above). Property 3 is not working.
My last idea was to use segment_data = array of 2 elements (I understand I was not very clear in first post, it is confusing even for me). I found next: there are group of segments, that behaves exactly the same for our task.
I mean, if:
for any i in (1..p-1): order(i * segment1) = order(i * segment2)
Then we can replace segment1 with segment2, and nothing changes for our task.
I generated groups of such segments for different p.
Example:
p=17
[6,7,10,12] can be replaced with [3,6]
after multiplication by 1..p-1, they lead to the same picture of orders:
[16 16 8 16 8 8 8 16 16 8 8 8 16 8 16 16]
[6,7,10,11] can be replaced with [6,7], picture
[16 16 4 16 4 8 8 16 16 8 8 4 16 4 16 16]
When I was investigating behavior of similar segments, I noticed segment of any length can be replaced with segment of length 2. And it will have the same properties. The plan was to have 2 numbers as nodes of segment tree. But I stuck with combining procedure.
Edited by author 29.05.2021 18:42 | | I wonder what was the reason for the original TL = 10 sec :) | [NRU ITMO] WiNGeR | 2124. Algebra on Segment | 25 Jul 2019 10:26 | 1 | | | Thanks for such a cool problem | Md sabbir Rahman | 2124. Algebra on Segment | 4 Jun 2019 07:06 | 1 | Whoever made this problem, thanks a lot! Seeing group theory applied in cp felt pretty cool. Alos learnt a lot thanks to this problem |
|
|
|
