nocriz's blog

By nocriz, 2 weeks ago, In English,
1262A - Math Problem

Writer: RDDCCD

Tutorial
1262B - Box

Writer: RDDCCD

Tutorial
1261A - Messy

Writer: RDDCCD

Tutorial
1261B1 - Optimal Subsequences (Easy Version)

Writer: MikeMirzayanov

Tutorial
1261B2 - Optimal Subsequences (Hard Version)

Writer: MikeMirzayanov

Tutorial
1261C - Arson In Berland Forest

Writers: BledDest, adedalic

Tutorial
1261D1 - Wrong Answer on test 233 (Easy Version)

Writer: RDDCCD

Tutorial
1261D2 - Wrong Answer on test 233 (Hard Version)

Writer: RDDCCD

Tutorial
1261E - Not Same

Writers: nocriz, RDDCCD

Tutorial
1261F - Xor-Set

Writer: nocriz

Tutorial
 
 
 
 
  • Vote: I like it
  • +113
  • Vote: I do not like it

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by nocriz (previous revision, new revision, compare).

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

The tutorial for 1261B — Optimal Subsequences is not ready, but I feel that it is better I post the tutorial soon! That problem is not by me and I hope the tutorial will be available soon.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    I can just post the brief solution:

    • The optimal subsequence for a given $$$K$$$ contains the largest $$$K$$$ values.
    • If the indices with the smallest of these values can be chosen in multiple ways, we want to choose smaller indices.
    • That means we want to sort the sequence of all $$$(A_i, -i)$$$. We get the answer to a query by taking the last $$$K$$$ pairs, sorting the indices in them and taking the $$$id$$$-th of these indices.
    • Easy offline solution: sort queries by $$$K$$$, add pairs one by one, build a sorted array of indices in them either using a treap or some sqrt structure.
»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

Qualifying round for Technocup (competitions for CIS schoolchildren), but tutorial in English only. hmm

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Editorial will be available in Russian soon.

»
2 weeks ago, # |
  Vote: I like it -19 Vote: I do not like it

obviously, its' easy and similar words are not appropriate for editorials. I understand that once you know the solution it obvious. There are thousands of people who were didn't found it obvious.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Which part exactly do you need us to explain? I'll be glad to answer your question.

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it -22 Vote: I do not like it

      A-Messy It's easy to construct a valid bracket sequence, I am puzzled if we can construct any valid sequence? If so probably we put all left brackets to left and right to right side, but I think we need to construct K outer brackets. maybe code solution example would help

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

        65626236 I would recommend you to see tourist's solution.

      • »
        »
        »
        »
        12 days ago, # ^ |
        Rev. 2   Vote: I like it +10 Vote: I do not like it

        I think "valid" is supposed to mean "with exactly K outer brackets". The example given in the tutorial is ()()()()((((())))) for say K=5; so you just put K-1 empty brackets first, then all the left brackets, and finally all the right brackets. This will always give you a valid bracket sequence with K outer brackets.

»
2 weeks ago, # |
Rev. 9   Vote: I like it +15 Vote: I do not like it

My $$$(n + q) \ log \ n$$$ solution for 1261B2 - Optimal Subsequences (Hard Version)

Greedy
Binary Indexed Tree(BIT)

Code : 65736937

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I didn't get the sol for 1261B, can anyone explain plz?

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

Why the following statement in Problem F is true? Shouldn't it be $$$4 \times n^2$$$?

We can prove that the number of both "real" and "auxiliary" segments of any size is not greater than 4 x n.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 2   Vote: I like it -10 Vote: I do not like it

    Consider a access to [l,r] on the segment tree, we would call the segments we accessed and found that the segment is completely in [l,r] real segments, and all segments we visited are auxiliary segments. Since we tried visiting n intervals (All intervals in A or B), and for each visit the segments (nodes) we touched of each depth is not greater than 4, the number of both "real" and "auxiliary" segments of any size is not greater than 4 x n is proved.

    This is the same with the proof of the complexity of the segment tree, I found this on internet only 4 nodes are processed in a level.

    Sorry, but I have no idea why it could possibly be $$$4n^2$$$.

    Check out my solution for more information:65749995

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

For anyone looking for the solution of 1261B2 - Optimal Subsequences (Hard Version) in Java, you can refer to my solution. I used the same approach as mentioned in the tutorial and used Segment Tree to find the kth smallest element in the set. 65750497

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Btw no need to binary search on seg tree queries, you can use this trick, (ctrl-f for find_kth)

    • »
      »
      »
      2 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot, exactly what I was looking for. It decreased the time complexity from log(n)^2 to log(n). Thanks a lot.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can Anyone Explain Full Logic Of Box Problem??

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

Thank you so much for the contest and editorials!

I'm just wondering if anyone has a solution which runs under $$$O(n^2)$$$ for Div1A/Div2C (Messy)? Or alternatively, is there a way to show that it is not possible to do this with better time complexity?

