2025-2026 ICPC Latin American Regional Programming Contest @ CF GYM

»

paulocezar

8 months ago, hide # |

← Rev. 2 →

0

.

→ Reply

»

DNR

8 months ago, hide # |

← Rev. 2 →

0

Problem I is cute, here's a brief solution sketch since there appears to be no official editorial.

Consider the following reduced version of the problem:

There are $$$n$$$ points in a line, numbered $$$0$$$ to $$$n - 1$$$ from left to right. There are two pointers, one colored red and initially on point $$$a$$$, and another colored green and initially on point $$$b$$$. There are also several edges, leading from a point with a smaller index to a point with a larger index. Each edge is colored red or green. The goal is to move the red pointer to point $$$A$$$ while only using red edges and the green pointer to point $$$B$$$ while using only green edges, while also ensuring that no point is ever visited by both the pointers (they cannot visit the same point even at different times).

Solution

We'll define our state to be $$$(x, y)$$$, where $$$x$$$ is the current location of the red pointer, and $$$y$$$ is that of the green pointer.

The initial state is $$$(a, b)$$$. We'll explore states such that if a state $$$(x, y)$$$ is reached, there exists a valid pair of disjoint paths from $$$a$$$ to $$$x$$$ and from $$$b$$$ to $$$y$$$.

But wait, you say, how can we perform this exploration? Don't we need to maintain more information? We perhaps need to maintain two bitmasks to prevent intersections between paths? The answer is no, if we explore states carefully. We're going to explore them in such a way that if state $$$(x, y)$$$ is reached, then a couple more conditions hold:

If $$$x \lt y$$$, then either $$$x = c$$$ or no points in $$$[x, y)$$$ are visited by the green pointer.
If $$$x \gt y$$$, then either $$$y = d$$$ or no points in $$$[y, x)$$$ are visited by the red pointer.

How can we ensure this? By just enforcing one simple rule when performing transitions from a state $$$(x, y)$$$:

Unless the lagging pointer has reached its final position, always move the lagging pointer. The only restriction is that you must not land on the leading pointer.

Why does this rule enforce the conditions mentioned above?

Consider the case where neither pointer has reached its final position, and we're at $$$(x, y)$$$ such that WLOG, the actual path this state represents has the second pointer visiting a node $$$p$$$ such that $$$x \lt p \lt y$$$. But this implies that at some point, we were at a stage $$$(x', p)$$$ (where $$$x' \leq x$$$ since each pointer never moves backwards during transitions) and then went to $$$(x', y)$$$. But this implies that we moved the green pointer even though the red pointer was lagging, which is a contradiction.
Once one of the pointer reaches its final positions, we only move the other one, and that's pretty trivial, so I won't discuss it.

Pseudocode takes the following form:

adj_red and adj_green = adjacency lists

fix a, b, c, d

queue q
seen[n][n] = all false

q.push({a, b}), seen[a][b] = true
while !q.empty():

    [x, y] = q.front()
    q.pop()

    assert(x != y)

    if x > y or x == c:     #move the green pointer
        for v in adj_green[y]:
            if x != v and !seen[x][v]:
                q.push({x, v}), seen[x][v] = true
    
    if x < y or y == d:     #move the red pointer
        for v in adj_red[x]:
            if y != v and !seen[v][y]:
                q.push({v, y}), seen[v][y] = true

if seen[c][d]:
    paths exist, can be reconstructed by storing back-pointers for states during the bfs

There are $$$O(n^2)$$$ states and $$$O(m \cdot n)$$$ transitions, where $$$m$$$ is the total number of edges, which is good enough for the problem.

Solution to the original problem

Fix the solitary edge $$$[l, r]$$$ that you use to cross from $$$[0, n)$$$ to $$$[n, 2 \cdot n)$$$ (I have 0-indexed the problem). There can be $$$O(m)$$$ such edges.
Now, you must find a path from $$$0$$$ to $$$l$$$ (in $$$[0, n)$$$), and one from $$$r$$$ to $$$2 \cdot n - 1$$$ (in $$$[0, 2 \cdot n)$$$) such that there's no residue intersection in the two paths. It's easy to see that this is just a weaker version of the subproblem described above, so just solve it in $$$O(n ^ 2 + n \cdot m)$$$ as described.
This takes $$$O(m \cdot (n ^ 2 + n \cdot m))$$$ time in total, which is fast enough (although it can be optimized a bit).

