chokudai's blog

By chokudai, history, 6 weeks ago, In English

We will hold Panasonic Programming Contest (AtCoder Beginner Contest 186).

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

 
 
 
 
  • Vote: I like it
  • +69
  • Vote: I do not like it

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

Are there any plans to hold an ABC on Sunday as well? Considering next week is goodbye rng_58 and many would like to jump that 2000 barrier to participate in them.

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

If anyone is interested, I'm currently planning to do a post-contest stream (twitch.tv/AnandOza).

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

Is it a hiring contest ?

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

Why don't you show start time like cf announcements? Or is there any reason you give just a link ?

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

    This is primarily because the time may vary from place to place, as per their time zone. timeanddate.com URLs can help with directly showing time converted in the local timezone, thus saves the confusion and hassle of converting them manually.

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

    I think only CF contests can have time-zone adjustable displays of event time. And to avoid the confusion harshitkumargupta mentioned, they are doing this.

    I wish all event times can be correctly displayed in CF blogs soon tho.

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

What is special about this contest?

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

very nice contest(especially problem D)

btw, how to solve F??

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

(k.x + s) % n = 0

given, n, s, and k, how to find the smallest x which satisfies this equation? I didn't try brute force as it will give TLE for sure.

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

    Even, if there was a brute force approach, it won't work for the sample test case (I tried for 10^7 iterations) and one of the testcases was giving the wrong answer.

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

      Could you please show me that which sample test case you didn't get the right answer through a brute force approach?

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

        What I did was to iterate from 1 to 10^8+ 7, it gave me answer -1, instead of 249561088 for 998244353 897581057 595591169. (correction, it was a silly bug :|). But still, I don't think it will work.

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

          It won't because you need 148897793 approx(1.5 * 10^8)itterations and you are just doing 10^8+7. There is no constraint on no of iterations

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

    This is what I did.
    (k.x)%n=(-s)%n
    Let g=gcd(k,n).
    We know that (k.x)%n takes all (i*g)%n values.
    If ((-s)%n)%g is non zero than answer is -1.
    For other case just divide k, n, and (-s)%n by g.
    Now the equation changes to (a*b)%m=c where gcd(b,m) is 1.
    It has a unique soln for a in range [0,m). Its a=(inv(b)*c)%m. You can use extended gcd to find that inverse.

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

      Yeah, modulo arithmetic does the work I guess.

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

      this is better, I did it by finding $$$x0, y0$$$ using euclids algorithm, and then checking sign and adjusting. Actually $$$s < n$$$ so no need of modulo $$$n$$$.

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

      According to cp-algorithm if we convert ax = b (mod m) to a/g x = b/g (mod m/g), this new equation's unique solution x' is not the only solution of original equation, there are exactly g solutions: x = x' + i m/g (mod m) for i in [0,g). How to prove that x' is the minimum solution?

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

        I tried to implement that, but no success. Can you shortly tell which of the input numbers n,k,s are the variables a,b,n of cp-algorithm?

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

          Check this AC submission with comments.

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

            Thanks, I see that pow(a, m-2) does not work here :/

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

              Yes, pow(a,m-2) comes from Fermat's little theorem (pow(a,m-1)%m=1) which works only if m is prime.

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

            why is c = n — s instead of c = s (line 68) in the mentioned solution?

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

              Takahashi is initially sitting on the chair that is S chairs away from the throne in the clockwise direction.

              Move: Go to the chair that is K chairs away from the chair he is currently sitting on in the clockwise direction.

              Draw some cases on paper and simulate if you are still unclear.

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

        All those g solns have same value mod (m/g). Just take the one with i=0 which is returned in above soln.

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

    Use extended euclid's algo to just find any solution to k.x-n.y=-s, then use shifting to find for finding minimum x>0

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

