arsijo's blog

By arsijo, 4 months ago, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
 
 
 
 
  • Vote: I like it
  • +119
  • Vote: I do not like it

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

What about shuffle solutions in F? Just mistake?

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

Is it possible to add this case to the system tests for F and hopefully a rejudge?

https://pastebin.com/dgWMkY4z

Both the following and possibly many more submissions fail on this case:

https://codeforces.com/contest/1186/submission/56222396

https://codeforces.com/contest/1186/submission/56210105

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

I want a prove for the incorrectness of the greedy solutions in F. Really puzzled...

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

    There is no need for proof of incorrectness, ever. There is only need for counterexamples, and there are many here. You can try the test case I provided above.

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

    One of the problemsetters wrote it: For example, suppose there are 4 groups A, B, C, D, each containing 10 nodes. Suppose all nodes from A are connected to all nodes from B, all nodes from B — to all nodes from C, all nodes from C — to all nodes from D. Then there are 3* 10^2 = 300 edges in total, so we want to leave no more than (300+40)/2 = 170 edges. However, if we choose what to delete randomly, we may just delete all edges between B and C accidentally. Then we won't be able to delete anything else. So we will be left with 200 edges.

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

thanks for editorial sir

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

It's easy to see that f(c,d) is even if and only if cntb and cntc have same parity
Someone can help to understand this in problem C? I don't see why that is always true

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

    Let the number of 1s in b that have the same index in c be x. Now total number of mismatched indices are cntb + cntc — 2x. Now this will be even if and only if cntb + cntc is even. Hence their parity should be same.

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

      thanks for your additional explanation.

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

      Shouldn't you add 'y' as the number of '0's that have the same index and subtract 2y also from the value? I know it doesn't make a difference for the solution, but still, to keep things correct, you can add it.

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

        No, actually we are calculating number of places bits differ so bits differ if in first string we have 1 and 0 in second or vice versa. So we have total_bits_that_differ=cnt1-x+cnt2-x.

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

Can anyone elaborate 3rd solution? Cossack Vous and numbers

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

    Just take every element floor value and mark those point which are integers. Now sum the numbers. Sum can be less than equal to 0 . if 0 then print it, otherwise increment those value which are not marked by 1

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

Can you give a more formal proof od problem D?

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

(Problem F) For which case will such a solution fail? (Test case-31)

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

B is missing :p

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

In problem C one of the tags is FFT, how is FFT applied here?

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

    I wanna know as well

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

      You can replace 0's with -1's in both strings, and let c be the convolution of a with b reversed. Let a_i be the substring of a that starts in the ith position and has length equals to b, ma(x,y) the number of matches of the strings x and y, and mi(x,y) the number of mismatches. Now if you check c[i] with len(b)-1<=i<len(a) then c[i] = ma(a_i,b)-mi(a_i,b) (a match adds -1*-1=1 or 1*1=1 to c[i] and a mismatch add -1*1=-1). You also know that ma(a_i,b)+mi(a_i,b)=len(b) thus, from both equations, you have ma(a_i,b) =(len(b)-c[i])/2. Consequently, after calculating the convolution of a and b reversed you iterate over the interval mentioned and add 1 to the answer if (len(b)-c[i])/2 % 2 == 0.

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

    Similar Problem : CodeChef:: String Matching

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

Problem C submission code. How can i optimize more it is giving TLE on test 7.

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

    You can use prefix sum technique to store the number of ones until ith index in an array/vector and then simply consider all the substrings having length same as the length of string b. Here is my code:code

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

    Or you may not use prefix sums. You can calculate it lazy. code

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

Can you explain the solution of B task? It is interesting problem

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

Can someone explain how to calculate f(x,y) in "E problem ". I didn't get the tutorial above. Or if there is any other approach to this problem?

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

what is the error in this code for problem c??

include<bits/stdc++.h>

using namespace std; int main() { string a,b; cin>>a>>b; int al=a.length(),bl=b.length(),i,j,x,ans=0; for(i=0;i<=al-bl;i++) { int x=i,count=0; for(j=0;j<bl;j++) if(a[j+x]==b[j]) count++; if(count%2==0) ans++; } cout<<ans<<endl; return 0; }

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

    Always remember pastebin is useful and straightly paste it is ugly :^

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

      please can you check now.

      https://pastebin.com/xT5Gj9st

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

        In your following loop:(begins at line 8)

        for(i=0;i<=al-bl;i++)
        {
                int x=i,count=0;
                for(j=0;j<bl;j++)
                if(a[j+x]==b[j])
                count++;
                if(count%2==0)
                ans++;
        }
        

        The loops are nested, and it will be looped for (al-bl)*bl times, with a time complexity of $$$O(n^2)$$$. For $$$n\leq 10^6$$$ mentioned in the statement, it works too slow.

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

          thanks.But is there any logical error as it is giving WA for first test case and correct for second testcase.

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

            Read the statement, $$$f(b,c)$$$ returns the number of positions where the two strings are different, not the same.

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

