Hello,

I would like to put GIFs in statements (in polygon), but attaching the GIF directly (and then inserting it like a picture) doesn't do the job. Does anybody know how to do this? please don't downvote me, I'm a very boomer

# | User | Rating |
---|---|---|

1 | tourist | 3870 |

2 | Benq | 3618 |

3 | Miracle03 | 3453 |

4 | peehs_moorhsum | 3430 |

5 | Radewoosh | 3418 |

6 | Petr | 3408 |

7 | maroonrk | 3387 |

8 | sunset | 3338 |

9 | ko_osaga | 3334 |

9 | jiangly | 3334 |

# | User | Contrib. |
---|---|---|

1 | YouKn0wWho | 214 |

2 | 1-gon | 203 |

3 | Um_nik | 195 |

4 | Errichto | 181 |

5 | awoo | 180 |

6 | tourist | 176 |

7 | sus | 175 |

8 | antontrygubO_o | 173 |

9 | maroonrk | 170 |

10 | SecondThread | 169 |

Hello,

I would like to put GIFs in statements (in polygon), but attaching the GIF directly (and then inserting it like a picture) doesn't do the job. Does anybody know how to do this? please don't downvote me, I'm a very boomer

Idea and Solution: Gheal

The basic naive approach would be to iterate through every subarray and naively check for each one if it is bordered.

Time complexity: $$$O(N^3)$$$

All bordered subarrays are either constant, or begin with a $$$1$$$ and end with a $$$2$$$. The answer can be found in $$$O(N)$$$ with prefix sums.

Time complexity: $$$O(N)$$$

Similarly to the first subtask, we'll iterate through every subarray. A subarray $$$[a_l,a_{l+1}, \ldots a_r]$$$ is bordered if $$$a_l \le min_{i=l}^r(a_i)$$$ and $$$ max_{i=l}^r(a_i) \le a_r$$$.

Calculating $$$min_{i=l}^r$$$ and $$$max_{i=l}^r$$$ for every pair of indices $$$(l,r)$$$ can be solved via RMQ or via dp in $$$O(N^2)$$$.

Time complexity: $$$O(N^2)$$$

$$$O(N \cdot \sqrt N)$$$ or inefficient $$$O(N log N)$$$ solutions should get 75 points.

Firstly, let's consider a simpler problem: `How many bordered subarrays start at position p?`

.

Let *nextless[l]* be the first position $$$j \gt i$$$ where $$$a_j \lt a_i$$$ and *nextge[l]* be the first position $$$j \gt i$$$ where $$$a_j \ge a_i$$$.

Since $$$a_l \le a_{l+1} \le \ldots \le a_r$$$, then $$$min_{i=l+1}^r (a_i) \ge a_l$$$. Therefore, the rightmost point of a bordered subarray starting with $$$a_l$$$ is at most *nextless[l]-1*.

Again, since $$$a_r \ge max_{i=l}^{r-1} (a_i)$$$, the number of bordered subsarrays starting at position $$$l$$$ is equal to the number of prefix maxima in the subarray $$$[l,nextless[l]-1]$$$.

The number of prefix maxima in some subarray $$$[l,r]$$$ can be calculated in $$$O(N)$$$ by starting with $$$p=l$$$ and replacing $$$p$$$ with *nextge[p]* until $$$p$$$ becomes greater than $$$r$$$. Optimizing this algorithm to $$$O(logN)$$$ requires setting up a sparse table from *nextge* and finding the answer via binary lifting.

Intended time complexity: $$$O(NlogN)$$$

Idea and Solution: cadmiumky

It is very uncomfortable for us to keep track of Gigi's players. More specifically, it's awkward to note the fact that each second we must update all the blocked positions due to their movement. So, we make the following claim: A pass is unsuccesful if the segment $$$[ (x_1,y), (x_2, y + (x_2-x_1)) ]$$$ intersects any player of Gigi's.

**the initial arrangement**

**the arrangement, as defined by the ammendement we made earlier**

**the arrangement at T=2, as defined by the statement**

We can prove this by induction. First, when we refer to (a,b)=1 at some time, it means that this point will be blocked at that time.

Base case: $$$(a+1,b), T=1 <=> (a+1,b+1), T=0$$$ (i.e. they are equivalent points at different times)

This derives from the statement, since if $$$(a+1,b+1), T=0$$$, then $$$(a+1-1,b+1), T=1$$$

Inductive step:

applying the base case on $$$(a+x+1,b+x), T=0$$$ we get

then again, by default, we have

So

And

so

QED

Now, let's assume we have to solve the following problem:

Given some vertical segments, determine for each query consisting of a horisontal segment if this intersects any of the earlier given segments.

This is a classical exaample of a problem that can be solved using the technique of line-sweeping. The solution we know, at least, is the following: sort both the vertical segments and the horizontal ones by their greatest X-coordinate. Then: A vertical segment is an update on all the Y-coordinates it covers. A horizontal segment is a point-query that asks if the latest vertical segment that covers this Y-coordinate happened after the left-X-limit of the segment.