how to solve E,F?

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

    Here is how I solved problem E.

    So assume that position of the throne is at position n and we are at position s.

    So to reach the throne following equation can be formed —

    s + x*k = y*n where(x is the lowest positive integer)

    So this equation can interpreted as ax + by = c which is standard linear dopamine equation.(There are many good resources for this on internet).

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

      I was able to do until this point but can you tell how you solved this equation

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

        So we are having this equation right x*(-k) + y*n = s

        You can learn about solving such equation over here

        Now after reading that we have all the possible values of x that are in form of x = x0 — m*(n/g), and we need to find the a value of m for which x is the lowest possible equation which can easily be solved by basic math.

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

        Considering the process to calculate the greatest common divisor $$$d$$$ of $$$a$$$ and $$$b$$$. Let's try to get a pair $$$(x,y)$$$ such that $$$ax+by=d$$$. When $$$b=0$$$ , $$$d=a$$$ so that we can set $$$x=1$$$ and $$$y=0$$$. Assume that we have already known $$$bx+(a\%b)y=d$$$. Then $$$d=bx+(a-(a/b)*b)y=ay+b(x-(a/b))$$$ so we can change $$$x$$$ into $$$y$$$ and change $$$y$$$ into $$$x-(a/b)$$$ at the same time. Repeat the operation above so that you can get a pair $$$(x_0,y_0)$$$ such that $$$ax_0+by_0=d$$$. All of the pairs $$$(x,y)$$$ satisfy the condition if and only if $$$x=x_0+k(b/d)$$$ and $$$y=y_0+k(a/d)$$$ ($$$k$$$ can be any integer).

        You can have a look at the following function to understand better.

        int x,y;
        int exgcd(int a,int b)
        {
        	if(b==0)
        	{
        		x=1,y=0;
        		return a;
        	}
        	int d=exgcd(b,a%b);
        	int p=y,q=x-y*(a/b);
        	x=p,y=q;
        	return d;
        }
        
  • »
    »
    5 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I have a solution for F involving policy-based DS(indexed set).
    First, you calculate the number of cells reachable by using steps down and then right.
    Then you need to calculate (for every column) how many rows are there such that their minimum y is less than the current column number. Add that number to the answer. This can be done using a Policy-based DS.

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

      Can you elaborate the part Then you need to calculate (for every column) how many rows are there such that their minimum y is less than the current column number. Add that number to the answer ?

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

    One solution for F is as follow :

    Let us find 2 arrays, call them R[H], C[W] and initialize R[i] = {w+1}, and C[i] = {h+1} for each valid i. So, the information we store in R[i] = first column which has a block in ith row, similarly , C[i] = first row which has a block in ith column.

    Now in first move we can go to anything from [1,R[1]] and [1,C[1]] and then we also have stored value, of how many blocks we can visit in front of each of them . So, we just add them up.

    Are we considering all the blocks which can be visited ? Yes. But, we also need to now remove the blocks which can be visited from both paths, going right then down or going down and then right.

    To count these cases, here is one approach 
    for each row, the maximum such blocks which can be repeated are min(R[1],R[i]), and we will not be repeating the cases, if there exists a row above them, which has any of these columns blocked.
    So, sort the blocked points by row, then for each row, insert the columns into a set, and we need to get lower bound for min(R[1],R[i]). 
    

    You can use pbds, segment tree or anything you like to answer these queries.

    Code

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

did some one use BIT TREE TO solve F ? if yes share ur code plz

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

    You can have a look at my code.

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

    I tried using merge sort tree and policy based trees to but code failed for 15 test cases and they dont share test cases I don't know what is the error now shifting on BIT lets see the results.

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

    I used segment tree with two operations: point update and (sum of range, number of zeroes in a range).

    Link to code

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

How to solve C for larger constraints? Preferably,$$$N<=$$$ 10^18

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

    we can use DIGIT-DP for modulo 8 and modulo 10 separately, but i am not sure about how to calculate intersection of both the sets.

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

How to solve E? I was able to deduce that if throne positon is not divible by gcd of n and k answer is -1. But i couldnt figure out final answer without doing brute force.

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

Has any of you tried persistent segment tree for the last problem? Thanks! I want to know how my solution went wrong: https://ideone.com/AH50pe

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

Could someone please explain an efficient solution for D? My (brute force) attempt timed out, but I'm unable to figure out the reasoning behind other contestants' accepted answers.

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