Thanks!

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I was wondering the same.

    After spending 5 mins thinking about a solution, I noticed n^2 can also pass but it looked like it can be solved in better complexity too.

  • »
    »
    2 weeks ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    There are several ways to implement a solution that runs under $$$O(n^2)$$$.

    Both operations explained in the editorial can be implemented in $$$O(log(n))$$$ using treap: code

    Also, you can notice that in this problem, reversing a range is only going to change the value of two positions (start and end of the range). So you can implement the reverse operation with a simple segment tree (by updating both ends of the range only). Finding the first position to the right equal to a value can be done in more than one way using the same segment tree. For example:

    • Binary search over prefixes starting in each position in $$$O(log^2(n))$$$: code.
    • Descending over the nodes of the segment tree, achieving $$$O(log(n))$$$: code.

    I didn't explain every detail in case someone wants to think about them. I'm not sure whether a $$$O(n)$$$ solution exists. Feel free to ask anything :)

  • »
    »
    2 weeks ago, # ^ |
    Rev. 4   Vote: I like it +11 Vote: I do not like it

    Actually it can be done in $$$O(n)$$$. Here is my code: 65767515

    The main idea is to create pointers first_opened and first_closed for first ( and ) in s and just update them. The solution is similar to the solution in the editorial. But every time when $$$s[i] \neq t[i]$$$, look at the substring s[i..max(first_opened, first_closed)]. It is either (..() or )..)(. Reverse can be done in $$$O(1)$$$ and after that you have to fix pointers, it is $$$O(n)$$$ total (details in the code).

    Also, I'm pretty sure that there is no $$$o(n)$$$ solution :)

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I saw solutions for B1, B2 using Segment Tree and BIT. How can we find kth smallest element in set using those 2 data structures? I solved it using ordered_set (PBDS in GNU).

Also, is insertion operation also supported with this trick (with the use of BIT/SegTree)?

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can do the hard version of optimal subsequences with online queries using sortings and a mergesort tree. Here is my solution: https://codeforces.com/contest/1262/submission/65675557

  • »
    »
    3 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Also you can compute persistent segment tree for each prefix that will store for each value count of it. And you will just go down in this tree in O(log n) to find min prefix with sum >= k.

»
13 days ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

The issue is solved.

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

Can somebody please explain why we should multiply the answer by k^(n-t) in div1D/div2F i think the n-t other answers have fewer possibilities

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

For Div 2 problem A (Math problem), how can we say that (rmin — lmax) will give us the segment that will connect each and every segment (ie. common point for all the segment)?

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

Could anyone suggest why this solution for Div2 C is wrong ? It makes string of pattern "()()(()())" of this sort. It is different from tutorial (and quite complicated) but since m can be upto n, I don't get what is wrong ?

»
11 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Sorry, but I have tried hard but still can't understand the given solution of 1261E ,I wonder what's the meaning of operations for {4,1} and the later stuff? Looking for your reply (:

  • »
    »
    11 days ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm sorry if the editorial is hard to understand. {4,1} means that we currently iterated through two elements in A, namely 4 and 1. If the next element in A is 1, then there are three numbers we handled, {4,1,1}. Be careful not to mix it up with the "compressed set".

»
11 days ago, # |
  Vote: I like it -10 Vote: I do not like it

У меня есть некое подозрение , того , что задача С которую я написал за N^3 работала , а именно она работает за N^3 ! Но только абстрактно понял почему ! Был бы очень благодарен тому ктом сможет объяснить почему задача С которая описано в разборе работает за N^2 А не за N^3 !

Вот мое решение , кому интересно !

include<bits/stdc++.h>

define ll long long

define sz size

define pb push_back

define pf push_front

define mod 1000000007

using namespace std;

ll T = 1, i, n, m, k, p, cnt, j; string s, t; deque<pair<ll, ll> >v; dequenm; int main() { cin >> T; while(T--) { cin >> n >> k ; cin >> s ; p = 1 — k; for(auto to : s) { if(to == ')')p ++;

}
    t = "";
    for(i = 1; i < k; ++i)
    {
        t += "()";
    }
    for(i = 1; i <= p; ++i)
    {
        t += "(";
    }
    for(i = 1; i <= p; ++i)
    {
        t += ")";
    }
    for(i = 0; i < n; ++i)
    {
        p = 0;
        if(s[i] != t[i])
        for(j = i + 1; j < n; ++j)
        {
            if(s[j] == t[i])
            {

                for(m = i; m <= i + (j - i) / 2 ; ++m)
                {
                    swap(s[m], s[j - p]);
                    p ++;
                }
                v.pb({i + 1, j + 1});
                break;
            }
        }
    }
    ///cout << s << '\n';
    cout << v.sz() << '\n';
    while(v.sz())
    {
        cout << v.front().first << ' ' << v.front().second << '\n';
        v.pop_front();
    }
}

}

  • »
    »
    11 days ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    опечатка второй раз я хотел написать , что она работала за N^2

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

I solved problem E using the concept entropy, you can see it here.

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

Problem : Arson in Berland Forest

How to do "add value on a rectangle" (using prefix sums)" ?

»
20 hours ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

.