Added to the announcement :)

9 challenging problems in just 2:15 hour? isn't that quite less?

You can register for the contest based on this (#749)

May be there will be some subtask problems.

Probably first few problems would be ez :) . Otherwise the time is very tight.

for LGMSs it's not so tight, for Div2 it's not big difference to solve first 3-4 problems in 2:15 or in 2:45 for example

I had only 10 minutes for the last three problems,so I just left and took a look at Atcoder Beginner Contest :(

Woah cheater has the guts to comment!

How are you cheater?

solve copy paste

.

I think I now know why "we" was used :|

maybe the college/school is starting... idk

note that m<n, which means that there is at least one vertex never occurs as $$$b_i$$$ among all restrictions

we can always find a such vertex and link all other vertices to it.

so it's like a greedy problem more than a graph/tree problem to me.

floor((1+2)/2)

Likely some mistake with not checking if cells which are $$$X$$$ could hypothetically escape if they weren't $$$X$$$. If that isn't the case you can't determine if it was initially $$$X$$$ or not. Forgetting to check that caused WA3 for me.

Do you mean XX \n XX? Then it's not determinable.

wtf, i insta-solved A and only managed to solve B with 2 minutes remaining

It's Russian highschool level which is roughly the same difficulty as a U.S. post-doctorate program or a Chinese gradeschool contest.

had the same idea, WA pretest 3 :(

I did something similar but got WA on test 3.

Maybe you did not handle if a blocked cell itself cannot exit the sub-graph if it was not blocked. In this case we will not be able to know if its N represents a blocked or an empty cell.

Are you checking if cells which are $$$X$$$ would be theoretically exitable if they weren't $$$X$$$ as well?

Suppose one of those cells is not exitable even if it wasn't $$$X$$$, then you wouldn't be able to differentiate between it being initially marked $$$X$$$ or not, so the grid isn't determinable.

I forgot about this and got WA3 because of that.

$$$m<n$$$ (strictly less)

Make b[i] leaves

It's given 1 < m < n .

So there will be at least one node that can be between any two nodes, make it root. Now just connect all the other nodes to it.

its correct its my solution too u probably implemented it wrong

Check if your bi is 0-indexed or 1-indexed. I had the same problem where I accidentally read in all bi's 1-indexed, and changing it to 0-indexed fixed it.

I also did same.. May be you have done some mistake in implementation

found a bug, there was incorrect handling of invalid columns
here is the fixed submission if someone would struggle with similar bug https://codeforces.net/contest/1586/submission/132293465

F has very similar solution to COCI 2020-2021 Contest -4 Hop .Unfortunately I recalled that I had done this problem before just after the contest ended.

A classic result is that if a directed graph with chromatic number $$$\chi$$$ is edge-colored with $$$r$$$ colors and $$$k^r < \chi$$$, then there exists a monochromatic path of length $$$k$$$. Problem F is just the construction to show that this result is sharp.

Reference: https://www.tau.ac.il/~nogaa/PDFS/Publications/Monochromatic%20directed%20walks%20in%20arc%20colored%20directed%20graphs.pdf

The second sample kinda gives away the solution. They should have made it more obscure.

I conjectured that the solution will be something like this.

Btw why are you tagging me??

I think problem F is more like a MO problem than a OI problem.

well, the quality of the problemset does not depend on whether you can solve them or not.

Your DP part is probably incorrect.

6 5
1 2
1 3
1 4
3 5
3 6
3
2 4
1 5
3 6

Output should be 3.

More like dp-problem

No, much simpler than that.

Hint: Consider under what situations will a single cell not be determinable.

It can be used (I used it) but not necessary

Nope, its dp combined with a sliding window like idea.

The core idea is that if a cell can't exit the grid due to being blocked by cells above / to the left of it, it would be non-exitable regardless of whether it was $$$X$$$ or not. So all cells in a subgrid with $$$1 \leq i \leq n$$$, $$$x_1 \leq j \leq x_2$$$ must not be blocked for the answer to be yes.

Basically let $$$minrow_{i, j}$$$ and $$$mincolumn_{i, j}$$$ be the smallest row and column reachable from a cell $$$(i, j)$$$.

Then the minimum $$$x_1$$$ for a given $$$x_2$$$ is $$$max(mincolumn_{i, j})$$$ where $$$1 \leq i \leq n$$$, $$$1 \leq j \leq x_2$$$ and $$$maxrow_{i, j} \gt 1$$$.

This can be calculated quickly for all $$$x_2$$$ with an easy observation — Since the function is max, $$$x_1$$$ never decreases as $$$x_2$$$ increases. So we can just iterate first on increasing $$$j$$$ then on $$$i$$$ to calculate the answer in $$$O(n \times m)$$$ time.

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

int n, m, q;
int32_t main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m;
    vector<vector<int>> grid(n, vector<int>(m)), minrow(n, vector<int>(m, n)), mincol(n, vector<int>(m, m));
    for(int i = 0; i < n; i++)
    {
        string s;
        cin >> s;
        for(int j = 0; j < m; j++)
            grid[i][j] = (s[j] == 'X');
    }
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
        {
            minrow[i][j] = i;
            mincol[i][j] = j;
            if(i > 0 && !grid[i - 1][j])
            {
                minrow[i][j] = min(minrow[i][j], minrow[i - 1][j]);
                mincol[i][j] = min(mincol[i][j], mincol[i - 1][j]);
            }
            if(j > 0 && !grid[i][j - 1])
            {
                minrow[i][j] = min(minrow[i][j], minrow[i][j - 1]);
                mincol[i][j] = min(mincol[i][j], mincol[i][j - 1]);
            }
        }
    vector<int> minl(m);
    int curminl = 0;
    for(int j = 0; j < m; j++)
    {
        for(int i = 0; i < n; i++)
            if(minrow[i][j] != 0)
                curminl = max(curminl, mincol[i][j]);
        minl[j] = curminl;
    }
    cin >> q;
    for(int i = 0; i < q; i++)
    {
        int l, r;
        cin >> l >> r;
        l--; r--;
        if(minl[r] <= l)
            cout << "YES\n";
        else
            cout << "NO\n";
    }
    return 0;
}

My solution is if there's an empty cell on column i, and it is blocked, then it is bad.

So I use dp to check the furthest left a cell could and store the max for all cell of that column, then use segment tree to check max(l,r) <= l

I aolved with seg tree tho idk it was the only soultion that came into my mind

It suffices to prove that, for a given tree and $$$u,v,w \in V$$$, edges which appears in exactly one of the simple path $$$uv$$$ and $$$vw$$$ forms the simple path from $$$u$$$ to $$$w$$$. This should be verified easily.

First let's think of it as a dfs tree after getting a dfs tree.

what you can do if you have a range of edges of ones on this tree is that you remove this range and replace it with one edge with 1 which is a back edge this edge will also have a 1 and since this edge is mapped to a range of edges it's obvious that you can't make it into a 0.

I think it's the same with spanning trees the difference is the edges are not back edges but they are still mapped to one range of edges.

The existence of an example is equivalent to all nodes participating in an even number of paths as endpoints. => is trivial, <= can be shown easily to hold for any tree (consider any edge, if it is used an odd number of times, the sum of usages in one of the subtrees would be odd as well).

path from u to v = (path from u to root) xor (path from v to root)

Suppose we can find $$$p_n$$$ in at most $$$n$$$ queries, then we can find all other values in at most $$$n$$$ queries by increasing $$$a_1, \ldots, a_{n - 1}$$$ or $$$a_n$$$ by the required amount for it to match each value $$$1 \leq k \leq n$$$, one at a time.

As for finding $$$p_n$$$, suppose I set $$$a_1, \ldots, a_{n - 1} = 1$$$ and $$$a_n = x$$$, then we will only get $$$0$$$ as a response if $$$p_n + x > n + 1$$$ (or $$$p_n + x > (n - 1) + 1$$$ if $$$p_n$$$ is $$$n$$$). So we can just iterate on all values of $$$x$$$ from $$$2$$$ upward and see the first value for which the condition fails to hold to exactly identify $$$p_n$$$.

#include <bits/stdc++.h>
#define int long long
using pii=std::pair<int,int>;
using namespace std;

int n, query_cnt = 0;

int query(vector<int>& vals)
{
    assert(vals.size() == n && ++query_cnt <= 2 * n);
    for(auto x : vals)
        assert(x >= 1 && x <= n);
    cout << "? ";
    for(auto x : vals)
        cout << x << " ";
    cout << endl;
    int resp;
    cin >> resp;
    return resp;
}

int32_t main()
{
    cin >> n;
    vector<int> ans(n, 0);
    for(int laval = 1; laval <= n; laval++)
    {
        if(laval == n)
        {
            ans[n - 1] = 1;
            break;
        }
        vector<int> queryvals(n, 1);
        queryvals[n - 1] = laval + 1;
        int resp = query(queryvals);
        if(resp == 0)   // p_n + laval (+ 1) = n + 1 (+ 1)
        {
            ans[n - 1] = n + 1 - laval;
            break;
        }
    }
    assert(ans[n - 1] != 0);
    for(int i = 1; i <= n; i++)
    {
        if(i == ans[n - 1])
            continue;
        if(i < ans[n - 1])
        {
            vector<int> queryvals(n, ans[n - 1] - i + 1);
            queryvals[n - 1] = 1;
            int resp = query(queryvals);
            assert(resp != 0 && resp != n);
            ans[resp - 1] = i;
        }
        else    // i > ans[n - 1]
        {
            vector<int> queryvals(n, 1);
            queryvals[n - 1] = i - ans[n - 1] + 1;
            int resp = query(queryvals);
            assert(resp != 0 && resp != n);
            ans[resp - 1] = i;
        }
    }
    assert(ans.size() == n);
    set<int> sanity_check;
    for(auto x : ans)
        sanity_check.insert(x);
    assert(sanity_check.size() == n);
    cout << "! ";
    for(auto x : ans)
    {
        assert(x >= 1 && x <= n);
        cout << x << " ";
    }
    cout << endl;
    return 0;
}

Hint: Create an undirected graph with N vertices where edge u-v indicates abs(p[u]-p[v])=1.

If you figure this out it's simple. All that is left is running a dfs.

You can also solve it with a tighter query limit using binary search:

The idea is if you find the last element, you can find every other element in $$$n$$$ queries. We can find the last element by performing a binary search to find $$$p_n - min(p_{n - 1}, p_{n - 2}, ...)$$$. If this value is negative, it means the last element is 1. So we only end up consuming $$$n + logn$$$ queries :)

I think, you should delete this line:

EDIT: It still struggles with test 4, Idk what else is wrong.

Its 99.99% purposeful unsuccessful hacks to get last place. I've done it in the past when I felt I was getting too worried about my rating to the extent where the nervousness was ruining contests for me.

Its trivial to copy paste the same input and change 1 value (can't use the same input twice on the same person) and make 20-30+ hacks / minute to quickly send yourself to last place.

You are defining an array locally (inside of a function) rather than globally. The locally-defined array can contain anything at initialization.

the array you defined is not global, if you didn't clear it then it just contain garbage :D

Try to solve 3 problems.

It is sad that I can solve D if 5 more minutes are given :D
also 9 problems deserve way more than 2:15

The rating calculation for new accounts is different. Maybe this is the reason.

if b is on path between a and c, than dist(a,b)+dist(b,c)=dist(a,c)