In APIO 2019, For problem A In this solution it says that,

Let f(x) = {(x + x / b) % a, x % b}

It's possible to prove that f(x) is periodic with smallest period = ab / gcd(a, b + 1)

How do i find this (period of f(x))? I tried googling "how to find the period of a periodic function" but i could only find articles about trigonometric functions.

Any help is highly appreciated. Thank you for your time.

I have asked this here but i didn't get any answer.

Today i tried to solve IOI 2015 horses problem. I observed that maximum profit can be gained by selling all horses on the same year. Obvious bruteforce would be to check every year.

Here is my solution:

int init(int n,int* x,int* y){
  ll MAX = 0;
  ll h = 1;
  for(int i=1;i<=n;i++){
    h *= x[i];
    MAX = max(MAX,h*y[i]);
  }
  return MAX;
}

But we have to keep the maximum profit. It is given that the answer could be very large therefore output it modulo 1e9+7; Because of the constraints above code works for subtask 1.

For remaining subtasks it won't. For keeping MAX i thought of maintaining a pair in the form of {n/ 1e9+7 , n% 1e9+7}. I think it could work.

But What if h exceeds integer bounds. we can't keep it modulo 1e9+7 because then h*y[i] will be wrong. How do i keep h such that it won't exceed integer bounds AND it won't give a wrong answer for h*y[i].

Thank you for your time

This is in reference to the question Rice hub in IOI 2011. I'll try to state specifically what i need so you don't have to go through the whole pdf.

when an array of points (sorted in non decreasing order), a starting index s and end index t of the segment is given calculate the absolute difference between each point in the segment s t and the mid point ( (s+t)/2 ).

i.e array: 1, 3, 5, 8, 11, 15

s: 1

t: 5

Here we have to consider the segment 3, 5, 8, 11, 15

Answer = |8-3| + |8-5| + |8-8| + |8-11| + |8-15| = 5 + 3 + 0 + 3 + 7 = 18

I want to do this in constant time. The solution suggests a way using prefix sum but i can't understand it.

Answer = (p - s)*arr[p] - (T[p] - T[s]) + (T[t + 1] - T[p +1]) - (t - p)*arr[p]

where s =  starting index, t = ending index, p = (s + t)/2, T is the prefix sum array

Can you please describe the above equation so that i can understand it.

I tried the Pebbling odometer task of IOI 2012. I wrote an output for the subtask 1 and uploaded it to the wcipeg judge. But i got WA. Then i downloaded the input data and tried them manually. They gave the correct answer. Then i uploaded the official Solution given by ioinformatics.org. Still it's WA. Does anyone know why this happens.

My solution:

left
rr: 
pebble r
halt
ll:
pebble l
halt
r:
get
right
right
move
jump ll
l:
get
left
left
move
jump rr

Official Solution:

# Solution for subtask 1 of Odometer.

# Author: Giovanni Paolini

right

jump A

B:
	get
	move
	pebble C
	halt

C:
	get
	left
	left
	move
	right
	right

A:
	pebble B

Result:

Recently i tried to solve the Amazing Robots task in IOI 2003.My first Idea was to run dijsktra while updating weights by calculating the position of guards. As we cannot wait in a position without a command this won't work. After that i have no idea how to solve this.

I googled for a solution and this is the only one i found from here .

Do a BFS on the state space.

Naive state space is

Position of robots in each grid.
Position of each guard.
This is too large (state space is 400 × 400 × ....).

Instead, compute the guards' positions as a function of time. In this case, we need to maintain:

Position of robots in each grid.
Current time T.
State space is still 400 × 400 × N, where N is the number of steps till they get out, which may become too large.

Observe that the guards' beats are of length 2, 3 or 4. Thus, each guard returns to his starting position after 2, 4 or 6 moves. Thus, we only need to keep track of time T modulo 2, 4 and 6. Since lcm(2,4,6) is 12, if we keep track of T modulo 12, we can recover all these three values.

In this problem, it is important to recognize that the path lengths for the guards allow you to cut down the state space of the BFS dramatically, to bring it within limits. Also, the number of edges is small because each node has at most 4 neighbours, corresponding to the N-S-E-W moves.

But i don't know what the State Space means. And i'm having hard time understanding how the BFS works here. (Edit: I understand how a simple BFS works) Again i googled and searched here for the state space of a BFS but found nothing.

Can someone help me understand what State Space of a BFS means and how can we use it to Solve this problem.

Thank you very much for your time.