Блог пользователя culver0412

Автор culver0412, 19 месяцев назад, По-английски

Thanks for participating, and happy Easter!

1816A - Ян навещает Мэри

Editorial
Implementation
Remark

1816B - Реконструкция таблицы

Hint
Editorial
Implementation
Question

1815A - Ян и сортировка массива

Hint 1
Hint 2
Editorial
Implementation

1815B - Граф сумм

Hint 1
Hint 2
Editorial
Implementation
Harder version
Solution to harder version

1815C - Между

Editorial
Implementation

1815D - Подсчёт XOR

Hint 1
Hint 2
Editorial
Implementation

1815E - Bosco and частица

Hint 1
Hint 2
Observation 1
Editorial
Implementation

1815F - OH NO1 (-2-3-4)

Key Idea 1
Key Idea 2
Editorial
Implementation (Tester: gamegame)
Разбор задач Codeforces Round 865 (Div. 1)
Разбор задач Codeforces Round 865 (Div. 2)
  • Проголосовать: нравится
  • +130
  • Проголосовать: не нравится

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

In problem D2C / D1A's Editorial, please correct the following line For even n, n−2 is odd...

»
19 месяцев назад, # |
  Проголосовать: нравится -18 Проголосовать: не нравится

what;s s in Let Ti consists of vertices x such that vx=s .

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    I think it should be "Let T_i consists of vertices x such that v_x = i". In other words, T_i consists of all the vertices which shortest distance to 1 is (i-1). It is also true that such x will appear i number of times in the final sequence.

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +24 Проголосовать: не нравится

A slightly simpler solution of 1815A:

The answer is "NO" if and only if n is even and the alternating sum of the elements of A is positive. Obviously the alternating sum is constant and this linear condition is the only condition on elements of A (we can add n-1 linearly independent vectors to A any number of times each). So we can transform A into any other array with the same alternating sum. The only situation where such an array does not exist is when n is even and the alternating sum is strictly positive.

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +4 Проголосовать: не нравится
Alternative solution to D2C / D1A (code with explanation)
»
19 месяцев назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

I posted this on the main blog but I realized that maybe its better to post it here.

Can someone please explain proof of B in editorial in more detail?

In particular, I would like to know what does it mean lowerbound for maximum cost and how do we, from the observations in proof before that, conclude that this is the value of the lowerbound.

In task we need to construct the grid such that minimum cost over all paths is maximized. So I think in order to prove that some construction satisfies the requirements we need to find value C(n) such that for every placement of integers on the grid minimum cost among all paths in the grid is <= C(n). Then we need to show that for our construction minimal cost equals C(n). Am I wrong?

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Editorial contains the formal proof. My intuition for the problem using n = 12 as example is below. To place {1,2,3,4,5,6,7,8,9,10,11,12} into 12 spots, among which 6 has positive contribution to the alternating sums. It always makes sense to place {7,8,9,10,11,12} into the positive spots.

        1 2 3 4 5 6
     1: + - + - + -
     2: - + - + - +
    

    As v[1][1] and v[2][6] are both positive and always included, it always makes sense to place {12,11} into these two spots. A path would pass exactly one of v[1][3] or v[2][2], so it makes sense to place (10,9) into these two spots. I end up placing these 5 pairs (10,9)(8,7)(6,5)(4,3)(2,1) the way below with bigger value in second row. The intuition happens to be right.

         1  2  3  4  5  6
    1:  12  5  9  3  7  1
    2:   6 10  4  8  2 11
    
    • »
      »
      »
      13 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Thanks for this I was struggling with how could this solution be thought of intuitively

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm struggling to understand Div2D's example. How does [1 2 3 4 5 6] comply with the query about $$$p_1$$$ and $$$p_3$$$? The distance between nodes 1 and 3 is 2 in the graph at that time.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    To be clear, the example's description does not mean that we have ruled out [2 3 1 5 4 6] for instance?

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      The example is correct by coincidence. It does not rule out other possibilities.

      This is common for interactive problems. The example mostly boils down to randomly guessing to avoid hinting you about the solution.

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You guess 2 permutations and only 1 of them needs to be correct. In this example the first one $$$(1,4,2,5,3,6)$$$ is correct, so it doesn't matter whether the second one $$$(1,2,3,4,5,6)$$$ is consistent with earlier queries.

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I see, thanks! But the example's solution had not figured out the permutation with certainty, right?

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится +35 Проголосовать: не нравится

I solved Div1D without noticing the pattern for $$$m\geq 3$$$. This DP is still $$$O(\log n)$$$ but works for all $$$m\geq 1$$$.

Let $$$s(l,r)$$$ be the sum of all possible XOR values, and $$$c(l,r)$$$ be the number of possible XOR values, when $$$l\leq a_1+\dots+a_m \leq r$$$. The answer to the original problem is $$$s(n,n)$$$.

