majk's blog

By majk, history, 5 weeks ago, In English,
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
Tutorial is loading...
Code
 
 
 
 
  • Vote: I like it
  • +151
  • Vote: I do not like it

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

the fastest editorial in the west

»
5 weeks ago, # |
  Vote: I like it -86 Vote: I do not like it

I am ready to downvote who comment "Fast editorial!! wow!!!" Thanks for the great contest btw

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

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

Fortunately for us, for each n≥3 there is a prime number in interval [n,3n/2], simply the smallest of them will do. Ok I need a demonstration for this one

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

Shouldn't there be a proof or at least a link to an article for 1178D, about finding a prime number between n and 3n/2? Cause a lot of the constructive algorithms used in it rely on this fact

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

"To optimise it to O(n^3) just note that the selection of a and b is independent."

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

Hi, can someone tell me how is my code for E (very brute, I printed palindrome with 2 characters) getting AC?

Is there any proof or countertest?

https://codeforces.com/contest/1178/submission/57407689

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

    Oof it's been hacked. apparently it altered my placement. good to know ig

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

Why my solution is giving wrong answer in problem B? link

I am using simple permutation and combination.

EDIT. this one got accepted. I guess macros doesn't work the way I thought they work :(

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

    Take long long int instead of int. (to stop overflow)

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

      I am still getting wrong ans after using long long. I have a macro #define int lli

      link

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

        Take your variable 'a' as long long. It is the one that is overflowing

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

    Your macro #define int long long is lower than type typedef vi vector<int>. That's why your values in your vi arr remain int

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

For Problem G, is a lazy segment tree possible instead of sqrt decomp? Is sqrt just to make implementation easier?

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

    Since you need to rebuild some part of the convex hull trick, using any type of segment tree just doesn't help it. Sqrt decomposition is used to balance out between the rebuilding complexity.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

In problem D, how can we say that there is always a prime in the interval [n,3n/2] ?

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

    Just list all primes less than 1000 by writing a simple program or querying Wolfram Alpha.

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

Learnt a very important lesson from Problem B.

Always use long long int if you're not 100% sure that int will not overflow.

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

    I have now made a habit to use long long int instead of int. It really was frustrating back then.

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

      well, once you will notice replacing back to ints gives you AC instead of TL and your life won't be the same

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

        Once you will notice replacing ints to long longs will give you AC instead of WA and your life won't be the same

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

          Once you'll be able to read whole discussion and not only last message of it. Not sure it'll change your life

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

            Where did you get the information that I read the only last message xD? Of course I read "whole discussion" consisting of your message and a few above. I will say more, my post fits much better to the discussion taking preceding posts into account.

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

              You had polish contest today or something?

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

                What were you trying to say through your last two posts other than just throwing wannabe cool random insults unrelated to the actual topic?

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

      Let's downvote Swistakk to make his contribution out of top 15.

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

    Or, you know, calculate which one u need.

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

      Thinking a little bit, it becomes understandable that in the worst case scenario each product may produce 10^(10).

      So, the decision to choose long long should have been clear to me if I paid enough attention.

      Thanks.

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

    using long long instead of int is for the weak

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

I was able to solve G with a modified kinetic tournament: 57423487 (AC in 530ms)

Can anyone bound the time complexity?

