Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

majk's blog

Codeforces Global Round 4 Editorial
By majk, history, 5 years 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

Comments Comments (133)
| Write comment?
»
5 years ago, # |
  Vote: I like it +67 Vote: I do not like it

the fastest editorial in the west

→ Reply
»
5 years ago, # |
  Vote: I like it +404 Vote: I do not like it

→ Reply
»
5 years 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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    Though I am interested in seeing some mathematical proof, I brute-forced in the interval [3, 1000] and it indeed holds true in that interval. And since 3 <= n <= 1000, we are set to get AC.

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

    You can read about Prime Gap

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +30 Vote: I do not like it

    Look at some of the results here:

    https://en.wikipedia.org/wiki/Bertrand%27s_postulate#Better_results

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

    I tested it by running through all n <= 1000 in ~ 500 squared operations, took me 2 min to implement because you needed a sieve anyway

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -11 Vote: I do not like it

    I just queried Wolfram Alpha for all primes less than 1000.

    → Reply
  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    The degree of every node can be either 2 or 3.

    So suppose we have X number of 2-degree nodes and Y number of 3-degree nodes, so $$$ X +Y = n$$$, and $$$2X + 3Y = 2e$$$ Why ?

    Solving these equation we will get $$$X = 3n - 2e$$$ and $$$Y = 2(e - n)$$$, and also $$$X >= 0$$$ and $$$Y >= 0$$$, upon solving this you will get $$$e >= n && e <= 3n/2$$$

    → Reply
»
5 years 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

→ Reply
»
5 years 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."

→ Reply
»
5 years 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://mirror.codeforces.com/contest/1178/submission/57407689

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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 :(

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

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

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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] ?

→ Reply
  • »
    »
    5 years 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.

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

    The density of prime numbers around n is approximately 1/ln(n) which means 1 out of every ln(n) numbers is prime, so between n and n+ln(n) roughly there must be a prime hence between n and 3n/2 also for large n, there will be a prime

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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

      → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
        • »
          »
          »
          »
          »
          5 years 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

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years 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.

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

              You had polish contest today or something?

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                5 years 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?

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

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

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

    Or, you know, calculate which one u need.

    → Reply
    • »
      »
      »
      5 years 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.

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

    using long long instead of int is for the weak

    → Reply
»
5 years 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})$$$.

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

    Modified kinetic tournament? What are these mysterious words xd?

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

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

    → Reply
    • »
      »
      »
      5 years 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.

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

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

    Can you share your proof?

    → Reply
    • »
      »
      »
      5 years 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})$$$.

      → Reply
»
5 years 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??)

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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...

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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
→ Reply
  • »
    »
    5 years 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).

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
  • »
    »
    5 years 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...

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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...

        → Reply
      • »
        »
        »
        »
        5 years 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

        → Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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

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

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

    → Reply
  • »
    »
    5 years 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)$.

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

      Now I got it, thank you so much)

      → Reply
    • »
      »
      »
      5 years 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 .

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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 :)

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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. :|

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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

    → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.).

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
  • »
    »
    5 years 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;.

    → Reply
»
5 years 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

→ Reply
  • »
    »
    5 years 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 :(

    → Reply
»
5 years 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.

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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.

      → Reply
      • »
        »
        »
        »
        5 years 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.

        → Reply
»
5 years 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

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

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

      Hi, Could please explain the solution of Bonus problem, present in E's editorial.

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

        Cases of length of 4k,4k+1,4k+2 are trivial, and we try to transform the case of 4k+3 into them if possible. You will find that the only cases that can’t be converted easily are like abab...ab abc bc...bcbc where the number of left ‘ab’s is equal to that of right ‘bc’s. It’s easy to prove there is no solution for these cases.

        → Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
    • »
      »
      »
      5 years 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.

      → Reply
    • »
      »
      »
      5 years 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.

      → Reply
»
5 years 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.

→ Reply
»
5 years 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...

→ Reply
  • »
    »
    5 years 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.

    → Reply
»
5 years 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 ??

→ Reply
»
5 years 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.

→ Reply
  • »
    »
    5 years 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!

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

      Didn't realize this until now. Big thanks!!!

      → Reply
»
5 years 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

→ Reply
»
5 years 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?

→ Reply
»
5 years 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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years 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://mirror.codeforces.com/contest/1178/submission/57488328

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

→ Reply
»
5 years 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?

→ Reply
  • »
    »
    5 years 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

    → Reply
  • »
    »
    5 years 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.

    → Reply
    • »
      »
      »
      5 years 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?

      → Reply
      • »
        »
        »
        »
        5 years 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)

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For question d i thought like the soln and also found the goldman conjecture conjectures: 1.Every integer greater than 5 can be written as the sum of three primes. 2.Every even number greater than 2 can be written as the sum of two primes. now i am unable to solve the problems using the these conjectures could anybody guide me

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

    betrand postulate there exits a prime p n < p < 2*n -2

    mindeg >=2 => E >= n

    The problem is to represent 2E as sum of n primes. For that find E first. let E be nearest prime num to n Bertrands theorem guarentee E<2n-2

    any even number by goldman conjecture can be expressed as 2 num E-2(k-2) is even and can be express as u and v

    since E<2n-2 u<n && v<n

    deg seq of graph is u v 2 2 .. (k-2) times

    → Reply
»
22 months ago, # |
  Vote: I like it -6 Vote: I do not like it

C is easy peasy lemon squeezzyy.

→ Reply