If we additionally require the lowest bit of the XOR value must be 0, the set of possible sums are $$$2\lceil\frac{l}{2}\rceil,2(\lceil\frac{l}{2}\rceil+1),\dots,2\lfloor\frac{r}{2}\rfloor$$$, and the number of 1s in the lowest bits of $$$a_1,\dots,a_m$$$ can be $$$0,2,4,\dots,2\lfloor\frac{m}{2}\rfloor$$$. Notice that both of them are set of integers equally spaced by 2. Thus by right shifting all numbers by 1 (that is, removing their lowest bits), we obtain a subproblem where the set of possible sums is again a contiguous interval. More precisely $$$\lceil\frac{l}{2}\rceil-\lfloor\frac{m}{2}\rfloor\leq a_1+\dots+a_m \leq\lfloor\frac{r}{2}\rfloor$$$. The contribution of this subproblem is

$$$ \begin{align} c(l,r)&+=c(\lceil\frac{l}{2}\rceil-\lfloor\frac{m}{2}\rfloor,\lfloor\frac{r}{2}\rfloor)\\ s(l,r)&+=2s(\lceil\frac{l}{2}\rceil-\lfloor\frac{m}{2}\rfloor,\lfloor\frac{r}{2}\rfloor)\\ \end{align} $$$

Similarly for the case where the lowest bit of XOR value must be 1, we have

$$$ \begin{align} c(l,r)&+=c(\lceil\frac{l-1}{2}\rceil-\lfloor\frac{m-1}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor)\\ s(l,r)&+=2s(\lceil\frac{l-1}{2}\rceil-\lfloor\frac{m-1}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor)+c(\lceil\frac{l-1}{2}\rceil-\lfloor\frac{m-1}{2}\rfloor,\lfloor\frac{r-1}{2}\rfloor)\\ \end{align} $$$

We can inductively show that all $$$l$$$'s and $$$r$$$'s for all states at the same depth of the recursion differs by at most 1 from each other. Thus the number of states at each level is bounded by a constant, and the recursion will only involve $$$O(\log n)$$$ distinct states.

»
19 месяцев назад, # |
  Проголосовать: нравится -13 Проголосовать: не нравится

For Div1B/Div2D I have a working algorithm working on my local computer, but the OJ is declining it for some reason. I've tried doing a custom test with what the input would have been and it worked just as intended, but it is still declining it for some reason.

It keeps giving me "wrong answer Wrong + operation format: x = 1 which is not between 2 and 2*n inclusive :( (test case 2)", but I am pretty sure my code doesn't print a "+ 1" unless n=1. Since the boundary for n is n>=2, it should never happen.

Could anyone help me out with what I messed up so I can avoid this on future interactive problems?

#include <vector>
#include <queue>
#include <iostream>
#include <string>
#include <algorithm>
#include <math.h>
#include <unordered_map>
#include <set>
#include <map>

using namespace std;

void solve () {
    int n;
    cin >> n;
    if (n==2) {
        cout << "! 1 2 2 1" << endl;
        return;
    }
    cout << "+ " << n << endl;
    int response;
    cin >> response;
    cout << "+ " << n+1 << endl;
    cin >> response;

    int mx=0, mxIdx=0;

    for (int i=2; i<=n; ++i) {
        cout << "? 1 " << i << endl;
        cin >> response;
        if (response>mx) {
            mx=response;
            mxIdx=i;
        }
    }

    vector<int> dists(n+1);
    vector<int> dist_map(n+1);

    for (int i=1; i<=n; ++i) {
        if (i==mxIdx)
            continue;

        cout << "? " << mxIdx << " " << i << endl;
        cin >> dists[i];
    }
    for (int i=0; i<n; ++i) {
        if (i%2==0)
            dist_map[i]=n-i/2;
        else 
            dist_map[i]=(i+1)/2;
    }

    cout << "! ";
    for (int i=1; i<=n; ++i) {
        cout << dist_map[dists[i]] << " ";
    }
    for (int i=1; i<=n; ++i) {
        cout << dist_map[n-dists[i]-1] << " ";
    }
    cout << endl;
    cout.flush();
    return;
}

int main () {
    int t;
    cin >> t;

    while (t--) {
        solve();
    }
}
»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +66 Проголосовать: не нравится

For D1F we can solve it as follows:

Lemma:Consider a graph with arbitrary initial weights, and for each edge we can add $$$1$$$ to exactly one of its vertices, we can make the final weights different.

Construction:Start from the vertex with the smallest initial weight,and for each step,take an unpicked vertex with smallest initial weight,and for all the unassigned edges connected to it, add 1 to the other vertex. This works in $$$O(n+m)$$$ or $$$O((n+m)\log(n+m))$$$ with set.

For the original problem, we can just reduce it to the lemma by properly assigning values in each triangle. It is clear that we can achieve $$$(+4,+4,+4)$$$ and $$$(+3,+4,+5)$$$ by only using weights $$$1,2,3$$$,and this are enough to handle all the cases if we add $$$(3,3,3)$$$ to each triangle initially and use the lemma.