This is a really good contest. Although I didn't do as well as I want,(I got WA 3 times during the contest) it shows me that I have something unfamiliar with and I must be more careful to make my solutions correct.

At the same time, I won't be able to join in AtCoder Grand Contest 050 (Good Bye rng_58) as a rated contest. So I hope that there is going to be another contest before the AGC contest for people like me.

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

So what's the editorial of F?

I think about it for a long time, but just can't solve it.

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

    Maybe you can have a look at my code first, I am trying to write the editorial for F now.

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

    First, calculate $$$a[i]$$$ which means the number of squares in the $$$i$$$-th row that you can reach (from $$$(i,0)$$$ in one move) and $$$b[i]$$$ for the $$$i$$$-th column, respectively.

    Set $$$c=a[1]$$$ and $$$d=b[1]$$$, so that you should only consider the first $$$d$$$ rows and the first $$$c$$$ columns. The only problem we need to solve now is to calculate the number of sqaures $$$(x,y)$$$ such that $$$1 \le x \le d$$$, $$$1 \le y \le c$$$, $$$y \le a[x]$$$ and $$$x \le b[y]$$$.

    We solve this problem in the ascending order of $$$b$$$. When we consider $$$i$$$, we need to put the first $$$b[i]$$$ elements of $$$a$$$ in BIT so that we can only calculate the number of elements which are not less than $$$i$$$ in BIT, which is called $$$p[i]$$$.

    Finally, the answer is $$$\sum_{i=1}^c(b[i]-p[i])+\sum_{i=1}^da[i]$$$.

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

Problem E

We start at position S, and need to count the number of steps to get to position 0. One step goes K positions. So

$$$x\cdot k=n-s$$$ |mod n

Implementing this according to https://cp-algorithms.com/algebra/linear_congruence_equation.html produces nonsense results for me.

Can somebody explain?

Code, not working

Edit: I am aware that there are basically 3 possible solutions (maybe some more): Linear Congruence Equation which is based on the inverse. The Diophantene equations which are based on the extended euclediean algo. And we can also solve this using the chinese remainder theorem (with only one equation).

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

    While I am not aware of the Linear Congruence Equation method — I am reasonably sure it should be if(b%g!=0) in your lce method.

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

      Thanks, that was wrong in the code.

      But the more basic error is stated in the editorial know: The inverse modulo M can be calculated with extended Euclidean algorithm. (Note that $$$A^{M-2}$$$ is not necessarily the inverse of A if M is not a prime)

      So I did wrong in calculating the inverse always with pow(a, m-2).

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

      Can you plz confirm that (b%g != 0) comes from the fact that for any linear congruence a = b(modm) this must satisfy -> m | (a-b). As we have already taken the gcd of a and m. So, remaining b must be divisible by m in order the satisfy the condition? Correct me if i am wrong! And one more thing if gcd is not 1 then, inverse shouldn't exist. But here we are still checking the condition (b%g != 0) and after that we are finding the inverse. CODE

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

    (b%g!=0) is one, also i was getting garbage values until i realised that modular exponentiation can only be used to find inverse if the given "mod" is a prime. Else it'll give wrong answers. i applied the same to your code and it gets right answers.I also changed MOD=n just in case.

    AC

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

can someone suggest me the problem simillar to E for practice?

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

Problem E was kinda similar to this codechef problem CVDRUN. Although constraints are smaller on this.

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

For problem E, In the editorial, its mentioned the answer is (Ainverse * B) for AX ≡ B mod M .. suppose if A = 3 , B = 6 , M = 10.. then (Ainverse * B) = 7*6 = 42 which satisfies the equation but isn't the minimum X , the minimum X is 2. How can we find the minimum X ?

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

    You should take the product modulo M as well, and $$$42 \equiv 2 \pmod {10}$$$.

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

Problem D is explained in gfg

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

[user:kyopro_friends], chokudai, Kmcode

hey,can you please add the test cases of this contest, I looked for it in https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=0 but there isn't for this contest, there is some Panasonic 2020 but that contest isn't this one.

Thanks.

Never mind ,I found the bug