Code

#include <bits/stdc++.h>
using namespace std;
#define endl "\n"

const int N = 505;

bool seen[N][N][2];
array<int, 3> bck[N][N][2];

signed main()
{
    ios_base::sync_with_stdio(false), cin.tie(NULL);
    int t = 1;
    while(t --)
    {
        int n, m;
        cin >> n >> m;

        vector<vector<int>> adj(2 * n);
        for(int i = 0; i < m; i ++)
        {
            int s, t;
            cin >> s >> t;
            -- s, -- t;
            adj[s].push_back(t);
        }

        bool can = false;
        vector<int> route;

        queue<array<int, 3>> q;
        vector<array<int, 3>> toclear;

        for(int cross = n + 1; cross < 2 * n and !can; cross ++)
        {
            q.push({0, cross - n, 0});
            seen[0][cross - n][0] = true;
            bck[0][cross - n][0] = {-1, -1, 0};
            
            while(!q.empty())
            {
                auto [p1, p2, t] = q.front();
                q.pop();

                toclear.push_back({p1, p2, t});

                if(p1 < p2 and t == 0)
                {
                    for(auto v : adj[p1])
                        if(v < n and v != p2)
                            if(!seen[v][p2][0])
                            {
                                seen[v][p2][0] = true;
                                bck[v][p2][0] = {p1, p2, t};
                                q.push({v, p2, 0});
                            }
                }
                
                if(t == 1 or (t == 0 and p1 < p2))
                {
                    for(auto v : adj[n + p2])
                        if(v - n != p1)
                            if(!seen[p1][v - n][1])
                            {
                                seen[p1][v - n][1] = true;
                                bck[p1][v - n][1] = {p1, p2, t};
                                q.push({p1, v - n, 1});
                            }
                }
                else if(t == 0 and p1 > p2)
                {
                    for(auto v : adj[n + p2])
                        if(v - n != p1)
                            if(!seen[p1][v - n][t])
                            {
                                seen[p1][v - n][t] = true;
                                bck[p1][v - n][t] = {p1, p2, t};
                                q.push({p1, v - n, t});
                            }
                }
            }
            
            for(int bc = 0; bc < n - 1 and !can; bc ++)
                for(int t = 0; t <= 1 and !can; t ++)
                    if(seen[bc][n - 1][t])    
                        for(auto v : adj[bc])
                            if(v == cross)
                            {
                                can = true;

                                array<int, 3> at = {bc, n - 1, t};
                                while(at[0] != -1)
                                {
                                    route.push_back(at[0]);
                                    route.push_back(n + at[1]);
                                    at = bck[at[0]][at[1]][at[2]];
                                }

                                sort(route.begin(), route.end());
                                route.erase(unique(route.begin(), route.end()), route.end());

                                break;
                            }

            for(auto [u, v, t] : toclear)
                seen[u][v][t] = false, bck[u][v][t] = {0, 0};
            toclear.clear();
        }

        if(can)
        {
            cout << route.size() << endl;
            for(auto i : route)
                cout << i + 1 << " ";
            cout << endl;
        }
        else
            cout << "*" << endl;
    }
}

→ Reply

»

ikrri

3 months ago, hide # |

0

How to solve F ?

→ Reply

»

sbarreto

2 months ago, hide # ^ |

0

Hi, one approach is to read the string and while the size of that string is bigger than 12-15 pop the last number, add to the count of 2 and 5 as we are simulating to divide it by 10. This is not the real number but with fit in that error. When you achieve that size you can do a normal prime decomposition.

In java you can do a similar approach using BigInteger but dividing by 2 or 3 depnding on the number parity. Both solutions may get AC

→ Reply

#	User	Rating
1	jiangly	3810
2	Benq	3676
3	Kevin114514	3655
4	maroonrk	3463
5	strapple	3447
6	Um_nik	3387
7	heuristica	3322
8	turmax	3317
9	tourist	3307
10	jiangbowen	3291

#	User	Contrib.
1	Qingyu	156
2	nik_exists	150
2	maspy	150
4	Um_nik	141
5	Errichto	139
6	adamant	137
7	AmShZ	135
8	BledDest	132
9	maroonrk	131
10	qwexd	129

paulocezar's blog