culver0412's blog

By culver0412, 14 months ago, In English

Thanks for participating, and happy Easter!

1816A - Ian Visits Mary

Editorial
Implementation
Remark

1816B - Grid Reconstruction

Hint
Editorial
Implementation
Question

1815A - Ian and Array Sorting

Hint 1
Hint 2
Editorial
Implementation

1815B - Sum Graph

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

1815C - Between

Editorial
Implementation

1815D - XOR Counting

Hint 1
Hint 2
Editorial
Implementation

1815E - Bosco and Particle

Hint 1
Hint 2
Observation 1
Editorial
Implementation

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

Key Idea 1
Key Idea 2
Editorial
Implementation (Tester: gamegame)
  • Vote: I like it
  • +130
  • Vote: I do not like it

| Write comment?
»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it -18 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
14 months ago, # |
Rev. 3   Vote: I like it +24 Vote: I do not like it

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.

  • »
    »
    12 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I can't understand your solution. Can you explain it again?

»
14 months ago, # |
Rev. 2   Vote: I like it +4 Vote: I do not like it
Alternative solution to D2C / D1A (code with explanation)
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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
    
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it -13 Vote: I do not like it

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();
    }
}
  • »
    »
    14 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it

    I'm dumb I wasn't getting input to see if my final guess was right.

»
14 months ago, # |
Rev. 3   Vote: I like it +66 Vote: I do not like it

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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.com/contest/1816/submission/201541528

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        14 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +46 Vote: I do not like it

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 :)

»
14 months ago, # |
  Vote: I like it -77 Vote: I do not like it

Div1B is a bad problem.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

Spoiler
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.com/contest/1815/submission/201700734

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
14 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

Test case 1
Test case 2
Test case 3
»
14 months ago, # |
  Vote: I like it +3 Vote: I do not like it

The div is unrated?

»
14 months ago, # |
Rev. 3   Vote: I like it +5 Vote: I do not like it

culver0412 Just found this Easter Egg! image

»
14 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

can some one help me, why my solution 201888165 is giving i = -1 for the output? problem : 1815B - Sum Graph

  • »
    »
    14 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What I see is you didn't input $$$1$$$ or $$$-2$$$ after outputting the answer.

»
14 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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

Approach
»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    14 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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].

»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

editorial code of 1815A is giving output "YES" for following test case:

n = 5
a = [2, 3, 1, 4, 3]

but when I tried to perform operations by hands I found answer should be NO, am I missing something, can anyone please explain the sequence of operations to make the array a in non-decreasing order.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is a high-quality contest!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Im just curious, how do you solve the minimum number of jumps problem for Div2A?

»
9 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    9 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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?

»
5 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.