Edit: I think I have a proof that it is $$$O((n+q\log{n})\log^2{n})$$$.

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

    Modified kinetic tournament? What are these mysterious words xd?

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

    Could u please give some good tutorial links for the data structure.

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

      I don't know of a good tutorial for this data structure. I learned about the kinetic tournament itself from Wikipedia and realized the priority queue can be embedded into the segment tree by having each subtree store the time until its first certificate failure. This problem also required lazy propagation of time advancement updates.

      I would recommend reading jiry_2's tutorial on "segment tree beats" as it uses many of the same ideas. Once you understand the ideas behind it you may be able to understand the code.

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

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

    Can you share your proof?

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

      The data structure is basically an amortized segment tree that supports the following operations on two arrays $$$a_i$$$, and $$$b_i$$$:

      • For $$$l\le i \le r$$$, set $$$a_i$$$ to $$$a_i+b_ix$$$, where $$$x>0$$$ ($$$x$$$ may be different between updates).
      • Find $$$\max_{l\le i \le r} a_i$$$.

      Queries are obviously $$$O(\log{n})$$$. Updates are trickier.

      First, suppose all updates are over the entire range. For each leaf, consider the set of segment tree nodes where it is maximum in. The size of this set can increase and decrease, but once it decreases it will never increase again.

      More formally, let's call a leaf shrinking if it will never become greater than the sibling of the topmost node in the segment tree it is maximum in (i.e. $$$a_{node}\le a_{sibling}$$$ and $$$b_{node}\le b_{sibling}$$$), and growing otherwise. Once a leaf becomes shrinking, it will stay shrinking forever. If a leaf is shrinking, the set of nodes it is maximum in will never increase again.

      Define the potential for a growing leaf to be the depth of the topmost node it is maximum in. The total potential is the sum of potentials of all growing leaves. Each unit of potential will pay for $$$O(\log{n})$$$ units of time. The initial potential is $$$O(n\log{n})$$$.

      An update will basically locate each node whose maximum leaf changes and fix it in $$$O(\log{n})$$$ each. This is paid for by the potential decrease of the growing leaf involved. Some leaves will change from growing to shrinking, but this only decreases the potential.

      Now consider updates that do not cover the entire range. For most nodes, everything above remains true. The exception is the $$$O(\log{n})$$$ nodes whose parent are partially covered by the range. The leaves maximum in these nodes may change from shrinking back to growing, which could increase the potential by $$$O(\log^2{n})$$$.

      Thus, the total time complexity is $$$O((n+q\log{n})\log^2{n})$$$.

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

Why are all the editorial solutions playing code golf? I can understand doing it in a contest, but for a solution that you intend people to read and try to understand? The variable names are all just one letter and there are no comments or anything anywhere. Please never do this again. (I realize that this happens in other editorials too, which makes it even worse — how is THIS the standard??)

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

    Same goes for explanations, actually. Sometimes all they say is How to solve the problem, not why it works (see current D for example). The code itself starts with double tabs for some reason. If they put so much effort in problems and testing, the code should be better than the ones posted. Accepted or not, there is a difference between right answer and solution.

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

    It's actually kinda funny though; I think this is a perennial problem for anyone with backgrounds in both mathematics and computer science. Programmers may wish that mathematicians stop using single-letter variables and funny symbols, but when you're up to your neck twisting numbers in algebraic and calculus knots, treating them as means to an end rather than an end to themselves... sometimes there is just no concise way to describe the intermediate variables. Just imagine if π was "circumferenceToDiameterRatio" everywhere, even in seemingly far-removed contexts like the "infinite lighthouse-lake" problem: https://www.youtube.com/watch?v=d-o3eB9sfls

    Though I do agree that more step-by-step explanations as well as some comments would be nice.

    Additional sources of great "fun": confusion between 0-indexing, 1-indexing, and sometimes even Python-indexing...

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

    I get whatchu mean. In CEOI testing, I was surprised that I'm the one with readable codes.

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

majk For 1178E another Exercise could be as follows:

If There are many letters like complete set of alphabet (Not just 'a' ,'b', 'c'). Also If consecutive elements can be same.