Submission:201599238.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for div2B did anyone have any other explanation? the editorial seems very involved for a div2B :O

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    We just put odd numbers in 1st row and even in other or vice versa. To maximise the answer we shud take the first and second maximum and put in the first row first element and 2nd row last element and greedily add the remaining elements. U can refer my submission below

    https://codeforces.me/contest/1816/submission/201541528

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      thank you for the reply,

      I was able to make some random stuff during the round to get AC, but I was scared coz I can't prove that my solution is the best. which makes me less confident to submit during contests.

      and that is why I felt this is hard for div2B

      • »
        »
        »
        »
        19 месяцев назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

        Yeah even I took 20 min to figure out. I just randomly took cases for n=4,6 and figured out. Eventually it worked. Greedy solutions will be tough to prove sometimes. But yeah we hv to try grinding it out

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

when will we have delta for div2, I cant wait to be cyan for the first time :v

»
19 месяцев назад, # |
  Проголосовать: нравится +46 Проголосовать: не нравится

For problem D2B, we intended to make a task about parity (the checkered property). However, we noticed that many participants discovered the solution by looking at samples and "proved by AC". In fact, the proof of this solution is very hard considering its position. Sorry if this task wasn't enjoyable for you.

We added some insights on finding the optimal construction in the editorial and made some minor fixes; sorry for the confusion. Still, I hope you had fun participating in the round :)

»
19 месяцев назад, # |
  Проголосовать: нравится -77 Проголосовать: не нравится

Div1B is a bad problem.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

As Rating of Div 1 is already updated but why there is delay in Div 2 rating update?

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Can anyone help me with a testcase where my code-201678387 for problem -C will fail?

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The harder version of D2D/D1B can be also solved by optimizing the editorial solution:)

Spoiler
»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

The interactor of problem D(div2)/B(div1) can be made TLE. Select a case that n>800,add O(n) random x between n/2 and 3n/2, and query n random pairs of nodes.As there are O(n^2) edges in the graph, it takes O(n^3) time for the interactor to answer all the query.

Submission:https://codeforces.me/contest/1815/submission/201700734

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I thought there was some genius algorithm to update the distances for each query

    • »
      »
      »
      19 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Unfortunately, no, it is just a simple BFS (I don't know any genius algorithm to update the distances). So indeed the interactor can be made TLE. However, as far as I know, all the correct solutions only use $$$O(1)$$$ type 1 queries, so this issue shouldn't prevent any correct solutions from getting accepted.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Why is the interactor in D1B space intolerant. I spent almost an hour upsolving this problem just because of that :(

»
19 месяцев назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

C. Between
Some test cases that I got wrong while upsolving:

Test case 1
Test case 2
Test case 3
»
19 месяцев назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

The div is unrated?

»
19 месяцев назад, # |
Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

culver0412 Just found this Easter Egg! image

»
19 месяцев назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

can some one help me, why my solution 201888165 is giving i = -1 for the output? problem : 1815B - Граф сумм

»
19 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

I did not get solution at first after reading editorial but solved Div2C using following method.

Approach
»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Anyone can tell me why my solution for Div1B/Div2D gives the wrong answer on OJ? Also, is there any way to find the code for the interactor for such problems?

  • »
    »
    19 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Checker comment: wrong answer Printed answer is not a permutation :( (test case 1)

    That means your code reported an answer that's not a permutation. Please take a look at your solution and see what has to be changed. If you have any doubts, you can read the tutorial.

    Also, there is no way to find the code for the interactor, unless the authors want to make it public for some reasons.

»
19 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I think the note for 1815F - OH NO1 (-2-3-4) has a wrong explanation for the first test case. According to the problem statement, the weights should be added to (1, 2), (2, 3) and (3, 1) respectively, making the final weights [5, 3, 4, 0].

»
18 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.me/problemset/status?my=on why this code not working,I am unable to figure out after many WA attempts for Div.1 B

»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

This is a high-quality contest!

»
14 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Seems like your official solution on div1 D got an TLE on test #94. I figured out that the problem is you haven't clear the two maps before each subtask XD.

  • »
    »
    14 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I submitted the same code that you submitted, but using C++ 20, and got accepted in 717ms

    I think there is issues on C++ 14?

»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Initializing the Grid:

Begin by setting up a 2D grid. Initially, assign values to specific positions within this grid:

a[0][1] is initialized as 2 * n a[1][n] is set to (2 * n) — 1 Filling the Grid:

Set cur = 1.

Iterate from 0 to n — 1:

Populate the grid in an alternating pattern across rows using the formula a[i % 2][i] = cur, incrementing cur by 1 after each assignment. Reset cur to (2 * n) — 2.

Iterate from 3 to n in steps of 2:

Fill the grid in an alternating column pattern: Set a[0][i] = cur Set a[1][i — 1] = cur — 1 Decrease cur by 2 after each assignment. Printing the Grid:

Visualize the resulting grid after following these instructions, showcasing the unique pattern formed based on the initializations and iterations explained above.