awoo's blog

By awoo, history, 4 months ago, translation, In English

1644A - Doors and Keys

Idea: BledDest

Tutorial
Solution (awoo)

1644B - Anti-Fibonacci Permutation

Idea: BledDest

Tutorial
Solution (Neon)

1644C - Increase Subarray Sums

Idea: BledDest

Tutorial
Solution (awoo)

1644D - Cross Coloring

Idea: BledDest

Tutorial
Solution 1 (awoo)
Solution 2 (awoo)

1644E - Expand the Path

Idea: BledDest

Tutorial
Solution (awoo)

1644F - Basis

Idea: BledDest

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

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Approach of D problem was great

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

In problem D why we process the queries backward?

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

    When you process backwards, the query is equivalent to "color all squares in this row and column which are not yet colored". This way, each square will be colored at most once. So now your answer will be $$$k$$$ raised to some power(which is actually the number of queries where at least one square was colored).

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

      Got it thanku

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

      I processed all the queries forwards but ended up getting WA, but I am unable to understand how is there a difference between processing it forwards or backwards? Even if we are doing it forwards then, yes it might be possible that some square is getting colored more than once but in the end I am counting the different number of colors for all the squares so that shouldn't make a difference.

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

        For each query you want to determine something that happens in the future — in the later queries. So to tell something about query $$$i$$$, you have to first process queries $$$i+1$$$..$$$q$$$. That is exactly the same as going backwards over queries: you first determine the status of the query, then add the information about it to some data structure.

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

        Failing testcase for your approach: Ticket 587

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

looks legit

upd. already fixed

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

Can anyone help why is this giving me TLE for D 147473308 ?

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

    You have initialized arrays visr and visc of size n and m respectively. Hence your time complexity is O(t*(n+m)) or larger, which in the worst case will be 2*1e9 since there is no limit on sum of m,n over all test cases.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I appreciate all the work that all problem setters and editorialists put in creating problems and writing editorials, but I want to know why there's a delay of almost a day between contest ending and editorials getting out? The excitement and the curiosity fade away (at least for me) due to such a long delay...

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

    That holds true only for certain contests, for some contests the editorial is out as soon as the round ends bro.

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

Can anyone please explain problem E?

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

    The editorial explains it in quite detail. Try to trace out on paper/whiteboard where you're unclear (I did and it helped me a lot!). If you still have doubts, I can help you resolve them.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If you are/were getting a WA/RE verdict on any of the problems from this contest, you can get a small counter example for your submission on cfstress.com

Problems added: "A, B, C, D, E, F".

If you are not able to find a counter example even after changing the parameters, reply to this thread, mentioning the contest_id, problem_index and submission_id.

»
4 months ago, # |
  Vote: I like it +9 Vote: I do not like it

No need for FFT in problem since we need only sum of those Stirling's number and this can be done in O(i): Since S(i,j) = sum(1<=t<=j) C(j,t) * t^i * (-1)^(j+t) / j! we have:
S(i,1)+S(i,2)+..+S(i,k) = sum(1<=j<=k,1<=t<=j)( t^i * (-1)^(j-t)/((j-t)! * t!) ).
Let d = j-t, then ans = sum(1<=t<=k,0<=d<=k-t)( (t^i/t!)*((-1)^d / d!) ) iterate over t and sum(0<=d<=k-t) ((-1)^d / d!) can be precomputed

  • »
    »
    4 months ago, # ^ |
    Rev. 18   Vote: I like it +9 Vote: I do not like it

    I really like this formula. It is elegant and works under any prime modulo. Thank you for sharing it!

    Here's a more detailed explanation and another way to look at it: Let $$$n \geq 1$$$ be a fixed integer.
    As in tutorial, let $$$p_i = \frac{(-1)^i}{i!}$$$ and $$$q_j = \frac{j^n}{j!}$$$.
    Then $$$S(n, k) = \sum\limits_{i+j=k} p_i \cdot q_j$$$.

    Consider a matrix $$$M$$$ in which $$$M_{i, j} = p_i \cdot q_j$$$ for $$$0 \leq i, j \leq n$$$.
    Then $$$S(n, k)$$$ is the sum of entries on the antidiagonal $$$i+j = k$$$.

    Suppose we want to find $$$S(n, 0) + S(n, 1) + ... S(n, k)$$$ for some $$$k$$$.
    That is to sum the entries above the antidiagonal $$$i+j=k$$$.
    We can sum these values column by column.
    For a fixed column $$$j$$$, the sum is $$$q_j \cdot \sum\limits_{i=0}^{k-j} p_i$$$.
    Thus, $$$S(n, 0) + S(n, 1) + ... S(n, k) = \sum\limits_{j=0}^{k} q_j \cdot \sum\limits_{i=0}^{k-j} p_i$$$.

    To compute this efficiently, note that $$$\sum\limits_{i=0}^{k-j} p_i$$$ is just the sum over a prefix of $$$p$$$.

    My implementation: https://codeforces.com/contest/1644/submission/148117254

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

    I have a question, though. To compute $$$S(i,1)+S(i,2)+...+S(i,k)$$$, the formula requires to find $$$t^i$$$ over $$$t=0,1,...,k$$$. Can this be computed (or precomputed) in $$$O(i)$$$?

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

      Oh I get it.
      We can use linear sieve to find all primes $$$p$$$ and compute $$$p^i$$$.
      For a composite $$$x = a \cdot b$$$, compute $$$x^i$$$ as $$$a^i \cdot b^i$$$.
      This is $$$O(k \log i / \log k) = O(i)$$$

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

