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

Автор nifeshe, 2 месяца назад, По-английски
Rating predictions

2056A - Shape Perimeter

Hints
Solution
Code

2056B - Find the Permutation

Hints
Solution
Code

2056C - Palindromic Subsequences

Hints
Solution
Code

2056D - Unique Median

Hints
Solution
Code

2056E - Nested Segments

Hints
Solution
Code

2056F1 - Xor of Median (Easy Version), 2056F2 - Xor of Median (Hard Version)

Hints
Solution
F1 code
F2 code
Разбор задач Codeforces Round 997 (Div. 2)
  • Проголосовать: нравится
  • +96
  • Проголосовать: не нравится

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

i feel so dumb after seeing B's solution because I used topological sort and then sorted all the elements with equal entry times in descending order

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

    same mistake tho. In the hindsight B is actually a great problem with multiple solutions.

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

    Here is another way to solve B -> We will construct the array by traverse each string and with each traversal we will get value at one index. permutation numbers : i = 1, 2, 3, ... Lets take i = 3. Now to find where we will place 3 in our array we simply traverse the third string and count the number of '1's before 3rd index in that string and number of '0's after third index. That gives us the index at which 3 will come. Why this works? Think Yourself gg:)

    Code

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

    did gpt tell u that

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

    an easy solution that i came up with is start placing elements in increasing order. For each element $$$i$$$, count the number of connections $$$j$$$ such that $$$j > i$$$. for example $$$i=1$$$ , and it's connected to $$$j=3$$$ and $$$j=5$$$, so $$$count=2$$$ start from the back of the array to find the second empty position and place $$$1$$$ there. here is my submission https://codeforces.net/contest/2056/submission/301478898

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

      Hey, i thought of an almost same solution but there is something that i am getting wrong. I implemented it by checking for each index in increasing order, the place from the back of array where it should be placed based on the count, say j. But if index j has some value already placed there, keep checking if any index k, (k=j-1;k>=0;k--) is empty and place the number there. Basically, How to process when the count that we calculate is same for 2 different numbers??

      here is my submission,301471228

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

        What ur doing there is partially correct. Here is an example where it will fail

        3
        000
        001
        010
        

        this should output 2,3,1 but your code would yiled 3,2,1

        the problem is that, for example count(2) = 1, in my code it means "I need at least 1 zero after me" , but your code says "go to second position from the back and find me the first empty slot" replace your loop with this and i think it should work

                // get next available slot by having at least 'c' zeros
                ll j = n - 1;
                for(j=n-1;j>=0 && c;j--)
                    if(ans[j]==0) c--;
                // if slot is full, skip it
                while(j>=0 && ans[j]!=0)--j;
                ans[j] = i+1;
        
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Exact same mistake, but I rewrote a recursive solution after the contest ended (something similar to Quick Sort I'd say).

    submission

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

    It is topo sort. Add fake dependencies from higher to lower if there isn't an edge from lower to higher..

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

B killed me and C buried me :(

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

Why the B looks easy here:(.I've done converting the undirected graph in directed based on pi<pj and then i had applied topological sort .Feelin dumb man

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

How did every single person predict that B was lower rated than C? C was much easier IMO. I think we need more lower rated testers.

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

C's solution can be put fairly simple:

Answer will be of the pattern:

[1, 1, 2, 3, 4, ..... ,n-2, 1]

then the max length f(a) is 3

and the count g(a) is: (n-2) + (n-3) = 2*n-5, which is greater than n for n >= 6.

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

    bro, you are fucking right

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

    Yes, it was somewhat obvious like this, but why the problem C is made like this...i thought we have to maximize this f(a). And that seems to be a problem...and idk.. plz share if anyone have idea how it gonna work in that case...

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

      if you maximize f(a) it will be equal to n like 1 1 1 1 1 1 1 1 1 you can insert 2 in between n is odd

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

        But maximizing f(a) like this doesn't guarantee to make g(a)>n and g(a) should always get 1 like this right? I meant maximizing f(a) while meeting the same conditions, like in sample 2 f(a) could be made 5 but as of now we solved it by keeping it as 3 only..!

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

          g(a) is no of palindromes with length==f(a) if you take f(a)=n then how will u find other palindrome of length n, g(a) will be always one and then for n>1 answer will be wrong as g(a) has to greater than n

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

    yeah same approach :)

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

The difficulty distribution of this match is simply a disaster.

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

Another solution for $$$C$$$ is for $$$n > 6$$$ construct the array $$$1,2,$$$ $$$[3...n - 2],$$$ $$$1,2$$$. Most elements will be part of two palindromes of length $$$3:$$$ $$$1,x,1$$$ and $$$2,x,2$$$. For $$$n = 6$$$ use the one in the example.

Edit: Nevermind I just realized this was mentioned in the editorial.

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

In C, If you realise that g(a) is 3n-11 for 6, and notice that 11 is a constant, and for each additional n, it will increase by 3, you notice that using the first construction directly solves the problem.

1,1,2...1,2 works because it follows 3n-11.

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

Any idea which test case is failing for my submission: 301434979 for Problem B. I used a bubble-sort-like approach.

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

It seems like i completely overcomplicated D, because i solved it in $$$O(nA^2 + A^4)$$$.

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

For C, I just took sample solution with 15, it already gives 190 and just pushed numbers in the end like 16 17 18 ... n.

The same way, for 15 > n >= 9 I took sample solution for 9, as it gives 24.

For 6 they already gave answer.

So I only needed to solve by hand 7, 8, which I did on paper.

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

    for 7, 8, you can also just assume adding 4 in the middle of the array for 6 will give at least 1 new palindrome, and adding a 5 after that will give at least 1 more palindrome, and you're guaranteed to not create a longer one

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

    This is the smartest solution.

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

why lasts codeforces rounds are random ? rarely to find topics .. number Theory or graphs in first 3 problems ?!! can any one explain

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

What's with the constraint of n in C? Why is it so small?

Also you can just put random distinct numbers at the end of the 3rd sample answer, as g(a)=190 which is >=100

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

Tried sort in B and failed, using another 30 min to ponder another graph solution (almost like dijkstra)... absolutely overkill for B.

Learned, though C is really too easy for some reason.

Still I conclude C << B.

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

A different way to approach D:(Probably easier?)

Solution :

Solution

My submission

Hope you understand the solution, if you have any queries feel free to ask, and I'll try to help if possible.

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

    I did this approach but for "good" subarrays and ended up with the subproblem:

    Given two arrays, Count all pairs i<j such that a[i] < a[j] and b[i]<b[j].

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

      The problem can be solved with CDQ D&C, however the time complexity is $$$O(An \log^2n)$$$

      I don't know what exactly your $$$a$$$ and $$$b$$$ is. But in my case, I found out that if i < j, then a[i] > a[j] and b[i] > b[j] can't happen at the same time. So the problem become "Count all pairs i,j such that a[i] < a[j] and b[i]<b[j]" and can be solved $$$O(An \log n)$$$ using BIT.

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

        Could you elaborate on your method? I first considered a fixed median x. Next, I defined ps[i] to be the prefix sum of the number of elements less than x (up to and including index i). I did this also for the number of elements greater than x.

        Now the condition I got was finding all pairs i<j such that ps'[j]<ps'[i] for both types of prefix sums where ps'[i] = ps[i]-i/2. Not sure where to go from here since it seems like a 2D inversion count problem.

        If possible, could you define what arrays a and b you got and show how to implement it with one BIT.

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

          Let's call the prefix sum of the number of elements <=x $$$ps1_i$$$, and for >=x, let's call it $$$ps2_i$$$.

          For a subarray $$$a_{i+1},...,a_{j-1},a_j$$$ (tha a in the problem statement) to be good and have a median x, $$$ps1_j-ps1_i, ps2_j-ps2_i >= \frac{j-i+1}{2}$$$ need to be satisfied.

          So we can define $$$A_i$$$ as $$$2ps1_i-i$$$ and $$$B_i$$$ as $$$2ps2_i-i$$$, and the problem becomes a 3D inversion count problem (count i<j, A_j<A_j, B_i<B_j). However, (i<j, A_i>A_j, B_i>B_j) can't happen because that means $$$ps1_j-ps1_i, ps2_j-ps2_i < \frac{j-i+1}{2}$$$ which contradict to the fact $$$ps1_j-ps1_i+ ps2_j-ps2_i >= j-i$$$. (equal happens when there is no x in the subarray)

          So i<j isn't necessary, and the problem becomes a 2D inversion count problem.

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

          301616593

          Of course not optimal for this task, but was curious to try.

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

    i checked out your code, but i am not able to understand how you are making use of UB / LB methods here. could you pls explain what this piece of code does? also, what will be the complexity for your solution?

    for(auto [_,v]:mp){
            for(int i = 0;i<v.size();i++){
                int p = v[i];
                auto it = upper_bound(pos.begin(),pos.end(),p);
                if(it==pos.end()){
                    continue;
                }
                int num = pos[it - pos.begin()];
                auto it2 = lower_bound(v.begin(),v.end(),num);
                int idx = v.end()-it2;
                ans += idx;
            }
        }
    
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Very nice problem F!(however probably too hard for div2)

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

    I think someone new to CP with strong math olympiad background can reasonably solve F1. And yeah, F2 is there to entertain out of contest reds even if it's not too much harder than F1 given enough CP experience

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

I don’t understand the editorial for D. For even length subarrays, when we are testing for x as the median, the bad scenarios seems a lot more than what the editorial depicts.

For instance, if we are testing for 9, the array 1 1 1 9 is certainly bad, but the number of numbers less than or equal to 9 is 4, not 2 as in the editorial .

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

    However, the sum of the array [1,1,1,9] is not 0, it is -4. You only count arrays where sum is 0 and the number appears at least once.

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

    Let's name the [(r-l+1)/2]-th element X and [(r-l+1)/2 + 1]-th element Y.

    A bad array has X!=Y.

    The editorial enumerate the X from 1 to 10, and count the above bad array when X is enumerated as the [(r-l+1)/2]-th element.

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

I have the dumbest solution using BST to solve B
301463165

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

Why we only update the cnt array when a[i] equal to chosen digit? I may think that when the conditieon is enough when we firstly seen the digit x? Like: n = 6, a = {1, 4, 4, 3, 1, 4} with chosen digit = 3. It only update when we at index 4 (a[4] = 3), so that we have {1, 3, 4, 4}. But there are also in the index 6, we can have an bad array {1, 1, 3, 4, 4, 4}, but in this case the author not update the cnt array.

Code:

if(a[i] == x) {
  while(j <= i) {
    cnt[pref[j]]++;
    j++;
  }
}
»
2 месяца назад, # |
Rev. 3   Проголосовать: нравится +3 Проголосовать: не нравится

The constraints in the question C were kind of redundant because, I solved directly from visible cases. The answer for n=15 the third case they have given is 198, so I directly gave the same array as output for n>=15 followed by 16, 17, 18... until the required length is achieved. And for n=9 => the answer was 24, so 9-15 range is also sorted. So, only ones remaining are 7,8, we can manually generate that by appending some numbers after the given array for n=6.

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

In the solution of D, it's a little confused by using the term "median". It took me some time to realize "median" means the (r-l+1)/2-th smallest number here.

Also, this intended solution is interesting since the observation is apparent but useful, and it seems that only few contestants came up with it.

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

i didnt realize that the solution for b was that simple. i have just started thats why ig. i did something like trying to find a correct candidate from indexes 1 to n in p. if the number of pairs that can be formed from this index to the last is > than the number of edges our candidate should be connected to and also the number of elements that are larger than our candidate that have not been used yet are also greater than the number of edges our candidate should be connected to then skip this candidate and move on to the next one . since that would mean we would definitely connect an edge that is not supposed to be connected. i converted the undirected to directed first for that and then did it. well the contest time was over by the time i did that lol. but it did work when i submitted it later.

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

I did very dumb solution for C.

For n = [6...11] find answer by hand.

For example, I realized that the prefix of "AABCABCDCDD" where different characters stands for different number gives correct answer, and I used it. As you see, we just need 4 different numbers.

Now, divide n to small parts: many 6 and one x from range [6...11]. Solve for small parts separately, with different set of numbers. Then concatenate them to one big array. It's not hard to see it will give you correct answer.

My submission.

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

E is solvable with xor hashing as well: 301474893

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

in problem C 1 1 2 3 4 5 ... 1 the maximum f(a) is 3 the first and the last one will add n-2 and the second and last one will add n-3 so 2*n -5 it worked for n>=6

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

i did something very different for C and it took me an embarrasing amount of time, first ans = [1, 2, 3, ..., n].Then ans[n-1] = 1 and ans[(n-1)//2] = 1, essentially ans = [1, 2, 3, ... (n-1)//2 , 1, (n-1)//2 + 1 ,..., n-2, n-1, 1] and it got accepted as those 1 essentially made f(a) = 3 and g(a) = 2*(n-2).

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

We can even solve D by counting the good subarrays for every fixed median and sum them up.

Here is my submission.

https://codeforces.net/contest/2056/submission/301477712

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

5 00000 00010 00000 01000 00000 for this input jiangly's solution gives 5 3 4 2 1 while solution in editorial gives 5 4 3 2 1 and both solutions get accepted how is 'p' unique then for this case

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

    This is an invalid input as the question mentions that there exists a valid permutation for each test case. No permutation exists for your set of input, as there is an edge between 2 and 4 but no edge between 2 and 3 or 3 and 4. (no place can be determined for 3 here, as if 3 is after 2 then there should be an edge between 2 and 3 or if 3 is before 4 then there should be an edge between 3 and 4)

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

      Isn't the wording for the question stating that, "It can be proven that permutation p can be uniquely determined " is wrong as it clearly states that we can prove , but fails for given testcase

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

        It is guaranteed that there exists a permutation p which generates the given graph.

        This is what the question guarantees. You can't just create any random testcase and say that the permutation is not unique by making two permutations for the test case. In case you do so, the permutations would be wrong i.e. the permutations would generate a different graph than the one in the input. The testcase which As1236 mentioned is invalid, the two different permutations formed by the editorial's code and jiangly's code are both wrong (infact there doesn't exist any permutation that would generate this particular graph) as in in the first permutation "5 3 4 2 1" there should be an edge between 3 and 4 according to the permutation but in the given graph this does not follow, and for the second permutation "5 4 3 2 1" is wrong because there is no edge between 2 and 4 according to the permutation but in the given graph there is an edge between 2 and 4.

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

Thanks for highlighting the unusual limits.

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

I don't seem to have received any rating yet — was this contest unrated?

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

How to solve the C with Binary Search?

Thanks in advance!

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

    Waa... Why the downvotes? A few hours ago, I saw the BS tag and, out of curiosity, I asked. :(( Now the tag has changed, though. :(

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

From F:

For a fixed $$$\text{cnt}$$$, the number of ways to order a is $$$\binom{n}{\text{cnt}_0, \text{cnt}_1, \ldots, \text{cnt}_{m - 1}}$$$. By Lucas's theorem the contribution is odd iff for each set bit in n there is exactly one i such that $$$\text{cnt}_i$$$ has this bit set, and $$$\sum\limits_{i = 0}^{m - 1} \text{cnt}_i = n$$$. In other words, $$$\text{cnt}$$$ has to partition all set bits in $$$n$$$.

Can someone explain this more in detail? I can't connect the dots between Lucas's theorem and this formula.

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

    $$$\binom{n}{\text{cnt}_0, \ldots, \text{cnt}_{m - 1}} = \binom{n}{\text{cnt}_0} \cdot \binom{n - \text{cnt}_0}{\text{cnt}_1} \cdot \binom{n - \text{cnt}_0 - \text{cnt}_1}{\text{cnt}_2} \cdot \ldots$$$

    So $$$\text{cnt}_0$$$ has to be a submask of $$$n$$$, $$$\text{cnt}_1$$$ has to be a submask of $$$n - \text{cnt}_0$$$, etc.

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

    By Luca's theorem we know $$$\binom{n}{k} \equiv 1 \pmod{2} \Leftrightarrow k$$$ contains subset of bits of $$$n$$$ in binary notation.

    Also we have $$$\binom{n}{cnt_0, cnt_1, \ldots, cnt_{m-1}} = \binom{cnt_0}{cnt_0} \cdot \binom{cnt_0 + cnt_1}{cnt_1} \cdot \binom{cnt_0 + cnt_1 + cnt_2}{cnt_2} \cdot \binom{cnt_0 + cnt_1 + cnt_2 + cnt_3}{cnt_3}\dots \cdot \binom{n}{cnt_{m - 1}}$$$, to make lhs an odd number, terms on rhs should all be odd numbers. Consider the last term $$$\binom{n}{cnt_{m-1}}$$$, $$$cnt_{m-1}$$$ should contains subset of bits of $$$n$$$, then consider the previous term before it $$$\binom{n-cnt_{m-1}}{cnt_{m-2}}$$$, $$$cnt_{m-2}$$$ should contains subset of bits of $$$n-cnt_{m-1}$$$ which is exactly bits in $$$n$$$ but not in $$$cnt_{m-1}$$$, then consider previous terms and so on.

    This process is essentially deleting bits from $$$n$$$ and distribute them to $$$cnt$$$, then it become quite intuitive that the above claim is true.

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

you don't have to consider n = 6 / 9 /15 separately.

1 ,1 ,3 ,4 ,5 ,... ,n-1 ,1

has f(a) = 3

and 2*(n-3) + 1 = 2n-5 palindromes! so g(a) > n for n >= 6 which fits the constraints

301414951

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

Solved C like nothing, bricked at B. Nice Problemset. Here's my weird solution to C. Solution

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

For D, I was like with a median of x: |the number of elements larger than x — the number of elements smaller x|<|the number of element of x in the sequence|. And I cannot find a good algorithm. It was too counterintutive for me to count "bad subarrays".

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

i think i have a better solution for c, i hope you'll like it :D it only require hardcoding for n=6 i just messed it up during the contest in second for loop where i started it from n/2 and not n/2+1

anyways good contest ~~~~~~~~~~~~ //this is code

include <bits/stdc++.h>

using namespace std;

define fio ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)

define ll long long

void solve() { int n; cin>>n; vectortemp={1 ,1 ,2 ,3 ,1 ,2}; if(n==6){ for(auto it:temp){ cout<<it<<" "; } cout<<endl; return; } vectorarr(n); int j=1; for(int i=0;i<=n/2;i++){ arr[i]=j; j++; } j=1; for(int i=n/2+1;i<n;i++){ arr[i]=j; j++; } for(auto it:arr){ cout<<it<<" "; } cout<<endl;

}

int main() { fio; ll t; cin >> t; while (t--) { solve(); } return 0; } //this is code ~~~~~~~~~~

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

I solved C differently. In sequence [1,2,3,…,n] I changed a[⌊(n+1)/2⌋]=1 and a[n]=1, so in this new sequence f(a)=3 and g(a)=n-3+n-2=2n-5 which is enough for n≥6. Here's my solution 301421526

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

for c just create sequence such that length of longest palindrome is 3 , putting 1 ....1 1 here all elements in between create 3 length palindrome now we have (n-2) palindromes ready now do it with 2 it will always exceed n>

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

~~~~~~~~ t = int(input()) for q in range(t): n=int(input()) buffer=[0]*(n+1)

adj=[buffer]
for i in range(n):
    adj.append(list('0'+ input()))
for i in range(len(adj)):
    for j in range(len(adj[0])):
        adj[i][j]=int(adj[i][j])

#print(adj)
arr=[]
for i in range(n,0,-1):
    arr.append(i)
#print(arr)
i=1
val=None
while(i<n):
    j=i-1
    #print(i)
    val=arr[i]

    while j>-1:
        if adj[val][arr[j]]==1:

            j-=1
            if j==-1 or (j>=0 and adj[arr[i]][arr[j]]==0):
                #print(j+1,val)
                arr.insert(j+1,val)
                #print(arr)
                arr.pop(i+1)
                i+=1
                break
        else:
            i+=1
            break
print(*arr)

~~~~~~~~~~~~~~~~

I did B this way: first arrange in descending order 5 4 3 2 1 now 4-->5 so 4 5 3 2 1 now 3 is connected to 5 but not 4 so: 4 3 5 2 1 now 2 is to 3 and 5 4 2 3 5 1 now 1 is to 3 5 4 2 1 3 5.

managing the loop parameters was a bit confusing but it is easy to get and works all good.301490247

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

geeked on b

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

I am too dumb for Smart contests.

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

I did so dumb for C.I never think that f(a) can be 3 for any input,I can't solve constructive problems:(

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

In B, i came up with the idea that if can device some sort of point or ranking mechanism for each vertex of the graph based on the edges the vertex makes, either to a greater value vertex or a smaller value vertex. Then i can use those points to arrange them in order.

~~~~~~~~~~~~~
// cpp
vector<pair<int,int>> vpr;    
for(int i=0;i<n;i++)
{
    cin>>s;
    int pnt=0;
    for(int j=0;j<n;j++)
    {
        if(j<i&&s[j]=='1')
        {
            pnt++;
        }
        if(j>i&&s[j]=='0')
        {
            pnt++;
        }
    }
    vpr.push_back({pnt,i+1}); 
}
vst(vpr);
for(int i=0;i<n;i++)
{
    cout<<vpr[i].second<<" ";
}
 cout<<endl;
   ~~~~~~~~~~~~~~

I increased a point if there was an edge from the current vertex to a smaller vertex, and increased a point when there was no edge from the current vertex to a greater vertex.

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

How come c is this simple,

void solve(){
	int n;cin>>n;
	vi pres(n+1 , 0);
	pres[1] = 1;
	pres[2] = 1;
	pres[3] = 2;
	pres[n-1] = 1;
	pres[n] = 2;
	int counter = 3;
	rep(i , 4 , n-2){
		pres[i] = counter;
		counter += 1;
	}
	rep(i , 1 ,n )cout << pres[i] << " ";
	cout << "\n";
}

wasted whole time on B noooooooooooooooooo.

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

Why the type of was_single is int in the solution of E

为什么在 E 题题解里面 was_single 的类型是 int

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

the wording of B's problem statement is extremely confusing, especially when the notes switch back and forth between i, j, pi, and pj

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

1 4 0110 1001 1000 0100

For this test case B no. solution doesn't work!! Why??

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

My B solution constructs a btree with a starting root node of 1

Then it will iterate nodes i from 2 to n

For each i, it will be attached to the btree like this:

void attach(btree* root, i):
    if adj[root->val][i]:
        if root->right == null:
            root->right = new node(i)
        else:
            attach(root->right, i)
    else:
        // same as above, but for root->left

Then the answer is just the inorder traversal of this btree.

Code: https://codeforces.net/contest/2056/submission/301423733

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

    Your code output is 4 1 3 2 But if you draw a graph for the given testcase you will notice 2 and 4 are connected to each other but this output shows that 4 is not connected to any vertex.

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

      I think the problem implies that the permutation comes first, then generates a graph from that.

      So if we start from the permutation 4 1 3 2, the constructed graph will be:

      0110 
      1000 
      1000 
      0000
      

      And we're only given this constructed graph, then we have to figure out the underlying permutation.

      So I think 1 4 0110 1001 1000 0100 is an invalid input because no such permutation of length 4 that we pick will generate this input's graph.

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

        But in the problem statement they indicates that there always exist a permutation for any given input and also how can i first generate the permutation then graph. It's like showing perfect output without knowing the input. I think it's the the mistake of the problem setter for not giving any option like printing -1 (impossible) for this kind of inputs.

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
void solve()
{
    int n, m;
    cin >> n >> m;
    int prevx, prevy;
    ll lastx, lasty;
    ll firsty, firstx;

    for (int i = 0; i < n; i++)
    {
        if (i == 0)
        {
            cin >> prevx >> prevy;
            firstx = prevx;
            firsty = prevy;
            prevx = firstx;
            prevy = firsty;
        }
        else
        {

            int tempx, tempy;
            cin >> tempx >> tempy;
            lastx = prevx + tempx;
            lasty = prevy + tempy;
            prevx = lastx;
            prevy = lasty;
        }
    }
    if (n == 1)
    {
        cout << m * m * 2 << endl;
        return;
    }
    cout << 2 * ((m + lastx - firstx)) + 2 * (lasty - firsty + m) << endl;
} 

this code is giving me error on test case 2 what am i doing wrong here

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

Can someone explain why my soln is wrong ? Thanks

https://codeforces.net/contest/2056/submission/301536267

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

Submissions of C is more than B. That denotes which one is more difficult.

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

another correct solution for C was to print 1 1 2 3 1 2 3 1 2 3... didnt know that it worked lmao

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

    I also solve it like this,and I have a proof in Chinese...If you want to see,there is the link.Maybe there are some mistakes.

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

    Then I translate it into English (forgive me if my English is poor).

    We consider a sequence whick looks like $$$1123123\cdots1$$$ (it is ended with $$$1$$$). Let $$$3k+2$$$ be the length of it (k is a positive integer), so it has $$$k+2$$$ 1s.

    If $$$k+2$$$ is odd:

    It is easily to find that $$$f(a)=k+2$$$.

    Then we can calculate the number (isn't all context):

    $$$111...1...111$$$: $$$1$$$

    $$$111...2...111$$$: $$$2k$$$

    $$$111...3...111$$$: $$$2k$$$

    It has already been $$$4k+1$$$ now!

    If $$$k>3$$$, it has already been more than $$$3k+2$$$ (even $$$3k+4$$$).

    else, you can calculate by hand.

    else:

    $$$f(a)=k+3$$$

    And $$$111...2/3...111$$$ has $$$2$$$ available.

    We exchange the pairs of $$$2$$$ (or the pairs of $$$3$$$) and the pairs of $$$1$$$, it has already been $$$2*2^{\frac{k}{2}}$$$! And it is big enough.

    Q.E.D

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

nice problem!but i think E is too simple

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

Problem C. Palindromic Subsequences. Video Editorial Solution Link : https://youtu.be/LmlZuqndrHg?si=Lmv00zHhXvMck2WQ

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

For the D solution, could someone explain what does the vector pref and cnt in the code represent?

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

This is best contest for me. I became expert in it.

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

for F2, it is useless to calculate SOSDP and can be computed in a linear time using bitwise arithmetic.

$$$O(k\log m)$$$ reference code, available more discussion were easily optimised to linear time :D

  • »
    »
    7 недель назад, # ^ |
    Rev. 5   Проголосовать: нравится 0 Проголосовать: не нравится

    I can't see your submission, it says I'm not allowed to view the requested page. I'm unable to understand the SOS-DP part of the editorial. Can you explain your method? (edit: I saw your code can't and I couldn't understand it either, any help would be would be appreciated, thanks in advance.)

    • »
      »
      »
      7 недель назад, # ^ |
      Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится

      For $$$0\le x<m$$$, we write out the formula and it is:

      $$$ (\sum_{k=1}^n\sum_{i=1}^{k-1}C(x,i)C(m-x-1,k-1-i)\sum_{a_1+...+a_k=n,1\le a_1\le a_2\le ...\le a_k} [a_1+...+a_i<med][a_1+...+a_{i+1}\ge med]C(n,a_1,a_2,...,a_k))\mod 2 $$$

      Simplifying gives:

      $$$ \sum_{k=1}^nC(x,k-1)Stirling_2(popcount(n),k)\\ $$$

      Enumerate the values of $$$k$$$ and then compute the xor sum of all $$$x$$$ such that $$$0\le x<m$$$ and $$$k-1$$$ is a bitwise subset of $$$x$$$. Then enumerate the first different position to the left of $$$x$$$ and $$$k-1$$$ and the xor sum can be easily computed.

      The complexity is $$$O(\log n\log\log n)$$$. It can be optimised to $$$O(\log n)$$$ using bitwise operations to find the first, second and third 0 of $$$k-1$$$ to the right.

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

there is a easier way to solve problem B sunbmission

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

D's editorial just blew my mind , such an elegant solution !

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

for D, i fixed the median $$$x$$$ ,and tried to count the number of good subarrays whose median is exactly $$$x$$$.
however i failed.
so i wonder could someone give me a solution to forementioned subproblem

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

Hi, I have an issue with problem B.

For the input:

1
4
0110
1011
1100
0100

there are several solutions that got AC but produce different results. For example:

These are the top 4 solutions. First of all, this contradicts the problem statement, which says "It can be proven that permutation p can be uniquely determined". Secondly, none of these "permutations" seem to resemble the original graph.

So what's happening here? Can someone help me understand what is wrong?

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

    The input you gave is not correct. To understand this, we can model the undirected graph as a directed one with edges directed from $$$i \rightarrow j$$$ if $$$i < j$$$.

    Now since we have edges between $$$p_i \rightarrow p_j$$$ if $$$p_i < p_j$$$ and $$$i < j$$$, this setup ensures the transitivity of edges, ie having edges between $$$i \rightarrow j$$$ and $$$j \rightarrow k$$$ certianly implies we must have an edge between $$$i \rightarrow k$$$.

    Hence in your input, there must be an edge between $$$1$$$ and $$$4$$$.

    Input:

    1
    4
    0111
    1011
    1100
    1100
    

    Answer 1 2 4 3

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

      Thanks for your answer. I understand the fact that writing the graph in form of a permutation makes it require the transitivity of edges. But the problem statement doesn't really have any restriction related to this for the input graph. That's why I got confused.

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

        It is guaranteed that there exists a permutation $$$p$$$ which generates the given graph.

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

          Wow, I've read the statement atleast 5 times and only now I see this, thanks.

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

in sollution D line 8 (this shoulld be if instead of iff) "iff ∑i=lrbi=0" ."

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

For problem D, my idea was to count all subarrays of odd length using sum of first n terms formula of AP and then good subarrays of even length, but the problem with this approach is the given constraint, n can be 10^5. So If I will calculate for all even length subarray one by one then I'll get TLE.

Editorial is saying that count number of bad subarrays then subtract it with total number of subarrays. How this approach is avoiding traversing the array again and again for all subarrays? Also, didn't got the intuition that why someone should think in this direction.

Is there any other approach which is easy to understand and intuitive?

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

Doubt for problem D.

Approach: I want to count total number of median arrays for each median. So basically,

l - 2x >= 2 [less, less, less, m, m, >=m, >=m, >=m] (for array size 8 having median m)

l - 2y >= 2 [<=m, <=m <=m, m, m, more, more, more] (for array size 8 having median m)

x: total number of elements strictly smaller than the current median

y: total number of elements strictly greater than the current median

l: size of the array under inspection(here is 8)

From this we can see that if we store values of i - 2*x and i - 2*y then for some index j we can query for index i falling on same parity(if the current index is odd only query odd or vice versa. did this so that length is always even and I don't count for odd index) having values <= 2.

Basically current index j and some seen index i,

$$$j - 2*x1$$$ we have now [x1: from start till index j, how many are less than current median]

$$$(i-1) - 2*x2$$$ we have stored [x2: from start till index i, how many are less than current median]

If we subtract we get,

$$$j-(i-1) - 2*x$$$ [x: from i to j how many elements are less than current median]

So query at each index j for values such that (i-1) - 2*(x2) should be <=2

So now the problem is given an array like [ {-1,-2}, {-4,-6}, {-8,-2} ... ] find the count of all values for current pair(mx,my) such that x <= mx-2 and y <= my-2. Looks like a 2D co-ordinate search. Nice.

Either you can find set union or 2D search. I went for the latter and used 2D segment trees. I got a time complexity of $$$O(10 * n * log^2(n))$$$ [ 10 median, for each array element, 2D segment tree search + insert ] which is not passing as you can see here. (Adding n for -ve values. The value can be max n - 2*n which is -n add n to make it 0. So 0 to 2n)

Can someone drop a little hint. I will really appreciate it. I don't really understand the PIE even after reading the editorial and its very counter-intuitive for me.

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

A better way to code problem C without handling n=6 case separately : 302147317

»
7 недель назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

For anyone who is stuck trying to understand the solution to D:

When it says "If there is no x in [l,r], then the median of a[l,r] trivially can't be equal to x.", it is refering to an even array where the "median" is the left part of the median. Meaning that we want to find an array where the left median is x and the right is not x (making it a bad array). We do not need to check for cases like [5, 7] when x == 6 because it is caught when x == 5, therefore we are only concerned with cases of b[l, r] == 0 when there contains x.

A side note: the solution doesn't need to check for when x == 10 since the b array would always be full of -1 since the bounds of a[i] are always less than or equal to 10.

»
6 недель назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Editorial solution for problem C is kind of overcomplicated. Consider this sequence of length n for n >= 6: [1 1 2 3 4 ... n — 2 1] We have n — 2 + n — 3 = 2n — 5 palindromic subsequences of length 3; as it must be larger than n: 2n — 5 > n => n > 5, which meets the constraint. Hence, we just need to output the sequence: [1 1 2 3 4 ... n — 2 1]

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

How to solve problem d using dp ?

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

Alternative solution to question C (using segment Tree):

#include <bits/stdc++.h>

using namespace std;

const int N = 105;

int t[4 * N];

void upd(int p, int x, int tl, int tr, int v) {
    if (tl + 1 == tr) {
        return void(t[v] = x);
    }
    int tm = tl + tr >> 1;
    if (p < tm) {
        upd(p, x, tl, tm, v * 2 + 1);
    } else {
        upd(p, x, tm, tr, v * 2 + 2);
    }
}

int get(int p, int tl, int tr, int v) {
    if (tl + 1 == tr) {
        return t[v];
    }
    int tm = tl + tr >> 1;
    if (p < tm) {
        return get(p, tl, tm, v * 2 + 1);
    } else {
        return get(p, tm, tr, v * 2 + 2);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int tst;
    cin >> tst;
    while (tst--) {
        int n; cin >> n;
        upd(n - 1, 1, 0, n, 0);
        upd(n - 2, 1, 0, n, 0);
        for (int i = 0; i < n - 2; ++i) {
            upd(i, i + 1, 0, n, 0);
        }
        for (int i = 0; i < n; ++i) {
            cout << get(i, 0, n, 0) << " ";
        }
        cout << "\n";
    }
    return 0;
}