In above case, "IMPOSSIBLE" can be one of the answers.

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

    Can you prove that works? It looks like it doesn't (but I may have misunderstood something).

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

      Have a look at this

      This is solution for 1178E. Instead of having 3 deque (for 'a','b','c') we can have a deque for each alphabet.

      Now we can take a deque whose back()-front() is maximum. maintaining order of deque would be very easy as we have to sort an array (array size would be number of disitnct letters so may be 26 for if we have all lower case letters.).

      In above solution I have checked which among the those deque (out of a,b,c) has maximum difference (back()-front()). so instaed of three we need to check for all the distinct alphabets.

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

    I think you are trying to apply greedy solution. It clearly doesn't work... This was solvable due to such constraints...

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

      The proof of correctness goes this way.

      Let's say we have 2 pointers. l pointing to index 0 and r pointing to index n-1.

      By comparing the difference, the approach is to converge these pointers and bring them close to each other at the slowest pace.

      let's say currently l points to index i1 and r points to index i2.

      let there been any index j1,j2 such that j1r then those would have already been covered (as we are moving at slowest pace).

      another case could be we have more than one choice of moving pointers and include letters in palindrome. here, we can take any one and move ahead (since our focus is to decide for current position if they can be included in formation of palindromic string.

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

        What's your answer for s = "AbccbAWpqrstW"?
        Important characters I have written in uppercase...

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

        That's no proof of correctness. It works for the "no adjacent pairs is equal" due to luck, if you understand the proof that there's always a solution you'll understand why.

        amnocabplpb — your algorithm finds "ama" even though "bplpb" is the best answer

        amncabplpb — depending on ties, your algorithm finds "ama" or "bplpb" (it'd find "ama" if you tie like in your submission), in this case "bplpb" is the only answer

        amncbpalpb — your algorithm finds "ama" even though "bpapb" or "bplpb" are the only answers. (5 spaces for a and 4 spaces for b)

        I could create some more cases but I think this is enough

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

Can anyone please explain what S[2 : -2] means in problem editorial E?

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

    S[2:-2] is S except for the first 2 and last 2 elements.

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

    I'm using the Python notation for subscripts. It means starting from the $$$2$$$nd character ($$$0$$$-indexed) until the $$$2$$$ character from the end ($$$-2$$$) exclusive. So the string $$$S$$$ without the first and last two characters.

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

Explain please: Problem F1: To optimize it to O(n^3) just note that the selection of a and b is independent

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

    ax + ay + bx + by == (a + b)(x + y)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +22 Vote: I do not like it
    $$$DP[l][r] \\= \sum_a \sum_b DP[l][a-1] * DP[a][I[c]-1] * DP[I[c]+1][b] * DP[b+1][r] \\ = \left( \sum_a DP[l][a-1] * DP[a][I[c]-1] \right) \cdot \left( \sum_b DP[I[c]+1][b] * DP[b+1][r] \right)$$$

    So you can just calculate

    $$$\sum_a DP[l][a-1] * DP[a][I[c]-1$$$

    and

    $$$\sum_b DP[I[c]+1][b] * DP[b+1][r]$$$

    each in $\mathcal O(n)$.

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

      Now I got it, thank you so much)

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

      It may seem silly but can you please tell me how the complexity of ∑aDP[l][a−1]∗DP[a][I[c]−1 is O(n) . I am really not able to prove/logically explain it .

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

        For selected l and r you need 1 for loop to calculate all a's.

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

Can G be solved using lazy propagation on segment tree? I was thinking, if we transform given tree in an array, then the problem is finding the maximum answer in some interval.

That sounds like it can be done with segment tree in which for each vertex we store a pair of values, (sum of (values of array A) of parents of the best vertex in that interval) and (sum of (values of array B) of its parents). Update for some vertex is just updating the interval by some value. When we are searching for maximum, we take in consideration only absolute values. If its not correct, please, I would like to know where it fails, or if I misunderstood something. Hope brackets help. Thanks in advance.

P.S. sorry if my english is bad :)

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

    The problem is, we have to increment each element on the interval by a multiple of the sum of b_i across all ancestors, not a single value across all elements, so lazy propagation doesn't work.

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

Fortunately for us, for each n≥3 there is a prime number in interval [n,3n2], simply the smallest of them will do.

This was the only link I found after the contest ended. Salute to the authors for assuming this was trivial. :|

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

In question E could someone explains to me why the answer would never be Impossible?

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

    Because you can cut pieces of size 2 from both ends of the string and always get two characters for palindrome from there. That is already almost half the string size. You can add any character from remaining string of length 3 or less in the end.

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

I need help understanding the DP in B. What is the intuition behind it? What do the a, b and c in the code mean?

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

    Maybe it is easy to learn.

    /*

    if(s[i-1]=='v'&&s[i]=='v')num_vv++;

    if(s[i]=='o')num_vvo+=num_vv;

    if(s[i]=='v'&&s[i-1]=='v')num_vvovv+=num_vvo;

    */

    The num_vv is 'a' . The num_vvo is 'b' . The num_vvovv is 'c'.

    For each 'o', the number of 'vv' before * the number of 'vv' after is the number of 'vvovv' that can be formed by using this'O'.

    For example,the answer to "vvoovv" is 2,because there are four wows: vvo.vv and vv.ovv

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

For C, may someone please explain how 2^(w+h) was derived? Thanks.

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

    Work for 1-D array then add another 1-d layer to it u will see

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

      Ok, so it seems that the first row and column decide the rest of the entire grid. And for each of those cells there are 2 possibilities, except for the leftmost and rightmost one. That cell has 4 possibilities. How is this taken care of though?

      EDIT: nvm literally just figured it out. When w + h, that cell is added twice, so 2*2 = 4.

»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

Can anybody help me out with this wrong solution (probably integer overflow). Please explain when to use a certain data type according to constraints, what could go wrong if I use long long int everywhere, Thanks.

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

    Yes. The problem in your code is indeed that of overflow in the power function. Convert all of the ints to long long ints in the function and it will work.

    Actually there is no harm if you use long long int everywhere but I once heard that memory limit exceeded can be encountered in some case. (btw I have never encountered it personally due to the use of long long int).

    You use int when you are certain that none of your value stored in your variables exceeds 10^9 (approx.).

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

      You can also get TLE with long long when used with slow Data structure like GNU-PBDS Ordered set, it happened with me in one of the CodeChef long rounds. But for most cases, using long long is good idea.

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

    Yes. When you multiply two ints, integer overflow happends.

    Use (or convert int to) long long int when multiplying. For example, x = ((long long int)x*x) % p;.

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

An one-line solution of C using python:

print(pow(2,sum(map(int,input().split())),998244353))

57432100

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

    A nice one-line solution of E:

    print(input())
    

    Unfortunately, doesn't work after the checker update :(

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

i don't understand problem C, the solution proposed by majk isn't clear for me, somebody has another solution, please explain me

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

Can anybody please share his code for the problem f1,as i was not able to grasp the code shared in editorial. It would be good for me if someone would share the code in which segment trees are used for min query and a memoization approach rather than iterative dp as i have used them in my code and would be easier to see where i am wrong.... But every help is welcome.. Thanks in advance.

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

Those Bonuses are really interesting!

Could you give some details of Bonus of F2? Does the faster alogorithm reduce O(n^3) part to sth smaller such as O(n^2logn) ? It's so hard.

BTW, time limit of F2 is so loose that My O(n^4+m) and O(n^3logn+m) can pass it. The runnning time are 5366ms and 3400ms. My O(n^3+m) runs 717ms, and most ACs pass within 1s. I guess those runs more than 3s are all of bad complexity, maybe 3s is a better time limit.

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

can some one tell me how to use c++14 in atom ide?

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

Why memory limit exceeded in my solution to problem B? Code

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

    Pay attention to this line: for(int i=str.size()-2;i>=0;i--)

    When str.size()=1, str.size()-2 does not equal to -1 as str.size() is a variable of type unsigned int

    On my ubuntu 19.04 x64 with g++ 8.3, that equal to 18446744073709551614.

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

      Thanks for the reply. But why does this code work then? The array declared now is of type int instead of long long.

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

        This can explain everything:

        #include <bits/stdc++.h>
        using namespace std;
        
        int main(){
        	string s = "s";
        	int x = s.size()-2;
        	cout << x << endl;
        	long long y = s.size()-2;
        	cout << y << endl;
        	return 0;
        }
        

        Notice: Use cf's 'custom test' to run this, please.

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

When solving problem G, I noticed that only changing my block size sometimes changes AC to WA. I am wondering, where is the error in my implementation? Is it likely to be in my SQRT decomposition or in my convex hull code?

AC submission: 57441583

WA submission: 57441814

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

1178E-Archaeology

In the editorial :

"Bonus: Find a subpalindrome of length at least ceil(|s|/2)."

s=abababcbcbc
|s|=11
bbbbb is a subpalindrome of maximum length and |bbbbb|=5.

In this case there is no pallindrome of length 6.

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

    Yes, for the bonus there are some cases in which no solution exists.

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

majk Thanks for the tasks!

There's a problem in task G, though. Your main solution uses doubles in some point to compute the convex hull. However, the point coordinates are as large as 1e18, and double has only 52 bits of precision (so something like 15-16 significant digits). Therefore, it's possible to craft a test against it: gen. it took way too much of my life

(When using doubles, your main solution decides that some three input points are collinear when they're not; then it removes a point that actually is the only optimal point for some query.)

I have some intuition that long doubles might be just enough for this task (by a few of bits of precision), but doubles are hackable. :<

Yeah, floating-point computations hurt.

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

    It would be great to have the Polish mafia for testers!

    I also have a solution with big integers marked as the master solution. In editorial I used the double solution for brevity.

    I didn't find such case and somehow convinced myself that doubles are sufficient (my notes are long gone as this task was prepared a year ago). So, congrats on finding the hacking case.

    It seems to have hacked only our Java solution, while the C++ one still stands. I'll see what I can do about it when I get back to a computer.

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

      return a/b >= c/d;

      Comparing without eps sounds dangerous af.

      Is it even guaranteed that e.g. $$$3/7 = 9/21$$$ on doubles or long doubles?

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

      Oh damn, these 32-bit cf judges. It seems that 32-bit C++ executable decides to use x87 instruction set to do the floating-point computations, which apparently has larger precision than double. The solution in editorial fails only when compiled in 64-bit mode. :/

      It then makes sense that Java solution fails as Java VM doesn't know anything about 80-bit floating-point numbers, and simply won't be able do any operations with higher-than-double precision.

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

      My solutions fails on the 3 test if I use 57508921 a/c >= b/d like in the editorial and gets AC, if I use a * d — b * c >= 0. 57510232

      The problem is in floating point calculation?.

      P.S. this computation I made in long doubles.

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

What does s[2 : -2] in the problem E actually mean? Edit : i found the explanation, doesn't matter anymore.

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

Another possible way to solve problem F is to note that there is one-to-one correspondence between such coloring and rooted tree obtained in such a way that for each color $$$v$$$ its ancestor is the color $$$p_v$$$ which was there before color $$$v$$$ was applied. And thus DP may be to calculate number of rooted trees which may be built on some particular segment. This one seems quite standard...

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

    I was trying to work out this idea myself, but I'm having trouble with figuring out where the current segment starts and ends. Basically, I start with the finished segment that is inputted. Starting from the highest color id, change its color to either the color of its left or right neighbor (this simulates the reverse of one painting step). Then, continue solving with that modified state (until we return to the blank segment), but the problem is I don't have a fast way of finding the current left bound and right bound of the highest color id segment. I think that this should work though by memoizing the states.

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

in problem E 1st test case why cabac is not a valid solution ??

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

I have a faster solution which works in $$$O($$$$$$N^2$$$ * $$$log_2$$$$$$(N))$$$ for F2.

Lets count the number of way to create 2 arrays $$$a_i$$$ and $$$b_i$$$ (the segment that we are going to paint the $$$i$$$-th color) in reversed order (From $$$N$$$ to $$$1$$$). Denote that $$$L_i = p$$$ be the leftmost position that $$$c_p = i$$$, same thing with $$$R_i$$$ for the rightmost position.

Say we are solving for the $$$i$$$-th color. We can easily write out some condition for this color as below:

  1. We should not paint more than enough. This means that we should only paint the $$$i$$$-th color for the segment from $$$L_i$$$ to $$$R_i$$$, and some positions to its left and right if these positions have already been painted.

  2. If our current $$$a_i$$$ and $$$b_i$$$ for the $$$i$$$-th color conflicts with some $$$a_j$$$ and $$$b_j$$$ $$$(j > i)$$$ that has already been painted. $$$[a_i, b_i]$$$ should strictly cover $$$[a_j, b_j]$$$. And once the $$$i$$$-th color covers the $$$j$$$-th color in our progress, we should also replace $$$j$$$-th color with $$$i$$$-th one by changing $$$[a_i, b_i]$$$.

With these two properties, our problem changes to choosing how many $$$j$$$-th color to cover from the left and from the right instead of choosing some specific $$$[a_i, b_i]$$$.

Let's denote $$$dp(i, j)$$$ as the number of way to paint our array until we reach the color $$$i$$$ and the consecutive segment of painted positions around $$$i$$$ formed with $$$j$$$ different colors.

To be easier to see, let's try solving with F1 first.

If we are solving for the $$$i$$$-th color, we should look to its left and right, let's say that these positions have already been painted and have the represented color (the smallest color in that consecutive segment) $$$left$$$ and $$$right$$$.

Now, if the $$$i$$$-th color is going to cover $$$x$$$ out of $$$X$$$ colors from its left and $$$y$$$ out of $$$Y$$$ colors from its right. We will have the transition formula below:

$$$dp(i, X + Y - x - y + 1)$$$ $$$=$$$ $$$dp(left, X)$$$ $$$*$$$ $$$dp(right, Y)$$$.

Luckily, the $$$i$$$-th color will cover only a suffix or a prefix of $$$dp(left)$$$ and $$$dp(right)$$$, thats why we can calculate the suffix sum of $$$dp(left)$$$ and $$$dp(right)$$$. The idea behind this is that if we want to keep $$$k$$$ colors from $$$dp(left, X)$$$, we can simply use $$$i$$$ to cover $$$X-k$$$ colors from its suffix.

Now our problem becomes

$$$dp(i, x + y + 1) = dp(left, x) * dp(right, y)$$$.

Which one can easily see the FFT/NTT application here. In total, this solution will run the FFT/NTT for $$$N$$$ times and the time complexity is $$$O($$$$$$N^2$$$ * $$$log_2$$$$$$(N))$$$.

The same can also apply for F2. But its a little bit more tricky if theres some painted color between $$$L_i$$$ and $$$R_i$$$. This part can be easily solved, but too hard for me to implement during the contest lol.

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

    Good solution! It seems that the $$$O(n^2)$$$ solution has also emerged if just replace the FFT/NTT by brute force since the contribution of every pair would be counted only once in all multiplication!

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

cann't visualize the tutorial of Problem F1. Can anyone please describe the solution of this problem more clearly?

Thanks In Advance

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

Can someone explain the states in problem F1-Short Colourful Strip? And how the recursive relation is being derived?

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

In problem C editorial code, I saw constexpr for the first time, and what I understood from GeeksforGeeks that it's something for performance improvement of programs by doing computations at compile time rather than run time. So why submitting the code[submission:57476357] that using constexpr is slower than the code 57476357 that doesn't use it!

I expected the opposite

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

In the editorial of E, what's the meaning of s[2: −2]? Why can the index be negative?

Edit : I found the explanation, doesn't matter anymore.

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

How to solve E if there may exist all the alphabet?

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

For those who may need help understanding the editorial and code for F1 and F2, I've plagiarized the editorial solutions, translated them to Kotlin, and added my own annotations:

https://codeforces.com/contest/1178/submission/57488328

https://codeforces.com/contest/1178/submission/57489552

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

In problem F1, what does lowest ID of a colour used in the final strip mean?

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

    As stated in the problem description, the strip is colored with each color from 1 to n successively. Thus the minimum color for each segment is significant, as that index will be colored first before the others, and, crucially, that index can never be recolored again

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

    Consider a simple example:

    4 4
    4 1 2 3
    

    For len = 0 and len = 1, the answer is trivial, there is only one way such "subsegments" can be colored. Now we consider each subsegment of length 2:

    4 1
    1 2
    2 3
    

    It turns out that those answers are rather easy to compute, as there are only two ways any subsegment of length 2 can be colored: either a a -> b a -> b c, or a a -> b b -> b c (given a<b<c). Same goes for the mirrored case. Note that these breaks down to two choices for one of the "cursors", and one for the other "cursor", and that we are always querying for D[x][l=0] or D[x][l=1] which have all been set to 1 initially. So D[a=any][l=2] = 2 * 1 = 1 * 2 = 2. But we store those results for later.

    Now comes the interesting bit. For subsegment D[a=0][l=3]: 4 1 2 we consider the minimum color, which is 1. We could choose 2 positions for the left "cursor", 1 1 x or 0 1 x, Either way, we have only one way to color the remaining segment, so, left = 1 + 1 = 2. Ditto right is also 2, and since the choice of the left cursor and the right cursor are independent, we multiply them for the result: D[a=0][l=3] = 2 * 2 = 4

    For subsegment D[a=1][l=3]: 1 2 3, again, the minimum color is 1, There is only one choice for the left cursor, left = 1. There are three choices for the right: 1 0 0, 1 1 0, and 1 1 1. However once we choose one of them, we essentially split the right subsegment into two subsegments that we have earlier solved, as you can't color over a border of two different colors, i.e. 1 1 0 can't become 1 2 2, as stated in the problem description.

    So:

    right = Sum of:
    1 0 0 -> D[a=2][l=0] * D[a=2][l=2] = 1 * 2 = 2
    1 1 0 -> D[a=2][l=1] * D[a=3][l=1] = 1 * 1 = 1
    1 1 1 -> D[a=2][l=2] * D[a=4][l=0] = 2 * 1 = 2
    

    which is 5. Therefore D[a=1][l=3] = left * right = 1 * 5 = 5

    Now we consider the original problem:

    D[a=0][l=4]
    4 1 2 3
    

    If you follow the steps laid out previously, left = 2 and right = 5, so the final result will be 2*5 = 10.

    After all that work though I realized that we never used any of the results D[a=x][l=3] in the final result, so there is probably some room for optimization here. But we can similarly see that for the problem:

    4 4
    1 2 3 4
    

    When we get to the final iteration (D[a=0][l=4]), left = 1, but

    right = sum of:
    D[a=1][l=0] * D[a=1][l=3] = 1 * 5 = 5
    D[a=1][l=1] * D[a=2][l=2] = 1 * 2 = 2
    D[a=1][l=2] * D[a=3][l=1] = 2 * 1 = 2
    D[a=1][l=3] * D[a=4][l=0] = 5 * 1 = 5
    

    so the answer is 14 in this case.

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

      For the example you gave, 4 1 2, shouldn't the four possible paintings be: 1 1 1, 1 1 0, 0 1 1, and 0 1 0? In your description, 1 1 0, and 0 1 0 are achieved from picking the left boundary, and 0 1 1 and 0 1 0 are from the right boundary. But this over counts 0 1 0. Am I missing something here?

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

        Actually it's 1 1 x and 0 1 x for the left boundary, and x 1 1 and x 1 0 for the right. As the choices are independent, we basically don't care where the other boundary is when considering the left and right factors separately. The math checks out, cause we then multiply the factors for the subresult, as that's what you do for independent choices in combinatorics (e.g. 5 dishes and 4 drinks = 20 meal choices, assuming one of each)

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

In problem D how i↔i+n2 this work ? Can anyone explain ?