300iq's blog

By 300iq, history, 3 weeks ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +83
  • Vote: I do not like it

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

Doesn't the solution for Anagram Paths run in quadratic time on a star? "upd" function iterates over all children of all vertices on the path when processing each query, and there can be O(n) of those.

I spent a lot of time thinking how to handle this situation, couldn't come up with anything better than 26 heaps in each vertex and overall O(n*sqrt(n)*log(n)) running time, and couldn't implement it before the contest ended :(

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

    How does a star graph work in a binary tree?

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

      Oh, here's what I missed :) Thanks!

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

    Isn't it binary tree?

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

I first implemented 1168D - Anagram Paths in $$$O(n \log n)$$$ with segment trees and only then saw that it doesn't say YES/NO correctly. But if the answer is YES, then I can correctly find the value to print (max number of each letter). But I later needed $$$O(n \sqrt n)$$$ anyway to check YES/NO.

So, how to find value of the answer in $$$O(n \log n)$$$? Run DFS to get preorder and postorder of every vertex. Create $$$26$$$ segment trees linearly, one for each letter. If there is a character on an edge, look at segment tree for this letter, and add $$$+1$$$ to segment corresponding to the subtree below the path. For each letter, you need a path to some leaf that has biggest number of occurrences of this letter — this is max in a segment tree.

This solution doesn't actually rely on the fact that there are at most two children. Maybe it's possible to extend it to get YES/NO too?

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

    It is very smart!

    But I don't think that it is possible to extend it, honestly. Problems about dynamic tree DP are solved with some spooky HLD solutions :(

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

    Why doesn't this sol, say YES/No prorpely. I can't think of a reason. Do you have a test case or any intuition?

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

      Other than checking depths to be equal, the answer is NO if there exists a vertex such that the height of its subtree is smaller than the number of fixed characters below — for every letter, we take a path (to a leaf) with max number of occurrences of this letter, and we sum these $$$26$$$ values. The issue with my solution is that I only check the root for this inequality, while I should check all vertices with two children.

      The counter test is: $$$N = 4$$$, edges: $$$(1-2, ?)$$$, $$$(2-3, a)$$$, $$$(2-4, b)$$$. The answer is NO because we need at least one a and at least one b below the vertex $$$2$$$.

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

    Point it out if I am wrong:

    Let sum[v] denote the sum of maximum occurrences in a link for each character in the subtree v.

    After replacing a '?' with a letter, what we need to do is a link addition.

    Fix sum[v] + dep[v] and its minimum(which is required to answer "Shi" or "Fou" queries), which can be done in O(n log^2 n) (HLD) or O(n log n) (LCTs with some extensive information).

    Another issue: how to find the length of the link we're going to update. Fix the 26 segment trees as you've mentioned above and do a binary search on the one that we need. Then, simply climb the tree through HLD or binary encoding.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Can anyone please explain their solution of Problem C (Increasing by modulo) ?

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

    Sure.

    First we notice that the number of overall operations is equal to the maximum number of operations used on a single index.

    Next we notice that, if we can solve the problem in <= X operations, then we can also solve it in <= X + 1 operations. This is a monotonic sequence, so we can solve for the minimum value of X with binary search.

    The question is, how do we check for <= X? Well, notice that it is never worse to have the leftmost index to be lower. However, we can only increase-- until it loops around. Thus we either don't change the value at x, or we set it to zero. (we check if the required number of operations to do this is <= X). Next, we move on to the next index, this time setting the "base" value equal to the previous index's value to ensure our sequence is nondecreasing. If at any point our current index is less than the base and X operations on it are not enough to make up for this, then we need to raise our value on X.

    Now we have O(log m) searches and O(n) checking, so we have an overall O(n log m) solution.

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

      Excuse me what do you mean by "However, we can only increase-- until it loops around. Thus we either don't change the value at x, or we set it to zero. (we check if the required number of operations to do this is <= X)."

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

        lets say the first value int the array is 3, and m is 6.

        after each operation, we get the following values: 3, 4, 5, 0, 1, 2

        If we increase 3 through the operation, we don't want to make it 4 or 5, as this just makes getting a nondecreasing sequence harder, we want it to become less than 3.

        However, to make it 1 or 2 we need to go past zero. Zero is better for nondecreasing sequences, and it is also easier to get to.

        Therefore, our only choices for the first one are zero or the initial value.

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

          Right! I just got it an hour ago after looking at your submission :) thanks again!

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

          thanks for great explanation.. can u give some question related to C i.e. increase by modulo

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

      Your explanation is awesome! Thanks a lot!

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

      "First we notice that the number of overall operations is equal to the maximum number of operations used on a single index."

      How did we get to this conclusion? I am not able to convince myself. Pls help.TIA

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

        As an example, suppose you have an array of length 5. You do 1 increment on the 1st element, 2 increments on the second, 3 on the third, 4 on the fourth and 5 on the fifth. As per the question, an operation is defined as any number of indices to be chosen and incremented. So in our example, the first operation could be incrementing all elements. The second operation would be to increment all elements except the first one, and so on. Now you see, the last operation would always be the increment the index (or indices) with the maximum number of increments required.

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

      how we come to conclusion that in first case we have make a[I] equal to prev if we have enough operation….. but it is okay to leave a[I] as it is as the sequence is still non decreasing... plz tell me the proof of this, as I cant understand it and thanks for great explanation.. sry for bad English.

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

      In the case when prev > a[i] we explore the possibility of increasing a[I] to previous by taking prev — a[i] steps but why don't we consider the other possibility of decreasing all other values before previous to a[I]. I mean we should consider the minimum of the two possibilities as our value for k. Please provide a mathematical explanation.

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

        That should work to in my opinion. But you cannot mix two strategies. You can edit the check function to your strategy and check if its right.

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

          But to decrement the previous values would increase the complexity to quadratic time which would not pass.

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