C can be done with 2D DP. My submission is linked below 147347109

Note that I only used the custom "getbigger" function instead of the max function because the max function was being annoying for me.

»
4 months ago, # |
Rev. 4   Vote: I like it +33 Vote: I do not like it

Here are two alternate solutions for F. (Neither one uses any prior knowledge about the Stirling numbers.)

Simple no-FFT solution
EGF+ODE solution
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me understand why we need the break condition in D? What are those cases requiring that break?

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

    Let's say after i'th query you get all rows (column can be anything) in the query. This would mean that whatever colours were present in all the cells before, are updated (possibly to the same colour but updated for sure) so any query that was processed before i'th query is no longer relevant to the final state. If however, we do process them in reverse order, it will update colour of some cell which shouldn't have been the case. Same goes for queries covering all columns instead of rows hence we have to check for both.

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

    Break condition is required when we have painted either all the rows or all the columns since after that final colour of a query would remain same.

    Remember
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am getting TLE for problem C but Idk why. My submission 147508883

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem D, why is the answer equal to k to the power of valid queries that have at least one cell belong to them? I am unable to understand. Why is "to the power"?

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

    Because for each valid query you have k different choices and these choices are independent to the ones that selected so far.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Apparently an O(n^2) solution is what is wanted by C... I guess I should have just went for it. I tried finding a solution where I was trying to basically mask the array and use those masks to find the respective points and values of the sums. Good problem overall, just didn't realize it could only be solved with O(n^2) and that was good enough.

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