another solution for C:

let the changes be equal to total position such that b[i]!=b[i+1].

now let cnt stores the total mismatch between first substring of a and b.

do cnt=cnt%2. if cnt is even: ans++

To calculate mismatch between just next substring of a and b: {

Better you draw 1st sample test case in notebook.(think now as we are shifting b to right.)

1.Now position where b[i]!=b[i+1] there will be +1( if previous match become mismatch ) or -1( if previous mismatch become a match ) in value of cnt and in either case cnt value change from odd to even or even to odd.

to keep it simple lets just +1 for those positions because we only concern about odd/even of the cnt.

so overall total +1 in cnt will be by + changes

2.take care about new mismatch and previous mismatch

(new) +1 the cnt if mismatch between last char of b and last char of current substring

(old) +1 the cnt if mismatch between first char of b and first char of current substring

if cnt is even: ans++

}

Link to my submission

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

how problem C can be solve using fft ?

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

    Let $$$n=|a|,m=|b|$$$. Suppose the string is 0-indexed. Let $$$f[i]=a[i],g[i]=b[m-i]$$$. You can find that

    $$$f(a[i\dots i+m-1],b[0\dots m-1])=\sum\limits_{j=0}^{m-1}(a[i+j]-b[j])^2$$$

    $$$=\sum\limits_{j=0}^{m-1}(f[i+j]-g[m-j])^2$$$

    $$$=\sum\limits_{j=0}^{m-1}(f[i+j]^2+g[m-j]^2-2f[i+j]g[m-j])$$$

    $$$=\sum\limits_{j=0}^{m-1}f[i+j]^2+\sum\limits_{j=0}^{m-1}g[m-j]^2-2\sum\limits_{j=0}^{m-1}f[i+j]g[m-j]$$$

    The first two parts can be solved with prefix sums. The last part, just do FFT with $$$f$$$ and $$$g$$$(let the product be $$$h$$$), then it is $$$2h[i+m]$$$.

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

can someone explain me in simple way in problem C why having same parity gives even no of change?

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

    f(b, c) == even no of changes

    let number of 1 in string b = x1, number of 1 in string c = x2, number of common 1 in both string = x,

    so, number of changes = x1 + x2 — 2*x, which should be even. /** 2*x is always even **/, x1 + x2 should be even , it implies x1 and x2 should be both even or both odd, hence should have same parity

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

      Hello @practise_ , can you please share in-depth resources regarding parity and related topics?

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

        parity simply means having same parity means both are even or both are odd

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

      thnks a lot

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

    Can You please explain me what is the meaning of "parity" here?

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

    there can be two types of mismatch in the problem

    let one string be c and other be b;

    the two types can be if there c[i]=0 and b[i] = 1;

    other case can be if c[i]=1 and b[i] = 0

    so the number of mismatch of first type is numc-x and second type is numb-x .

    where numc and numb are number of 1 in c and b respectively.

    total mismatch = numc+numb-2*x

    to make this even numc and numb must have same parity

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

Can you post Code solution of problem D for better understanding arsijo

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

In problem E, while doing this multiplication, ((fieldx−1)⋅(fieldy−1)−1)⋅n⋅m / 2 it can lead to overflow. Can someone suggest how to handle the overflow? I think it requires some sort of trick.

My solution is here: https://codeforces.com/contest/1186/submission/56266238