Are there many other programmers who compete in Rust?

My solution to 1168C seems similar to the editorial, but it times out and I don't know why.

Also, why isn't the i-j-k loop in the official solution n log^2 n?

Edit: locally, my code runs a lot faster if I use -O. What rustc compiler options does Codeforces use?

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

    It's roughly 10^8 operations. Should be fine with C++. I've heard Rust is faster than C++?

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

      I got word from Mike, we use: rustc -O -C link-args=/STACK:268435456 --cfg ONLINE_JUDGE %1

      The inner loop should only run 300,000 * floor(19/2) * ceil(19/2) = 27 million times, so it's still puzzling that my solution is so slow.

      Edit: I figured it out! Unfortunately, it turns out stdout is line-buffered, so it's slow if you print a lot of newlines, such as using println!() or print!("\n").

      Here's a passing submission using writeln!()

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

Is there anyone who has a proof for the lemma of problem D ? Why there are no strings without such x,k of length at least 9 ?

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

what do these lines do?

#ifdef ONPC
  mt19937 rnd(228);
#else
  mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
#endif
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    If running on local machine (ONPC!), use a constant seed for random (228), but when submitting to codeforces for instance, use the time as seed to avoid hacks. This will make debugging your random code easier, because the values produced by rnd(228) are always the same every time you run the code on your machine.

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

      Hey!! Can you please explain how does generating seed help with hacks? Maybe I dont know how hacks work. Can you please tell me about it too?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

I checked your solution of problem D Good Triple. I don't understand why get the largest r. If we fix l, and we find the smallest possible r, and r of value from r to n-1 (inclusive) is ok. I think we should get the smallest r, and I changed your code by add a break if I get a smallest r.

    if (s[i] == s[i + k] && s[i + k] == s[i + 2 * k]) {
                vl[i] = i + 2 * k;
                break;
            }