This can be solved using a Segment Tree with lazy propagation.

I do admit that this is a... bad, to say the least, solution for this problem, and there are easier solutions. But I saw this problem and that was the first thing that struck me

The problem is that momentarily we have queries on lines parallel to ( (0,0), (1,1) ), and segments for updates parallel to Oy. With more consideration, we can say that we are currently working in the space defined by

So, we have to transform it to

This can be done by multiplying with the inverse of the first matrix (by the definition of matrixes) and then multiplying it with the latter (which is the identity matrix, so it won't have any effect). The inverse we are talking about is of course:

The effect on this matrix on every vector (which, in our case, would be the endpoints of the segments) in the plane is basically just subtracting the x-coordinate value from the y-coordinate value. So we use this to recalculate the input to the "normal" version. Then we can use the sweep-line algorithm we described earlier to solve the problem.

Time complexity: $$$O((N+M)*(log(N+M)+log(COORDMAX)))$$$

Space complexity: $$$O(N+M+COORDMAX)$$$

I do agree that I might have over-complicated the solution, but all of this was just for rigorous mathematical demonstration purposes. I also note that if we were to give the problem using something of the sorts "passes move with speed X, and players go down with speeds Y", the problem could've easily made it as the easy problem from some Romanian IOI TST (the solution would be to change the first column of the initial transformation to (X,Y)). We decided not to do this, because we didn't want to implement Segment trees over doubles, and neither would the contestant in this case. Also, as "artificial" the problem might seem, the idea for the original problem is as you see it in the statement (except the initial problem didn't have the bounds that the passes were horizontal and the blockers were vertical).

Idea: Gheal

Firstly , let $$$sb(n,k)$$$ be the number of ways of writing n as sum of k values greater or equal to 0. This is well known as "Stars and bars".

How can we encode a way of choosing money ? The conditions of a move are as follows :

- From each bag , substract its amount of money by some value which is $$$\ge 0$$$.
- There must exist at least one bag such that we substracted a value $$$> 0$$$ from it.

Thus , we can encode a way of choosing money as follows :

$$$A_{1,1}$$$ $$$A_{1,2}$$$ $$$\cdots$$$ $$$A_{1,k}$$$

$$$A_{1,1}$$$ $$$A_{1,2}$$$ $$$\cdots$$$ $$$A_{1,k}$$$

$$$\vdots$$$ $$$\, \, \, \, \, \, \, \, \, \, \, \, \, \, \,$$$ $$$\ddots$$$

$$$A_{N,1}$$$ $$$A_{N,2}$$$ $$$\cdots$$$ $$$A_{N,k}$$$

$$$\Sigma^{K}_{j=1} A_{i,j} = A_i$$$ for every $$$i$$$ in range $$$[1,N]$$$

There exists an element in every colum of the matrix such that it is $$$> 0$$$.

Where $$$A_{i,j}$$$ is the amount of money we took from bag i , during the j-th move.

This subtask needs an $$$O(K)$$$ solution. Let's fix the number of 0 values on the first row of the matrix. Let this value be $$$T$$$. Thus , the second row of the matrix must contain at least $$$T$$$ non-zero value. There are $$${K}\choose{T}$$$ ways of arranging the zero values in the first row. This must be multiplied by sb($$$A_1$$$ , $$$K-T$$$) and sb($$$A_2-T$$$,$$$K$$$).We conclude the final formula as being :

In this subtask $$$O((N+K) \cdot K)$$$ is required. Let $$$dp_i$$$ be the number of possible configurations which last $$$i$$$ moves. Initially , $$$dp_0 = 1$$$, if all values are equal to 0, otherwise $$$dp_0=0$$$ if there is a value greater than 0. Let's use the principle of inclusion exclusion. First count all configurations , in which there could be a column full of 0s. Their number is equal to

Now we need to subtract from that number , the number of matrices that contain columns full of 0s. Let's use the previous states. It turns out that the number of matrices that contain columns full of 0s is equal to

This is true because we will subtract the number of matrices with 1 column full of 0s, then the ones with 2 columns full of 0s ... So , our transitions are :

Time complexity $$$O((N+K) \cdot K)$$$

Tutorial of Infoleague Autumn 2021 Round 2 Div. 1

Problem author : Gheal

Let some sequence $$$b=[$$$ $$$a[i_1],a[i_2], \ldots a[i_k]$$$ $$$]$$$. If $$$b$$$ is constant, then $$$a[i_1]+1=a[i_2]+2= \ldots = a[i_k]+k$$$. Therefore, $$$b=[$$$ $$$a[i_1],a[i_1]-1, \ldots, a[i_1]-(k-1)$$$ $$$]$$$.

Let *dp[i]* be the maximum length of a constant subarray ending in $$$a[i]$$$. We'll also need *maxdp[x]*=max( *dp[i]* for which $$$a[i]=x$$$).

Let $$$i$$$ be the current position. *a[i]* can be appended to any subarray ending in **a[i]+1**. Therefore, *dp[i]=dpmax[a[i]+1]+1(. *dpmax[a[i]]* will also be updated accordingly: *dpmax[a[i]]=max(dpmax[a[i]],dp[i])*.

The maximum length of any constant subarray is equal to $$$k=max_{i=1}^n(dp[i])$$$.

Reconstructing a maximal constant subarray will also require *prev[i]* — the last appearance of *a[i]+1* to the `left`

of $$$i$$$. From some position $$$p$$$ where *dp[p]* is maximal, $$$p$$$ will be replaced repeatedly by *prev[p]* $$$k-1$$$ times. This traversal will visit, **in reverse**, all the elements of a constant subarray ending in $$$a[p]$$$.

Problem author : cadmiumky

Is it really necessary to set some segment $$$[l,r]$$$ as the solution, where $$$l != 1$$$ ?

Let's say X is the last element of the solution. How can we find how many elements it overwrites?

let's say the optimal solution is $$$[l,r]$$$ (where $$$[l,r]$$$ denotes the subarray between indexes $$$l$$$ and $$$r$$$). Then, We can prove that l=1 the following way: let's consider $$$[l-1,r]$$$ (which should exist assuming $$$l!=1$$$), then $$$sum[l-1,r] = sum[l,r] + min(v[i] | l-1 \le i \le r)$$$ The second term of the sum is always greater than 1, so $$$sum[l-1,r]>sum[l,r]$$$ (where sum[x,y] denotes the sum of the elements in between indexes x and y after the segment is gorbasorted)

Then, we propose the following soltuion: Let gorba[i]= the sum of elements in $$$[1,i]$$$ after gorbasorted. Then, if X is the greatest position such that $$$X \le i$$$, and $$$v[X] \le v[i]$$$, then gorba[i]=gorba[X]+(X-i)*v[i] (v[i] overwrites all elements between X+1 and i-1). Then how do we find X for each i? This is an easy question that can be solved using a stack. more on that here

Problem authors : tibinyte + Gheal

Since $$$N,K \le 1000$$$ , we can start to develop an $$$O(N \cdot K)$$$ algorithm. Let DP[i][j] store the maximum money i can have if i helped $$$j$$$ homeless men from the first i places. We have 2 cases :

The value at $$$A_i$$$ is positive ( including 0 ).

The value at $$$A_i$$$ is negative.

First case is easy , because it is always optimal to withdraw money ( easy proof by contradiction ). So in this case we can just say that

Second case is pretty easy as well. Just like in the well known 0-1 knapsack algorithm , we have 2 choices : either help the i-th homeless man , or ignore him. Transitions are :

- DP[i][j] = max(DP[i][j],DP[i-1][j-1] — $$$|A_i|$$$) if $$$DP[i-1][j-1] - |A_i| \ge 0$$$
- DP[[i][j] = max(DP[i][j] , DP[i-1][j])

So , with $$$O(1)$$$ transitions and $$$O(N \cdot K)$$$ states , the time complexity will be $$$O(N \cdot K)$$$.

For this subtask , we need a better time complexity. First notice that an optimal solution that contains a maximum amount of homeless men , will also contain the optimal solution of any less homeless men as a `subsolution`

. Let's find the best solution in which we help the most homeless men. Let's assume we are currently at the ith place and we know an optimal solution for the first i-1 places. We have two cases :

- The value at $$$A_i$$$ is positive ( including 0 )
- The value at $$$A_i$$$ is negative.

If $$$A_i$$$ is positive , we will just take the money.

If $$$A_i$$$ is negative and we have enough money , we will help the i-th homeless man ( we want maximum number of homeless men ). Else we will look at the optimal solution for the first i-1 places. If in that solution we have a homeless man begging for more money, we will add the homeless man at position i and remove the other homeless man from the optimal solution. Else , there is no reason for us to help that homeless man.

This can easily be simulated using a `priority_queue`

, with at most n removals and n insertions , we have an $$$O(NlogN)$$$ time complexity.

Thanks for participating in this round ! Also , we would love if you could share your thoughts about this round ( how were the problems , what could be improved in the future etc )

Tutorial of Infoleague Autumn 2021 Round 2 Div. 2

Hello,

Not for long, I have been using polygon to manage problem creation (so those could be subsequently be posted in a contest of some kind), and while creating a problem, I thought the following dynamic could be interesting to be implemented: The user can, in the beginning of the program, mention the checker that it would either want to print the queries in the problem in an offline manner or an online manner (i.e. the online method could be implemented via an interactive checker of some kind, while the offline method could work normally). But as I am a beginner with the polygon system, I do not know if there could be some way of ''internally'' (i.e. while the contestant's code is being checked) to change the type of the problem to interactive/normal. Is this possible or is it only science fiction?

I do acknowledge the fact that this could be implemented all in an interactive checker, but I do not know how to modify one to accept both types of implementations (offline/ online)

Thanks in advance (hopefully not for downvotes?)

What are the steps one have to go through for creating a successful contest? How do you propose problems, and what happens when they get rejected? when can they get rejected, and when is the round considered to be ready?

Thank you a lot in avance.

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/08/2021 18:30:36 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|