can anyone help in telling me what is wrong in my solution for Problem B 147407485. This solution is working on visual studio community and i have checked my times that it gives distinct anti-Fibonacci permutations only. but when submitted on codeforces online judge it shows "wrong answer on test 2".

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

    Failing testcase: Ticket 633

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

      thanks for reply.`` When i compile the program on visual studio with same input as shown by you, visual studio is showing different output.

      ![](https://disk.yandex.com/i/JFdst1Kg8uUVRw)

      link provided by you is showing two same permutations but visual studio is showing all distinct permutations.

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

        It's because you are initializing the seed dynamically (based on current time). It's entirely possible that it produces one answer on your machine, another on mine, and a completely different one on Codeforces. Hence, you can't guarantee it to produce a correct solution.

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

          thanks again . look at this submission 147594424 in this i have removed seed but even then it is not accepting the answer. now it is showing that test case 7 is not anti-fib permutation. However this is not the case as one can easily verify that in case 7 program is printing anti-fib numbers only.

          • »
            »
            »
            »
            »
            »
            4 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it
            1. You removed the seed, but you did not remove the randomization (see the random_shuffle function). Hence, your program can still produce different answers based on the seed chosen during runtime.

            2. The error message does not mean that your program anti fibonacci permutation for $$$n = 7$$$. It means, that it prints an anti fibonacci permuation for some $$$n$$$ which is present in testcase 7.

            3. If you have any more doubts, you can simply use my website to get failing testcases for your submission. For example, your latest one fails on Ticket 636

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

In problem D, why TLE with vector(int) and AC with vector(bool) , time complexity doesn't change. AC code with bool,
TLE code with vector

UPD: People already answered this in Announcement for this contest

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

the solution for question C gives TLE. Didn't expect it to be like that in editorial.

»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody help me that where is the bug in my code? (Problem A).

#include <bits/stdc++.h>
#define disabled { f = 0; break; }
using namespace std;

bool key[3];

int main() {
	int t;
	cin >> t;
	while (t--) {
		for (int i = 0; i < 3; i++) key[i] = 0;
		string s;
		cin >> s;
		bool f = 1;
		for (char ch: s) {
			if (ch == 'r') key[0] = 1;
			else if (ch == 'g') key[1] = 1;
			else if (ch == 'b') key[2] = 1;
			else if (ch == 'R') if (!key[0]) disabled
			else if (ch == 'G') if (!key[1]) disabled
			else if (ch == 'B') if (!key[2]) disabled
		}
		if (f) puts("YES");
		else puts("NO");
	}
	return 0;
}
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Try this. This is exactly same code but with better punctuation marks. Your else-if statements for char — R G B have problem as if block in these may not be recognized by compiler correctly. ~~~~~

    #include <bits/stdc++.h>
    #define disabled { f = 0; break; }
    using namespace std;
    
    bool key[3];
    
    int main() {
        int t;
        cin >> t;
        while (t--) {
           for (int i = 0; i < 3; i++) key[i] = 0;
           string s;
           cin >> s;
           bool f = 1;
           for (char ch: s) {
             if (ch == 'r') key[0] = 1;
             else if (ch == 'g') key[1] = 1;
             else if (ch == 'b') key[2] = 1;
             else if (ch == 'R'){ if (!key[0]){ disabled}}
             else if (ch == 'G'){ if (!key[1]){disabled}}
             else if (ch == 'B'){ if (!key[2]){disabled}}
           }
           if (f) puts("YES");
           else puts("NO");
        }
        return 0;
    }

    ~~~~~

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

      Thanks. I know that where is the bug. If i change the code as the following, you can know what i mean.

      #include <bits/stdc++.h>
      #define disabled { f = 0; break; }
      using namespace std;
      
      bool key[3];
      
      int main() {
      	int t;
      	cin >> t;
      	while (t--) {
      		for (int i = 0; i < 3; i++) key[i] = 0;
      		string s;
      		cin >> s;
      		bool f = 1;
      		for (char ch: s) {
      			if (ch == 'r') key[0] = 1;
      			else if (ch == 'g') key[1] = 1;
      			else if (ch == 'b') key[2] = 1;
      			else if (ch == 'R') 
                                   if (!key[0]) disabled
      			     else if (ch == 'G') 
                                       if (!key[1]) disabled
      			         else if (ch == 'B')
                                           if (!key[2]) disabled
      		}
      		if (f) puts("YES");
      		else puts("NO");
      	}
      	return 0;
      }
      

      I Accepted the code. Thank you very much.

»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

As for problem F, I think the solution described in the tutorial is in $$$O(n\sqrt{n}\log n)$$$ time complexity, because we have $$$O(\sqrt{n})$$$ $$$\lceil\frac{n}{i}\rceil$$$ s, and calculating each of them takes $$$O(n\log n)$$$. But the solution of F says it takes $$$O(n\log^2n)$$$, am I wrong or the tutorial made a mistake? Can anyone help me?

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

    The polynomial describing $$$A_i$$$ has $$$\min(i, k) + 1$$$ terms, so the complexity of calculating $$$A_i$$$ is $$$O(i \log i)$$$ and the total complexity is $$$\sum \limits_{i = 1}^n O(\frac n i \log \frac n i) = O(n \log^2 n)$$$.

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

Can someone please help me with this solution? I am not getting why this sol isn't working, it would be great if someone can suggest a test ( of reasonable length)case in which it fails .151373734

PS: I tried finding the array with the largest possible sum and its length (**let l **) and for all values of k <= l, I added k*x to the max sum and for all k > l, I checked for subarray of size k with the largest sum and printed max of ( prev_sum, (cur_sum + k*x)).

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

I am doing question D the same way, but getting a wrong answer. I have used a set to store the rows and columns and then proceed with the maximum size among the two. Can anyone help me out, please? Link for my solution: https://codeforces.com/contest/1644/submission/155271519

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

My submission for problem D. https://codeforces.com/contest/1644/submission/157867234 Anybody please tell me where and why the code fails