And the code get AC. Is there any bug of the solution or the system test does not cover all cases?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it
    for (int k = 1; i + 2 * k < vl[i]; k++) {
    

    This part already ensures that you will make vl smaller, so if you will update vl, you will break because of the for condition.

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

      Then the code works to find the smallest $$$r$$$, not the largest.

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

        If we find largest $$$r$$$, then it’s obviously n-1 or bust. So it’s a typo.

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

How to solve 1169B using graphs? Thanks.

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

Hi,

In B Question in the solution of author ==>

a--, b--;

Why the author use this line when his getting pairs?

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

    Because , he want to store them in the range between [0,n-1]. Many programmers are used to this notation .

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

      Yes you're right after that he defines vector(n) but if the line wasn't there he should do vector(n+1).

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

Can someone explain 1169E? I didn't get it from the editorial.

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem 1168E is just same to the problem in the Topcoder! Here is the address: https://community.topcoder.com/stat?c=problem_statement&pm=14159
The problem is in SRM686.

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

why this approach doesn't works for E — AND Reachability, for every bit i merge all numbers have that bit on and to answer the query if two numbers lie in same component then they are reachable otherwise not.

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

    Its not guaranteed that two numbers that are reachable share a bit. (the and checks two numbers for adjacancy, not the whole sequence.)

    For example: 8 12 4

    We can reach the 4 from 8, but they don't share any bit.

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

      what I'm trying to do is for each bit I'll merge every number whose bit is on so for your case 4&12 will get merged when we check 2nd bit then 12&8 will get merged when we check 3rd bit so every number lies in single component

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

    Assume you need to find reachability from index 3 to index 4 and a3&a4 is 0 but a3&a1>0 and a4&a1>0, then your code will return reachable as a1, a3 and a4 share a component but since index 1 is not between 3 and 4 this route shouldn't be used.

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

In problem B How are we going to fix who is x in the first pair?

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

Is there any other way to solve 1169C, instead of the one provided in the editorial. The question was really good BTW!

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

Can anyone please explain their solution of Problem 1169E (And Reachability) ?

»
3 weeks ago, # |
  Vote: I like it +52 Vote: I do not like it

Complexity of Div2 E is $$$n(log(n)^2)$$$ not $$$nlog(n)$$$

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

Hey guys, I understood how 1169B works, but my code keep failing on test case #4. Can anyone find the problem? Here is my code: https://codeforces.com/contest/1169/submission/54742878

Thanks

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

In tutorial for problem C, can somebody explain what does the below condition checks: (lf <= prev && prev <= rf) || (lf <= prev + m && prev + m <= rf)

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

some one pls explain problem B 6 9

  1. 6 2

  2. 4 2

  3. 3 6

  4. 4 6

  5. 2 6

  6. 1 4

  7. 2 6

  8. 4 5

  9. 4 2

****the ans is yes why not NO coz there r 9 pairs if lets say x=2&y=6 there is a pair no 8 where neither is x nor y .if u put any other x nd y u will definitely get one pair where either x is not present or y ??** **so why ans is YES not NO ****

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

please anyone explain problem D proof.

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

    I am not able to prove it any formal way but i can do this in informal way.
    if x=1,k=1, positions are 1,2,3
    so if we want to find upper bound of k it is better not to put triplets of same numbers together.

    0011001100110011

    Now consider x=1,
    k=1->[1,2,3],2->[1,3,5],3->[1,4,7],4->[1,5,9]
    for k=1,2,3 condition does not satisfy but for k=4 this conditions satisfied.so our maximum position will be atmost 9.
      for (int i = n - 1; i >= 0; i--) {
        vl[i] = vl[i + 1];
        for (int k = 1; i + 2 * k <n; k++) {
          if (s[i] == s[i + k] && s[i + k] == s[i + 2 * k]) {
            vl[i] =min(vl[i], i + 2 * k);
          }
        }
        ans += n - vl[i];
    }
    

    Here we iterate from backward find the minimum possible r for this l.

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

      You can use the "pigeonhole principle" to understand this lemma. For a 01 string of length 9, it means at least five zeros or five ones. Assuming there are five ones, then no matter where 0 is, there will be a k satisfying condition.

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

can someone explain me the div2 B solution using graph..? Thanks.

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

Div 2E:AND Reachability is a beautiful problem with a beautiful solution!

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

Explain problem B please

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

Why is Div2B tagged as "Graphs"?

»
3 weeks ago, # |
  Vote: I like it -16 Vote: I do not like it

Can somebody help me my code is below I think I have done little differetn but getting WA at test case 13 please help me ?

include<bits/stdc++.h>

using namespace std;

int main() { string s; cin >> s; long long n = s.length(); long long ans = 0; long long l = 1; vector<pair<long long,long long>> v;

long long r = n;
for (long long i = 0;i < n;i++) {



    for (long long x = 1;i + 2 * x < n;x++) {
       if (s[i] == s[i + x] && s[i] == s[i + (2 * x)]) {
         r = i + (2 * x);

         v.push_back(make_pair(r,i+1));
         break;

       }
    }

}
for (long long i = 0;i < v.size();i++) {
    if (i == 0) {
       ans = ans + (v[i].second) * (n - v[i].first);

    }
    else {
       ans = ans + (v[i].second- v[i-1].second) * (n - v[i].first);
    }

}


cout << ans;

}

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

Huh. So I solved E with machine learning. I thought for some time, didn't prove anything useful except the form of the answer if the input is a permutation as well and $$$p = I$$$, so I just took that as the starting point and did some random swaps until I got the target sequence. It should be slow theoretically and doesn't have to terminate, but it worked pretty damn fast after some speedups.

Specifically, I keep $$$p = I$$$ and only care about the number of occurrences $$$c_i$$$ of each number in the target (input) sequence compared to the number of occurrences in my current sequence $$$p \oplus q$$$. I calculate the loss function $$$L = \sum |c_i - c^*_i|$$$ and perform only swaps in $$$q$$$ that don't increase $$$L$$$. I go through the whole permutation $$$q$$$ multiple times in random order, ignore some elements that probably won't decrease the loss when swapped and try all swaps otherwise. Swaps that strictly decrease $$$L$$$ are made immediately. If there are currently no such swaps and $$$L > 0$$$, I also make swaps that keep $$$L$$$ constant.

It's really just hill climbing — small incremental improvements to minimise loss, with some "epochs" that start by shuffling and a bit of extra swapping after each epoch to increase entropy.

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

I made Youtube videos about two problems from this contest, both with an explanation how I got to a solution, and then code walk-through. It might help some people.

  1. 1169B - Pairshttps://www.youtube.com/watch?v=IW2xZVsD6w4
  2. 1168C - And Reachabilityhttps://www.youtube.com/watch?v=MB_n50WNQrw
»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I have seen many solutions of problem c but no one is thinking of this statement (ai+1)mod m,I mean they are just comparing adjacent elements and despite of modifying by the given way they are just assigning the min value

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

Link to solution of this contest https://www.youtube.com/watch?v=APi5XhkflZM

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

lf <= prev + m

Line #32 in Solution to 1169C is not really required.

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

can anyone explain the solution of problem 3?