It is failing on test 5 due to overflow (at least that's what I think).

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

    Maximum answer can be 10^18 so that's not the problem(overflow). But you calculated your dp wrong. Your code with correctly calculated dp. Code

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

    As $$$x,y \leqslant 10^9$$$ and $$$n,m \leqslant 1000$$$, we have:

    $$$Field_x=\lfloor \dfrac{x-1}{n} \rfloor \leqslant 10^6$$$ and so is $$$Field_y$$$

    Thus, $$$((Field_x-1)\times (Field_y-1)-1)\times n\times m \leq 10^{18}$$$, which is in range of long long.

    Use long long for calculation.

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

Where is author's source code for F?

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

In problem C, It's easy to see that f(c,d) is even if and only if cntb and cntc have same parity. In other words if cntc≡cntd(mod2) then f(c,d) is even.

what is the meaning of parity here? I have looked up all the comments but cant found any clear explanation.

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

    A and B have same parity if

    A = B(mod 2)

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

      just to be sure, you mean A = B%2?

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

        no A % 2 = B % 2

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

          Ohh Ok I got it. I have figured out a way to solve even but how is the participant supposed to know that if cntc≡cntd(mod2) is true than only the string will be even.

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

Can anybody kindly tell me what's wrong with this code for problem C? — https://codeforces.com/contest/1186/submission/56220737

Also, is there any way to see all the entries in a large input in a testcase?

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

For problem F, you don't need to "find Euler cycle and do the following steps for each component independently."

Because adding fictive vertex makes the graph connected.

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

    It doesn't if a component has an euler cycle by itself(meaning all degrees are even).

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

I think I have a good idea of understanding Problem C.

Find out how many different positions of two strings A and B are equivalent to $$$\sum{a_i\bigoplus b_i}$$$

Because it only judges parity, it is equivalent to $$$XOR(a_i)\bigoplus XOR(b_i)$$$

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

    Can you explain a little bit better your solution?

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

      The task of the problem is to find out how many different positions of two strings A and B(A is the substring of string a,B is the string b)

      As I said above,it is equivalent to $$$XOR(a_i)\bigoplus XOR(b_i)$$$

      Because of two adjacent substrings of string a is just a character difference,so we can solve it in $$$O(n)$$$

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

In problem C, I don't understand the explanation for the problem. Please explain the pseudo code for the solution.

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

I don't understand solution problem D, anybody explain better?,i was seeing some solutions and most of them have this solution

https://codeforces.com/contest/1186/submission/56278052

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

    Let a[] be the given array of doubles whose sum is 0

    We need to find b[] such that b[i] = ceil(a[i]) or floor(a[i]) such that sum of all elements in b[] is 0.

    Fact: ceil(x) — floor(x) = 1 for any real number with a non zero decimal part ceil(x) = floor(x) for any real number with zero decimal part

    So let's initialize b[] such that b[i] = ceil(a[i]). Let's call the sum of this array as s. We need to make s = 0, and we can do so only by subtracting 1 from a set of 's' b[i]s (whose corresponding a[i] has a non zero decimal part).

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

      Thanks for explanation. I got it now. I have one more thing to ask if you dont mind. I am usually a python user and now I am shifting to c++ for simply the reason that it is way faster. But I am having difficulties finding an IDE for it. Could yo explain which IDE to select? I use debugging a lot

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

Can some one explain me last part of editorial E .I mean how author arrived at if bitcnt(a)+bitcnt(b) is an odd number, then the matrix is inversed. Also how do we determine if a field is inverted or not if its coordinates (x,y) are odd,odd or odd,even ?

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

One important note — (In tutorial of Problem E)in last statement "if bitcnt(a)+bitcnt(b) is an odd number, then the matrix is inversed" , indexing is considered from zero i.e suppose we are referring to first row and second column then that is (0,1). readers might get confused since in problem and in most of the part of tutorial of problem E indexing is considered from 1. Also bit count refers to number of 1's in binary representation of number and not least number of bits required to represent the number in binary.

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

For Problem $$$E$$$, $$$bitcnt(a)+bitcnt(b)$$$ tells you whether the matrix at position $$$(a,b)$$$ is inverted or not due to the following reason:

Imagine the whole infinite a grid as a big quadrant, which consists of $$$4$$$ quadrants, each of which consists of another $$$4$$$ quadrants, and so on. Then if you started looping on bits from the most to the least significant position (let the current bit in the loop be the $$$i_{th}$$$ bit), then checked the $$$i_{th}$$$ bit in both $$$a$$$ and $$$b$$$. If bits are $$$(0,0)$$$ you go to the top left quadrant, $$$(0,1)$$$ to the top right, $$$(1,0)$$$ to the bottom left, $$$(1,1)$$$ to the bottom right. Then you repeat the process for the quadrant you went to using the $$$(i-1)_{th}$$$ bit and so on. This shows then when you eventually reach your matrix, it will be inverted only if the parity of $$$bitcnt(a)+bitcnt(b)$$$ is odd.

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

Where is the author's code for problem F???

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

Can anyone explain me this code for problem C clcik here