Problem D O(1)

void solve(){

ll n,m,k;

cin>>n>>m>>k;

ll total=(n*m-k)/n;

ll kena=m-total;

cout<<(ll)ceil((float)kena/(float)(total+1))<<endl;

}

int main(){

ios::sync_with_stdio(false);

cin.tie(0);

int t=1;

cin>>t;

while (t--)

{

    solve();
}

}

F has a nice explanation

Praise the sun! Solaire posture

In G, I wasn't able to prove the fact where the answer will always be $$$k$$$ or $$$k - 2$$$ for $$$s \ge k^2$$$, so I am posting my solution for the same.

Main thing to note is that for each value of power $$$x$$$, we only need to consider $$$x$$$ different residues modulo $$$x$$$, and particularly for each turn around step we only need to consider the maximum $$$x$$$ values we can reach if we are travelling forwards or the minimum $$$x$$$ values if we are travelling backwards. Running complexity is $$$O(k^2)$$$ for each valid $$$k$$$ resulting in overall complexity of $$$\begin{equation} \sum_{i=1}^{k} i^2 = O\left(\frac{k(k+1)(2k+1)}{6}\right) \end{equation}$$$

Edit: My Submission — 312461704

What is the reason behind of making k <= 1000 and sum of k <= 2000 in G? I just didn't write the code because I have never wrote an n^3 algorithm for n <= 1000. And yes it has very nice constant factor and in practice works very fast. But why couldn't u make it like k <= 800, sum <= 800, any unintended solutions that pass under smaller constraints?

Cool contest!

In fact there are two ways to approach the problem $$$F$$$: either by counting ways to reach the current 'X' index from the neighboring 'X' indices or vice versa, counting ways to reach the neighboring 'X' indices from the current. The first approach can be implemented with prefix sums and the second via a difference array.

In problem G I just "felt" the algorithm wouldn't run slow, then I submitted the code and got AC.

Interesting G.

Using derivatives to prove the $$$\Theta$$$ of G may be more intuitive&simple (⑅˃◡˂⑅)

Thanks for a great contest!!!

As per my current rating, of 1076, If I have solved questions till E, how much will the rating change ?

Problem D

#include <stdio.h>
int main()
{
    int t;
    scanf("%d", &t);
    int n, m, k, groups, num;
    while (t--)
    {
        scanf("%d%d%d", &n, &m, &k);
        n = (k - 1) / n + 1;        // max num per row (ceil)
        groups = m - n + 1;         // m = (group - 1) + n;
        num = (n - 1) / groups + 1; // num per group (ceil)
        printf("%d\n", num);
    }
}

Problem D O(1)

void solve(){
    int n , m , k;
    cin >> n >> m >> k;
    int ans = m / (( n * m - k) / n + 1);
    cout << ans <<endl;
}

Can G problem be solved in $$$O(K^2log(K))$$$
My Solution: Submission

Consider that $$$s \lt k*k$$$

• It can be observed that the visitable points form continuous ranges. I try to maintain the visited points as ranges $$$[lx , rx]$$$.
• My claim: number of continuous visited ranges (segments) are <= k, after every turn.
• Reason: Say power was $$$x$$$ , so adjacent visitable ranges have atmost x gap. So for the next turn with power $$$x-1$$$ the adjacent ranges would definitely merge, new ranges are created only at the boundary points.
• Propagating the intervals to any multiple of x can be done using sliding window.
• I am bad at explanation, Correct me if i am wrong anywhere.

Can any one explain another approach for problem f ?

in d part for the binary search suose you wrote while(l<=r) you get TLE error ,can someone tell me the calculation why ?

can anyone please explain me in problem-G; when s=10 and k=4 how is the answer 2

Some how I find C is the most difficult one among A-F, I have read the editorial, but can not I find a way to come up with solution, why people can relate to the fact that even length can not be constructed in the first place then gradually come up with the solution?

Don't forget to praise the moon!

O(k^2logk) solution for G.

For convenience, we will only consider the round of jumping to the right here. The turn that jumps to the left is symmetrical. If the current jump distance is k0, then for each modulo result of k0, we only need to record the smallest position. Because smaller positions can always jump to larger positions. Next, consider turning at each position. These positions, such as d, d+k0, and d+2k0, must form a cyclic interval in the form of k0-1. What we need to do is to take the maximum value of the cyclic interval for the arithmetic sequence. It can be achieved using a suitable data structure.

Problem-F is wrong, you have not calculated the possibility of Igor climbing from level x to level x+2,x+3,....x+n directly, If Igor can't skip any levels while climbing from one level to another you should have clearly mentioned this in problem statement ;(

I think I have a proof that my solution for G (which is basically the same as the editorial solution, but with dynamic programming instead of BFS) works in $$$O(k^2)$$$ per test case.

Let $$$x$$$ be the maximum integer such that $$$s \ge x \cdot k$$$. In other words, $$$x$$$ is $$$\frac{s}{k}$$$, rounded down.

Each value of Gleb's power is processed in $$$O(x \cdot k)$$$, and I claim that after we decrease Gleb's power by $$$O(\frac{k}{x})$$$, we will find the answer. So, if this claim is true, it works in $$$O(x \cdot k \cdot \frac{k}{x}) = O(k^2)$$$.

Let's prove this claim. Initially, Gleb is at point $$$0$$$ and has power $$$k$$$. Let's consider the points where he can be after we decrease his power by $$$2$$$. If he moves $$$i$$$ times to the right, makes a U-turn, moves $$$i$$$ times to the left, and makes a turn again, he will be in point $$$i$$$. And the maximum possible value of $$$i$$$ is $$$x$$$, so, after we decrease Gleb's power by $$$2$$$, he can be in any point from $$$[1, x]$$$ (and possibly some other points we haven't considered yet).

Using a similar argument, we can prove that after we decrease his power by $$$2$$$ again, Gleb can be in any point from $$$[2, 2x-1]$$$, and so on. So, after $$$2i$$$ power decreases, there is a segment of length very close to $$$i \cdot x$$$ in which every point is reachable by Gleb with his current power. As soon as this segment's length becomes equal or greater than his current power $$$k-2i$$$, there will be at least one point $$$p$$$ in this segment such that $$$p \bmod (k-2i) = s \bmod (k-2i)$$$, so the point $$$s$$$ will be reachable with current power. If we take $$$i = \frac{k}{x}$$$, the length of the segment will be very close to $$$x \cdot \frac{k}{x} = k$$$.

I'm truly dissapointed by the testcases on G , if I would have got a wrong answer I would have changed the range from 0 to n instead of 1 to n.

I got TLE on system testing for problem E just because of j=1. How?! (j=2 got AC)

#In The Name Of Allah





n=10**7
prime = [True for i in range(n+1)]
p = 2
while (p * p <= n):

    # If prime[p] is not
    # changed, then it is a prime
    if (prime[p] == True):

        # Update all multiples of p
        for i in range(p * p, n+1, p):
            prime[i] = False
    p += 1
prime[1]=False


t= int(input())
for z in range(t):
  n=int(input())
  ans=0
  for i in range(1,n):
    j=1
    while i*j<=n:
      if prime[j]:
        ans+=1
        #print(i,j)
      j+=1
  print(ans)

There is no way 63% of people that solved problem A, can actually solve problem C. I find problem C from this contest (division 3 contest) to be much harder than problem A from the previous division 1 contest (Codeforces Round 1012). The mentioned problem A was solved only by 935 persons, this problem C was solved by 15434 persons. Also, not to mention the difference in ello/rating between people that participated in the division 1 contest vs the rating of the people that participated in the division 3 contest. (In other words, the persons with higher rating can't solve the easier problem, but persons with lower rating can solve the harder problem).

Praise the sun!

How to implement prefix sum in memoization? Anyone help. 312470925

In F while selecting second hold on same row, it is done

dp[i][j][f]= dp[i][j][f]+∑j+dy=j−d dp[i][y][1]−dp[i][j][1]

But why here dp[i][y][1]? shouldn't it be dp[i][y][0]? why we take another hold if we already took 2?

Praise the sun!

Can someone tell me why we define a and b as:

a=gcd(a,b)⋅x, b=gcd(a,b)⋅y for some x and y Where does this come from

for problem E , the sum of n overall test cases isnt required to be bounded we can realize that for each number x it has number_of_distinct_primes(x) relations under it which inspires a dp solution where

dp[i] = dp[i — 1] + number_of_distinct_primes(i);

312619387

also another solution for problem G

let dp[i][j] denote the following

for a movement with same parity as k the minimum reachable cell such that its index equals j mod i

for a movement with different parity from k the maximum reachable cell such that its index equals j mod i

ans is the first time a movement with the same parity as K has s % movement is reachable

transitions are kind of hard to explain honestly but i'll leave a submission and if maybe i've time later i'll explain them

312626019

complexity o(k * k * log(k))

For problem E, I was able to pre-compute the answer of all n up to 1e7. However, the test case limit was up to 1e3, gives enough time to have a loop over all prime which is not required with pre-compute. So, even if the test cases are 1e7, it would have worked.

\[^-^]/

4 line solution for F (except for template)

Using lazy segment tree

https://mirror.codeforces.com/contest/2091/submission/312526600

For Problem E n=5 how is ans 4?

for b = 2, a = 1 is only solution such that F(a, b) = 2 for b = 3, a = 1 is only solution such that F(a, b) = 3 for b = 4, there is no solution for b = 5, a = 1 is only solution such that F(a, b) = 5 b from 6 is > 5 since it's > n

So ans should be 3?

Can anyone tell me why Binary Search has been mentioned in the tag of Problem F? I get it uses Prefix Sum along with dp states but where have we used binary search ??

2091G - Gleb and Boating I solved it in O(k^2 log k). Let's consider the number m (=k-2*j), let's get a dp of size m, where in the index i there will be a maximum or minimum position (depending on where we are going at the moment: left or right) that can be reached and which has a remainder i modulo M. Thus, we will iterate through all q from k to m and update dp, if at some point we have dp[s%m] ==s, then m suits us. Let's call this algorithm for m as check(m) -> true/false. If we consider all the numbers k, k-2, k-4, ..., and for them check(k), check(k-2), check(k-4), ... then false will go first, then true. We'll do a bin search for them and find the answer. If everything is false, we'll output 1.

My solution: 319579708

in F in last fomrula

dp[i][j][f]=dp[i][j][f]+∑j+dxy=j−dxdp[i+1][y][0]

as given in qn. for vertically we can go one by one up only. then how we directly going above

Each subsequent hold is not lower than the previous one; At least one hold is used on each level (i.e., in every row of the rectangle);

can someone explain me how did thy get k=pi−i (mod n) from (i+k) mod n=pi in question C. I mean how did they simplify (i+k) mod n ?????????????????????? and what goes where ?

.

Problem D O(1):

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t; cin >> t;
    while(t--){
        int n,m,k; cin >> n >> m >> k;
        int spots;
        if(k%n == 0) spots = k / n;
        else spots = k / n + 1;
        int splits = m - spots;
        int section_length = m / (splits+1);
        cout << section_length << '\n';
    }

    return 0;
}

D: O(1)

void solve() {
   int n,m,k;
    cin>>n>>m>>k;
    int x=(k-1+n)/n;
   // debug(x);
   int y=(m-x)+1;
   cout<<(m/y)<<endl;
}

My thinking process for problem E is slightly different than the editorial, but using the same fact anyway.

Case $$$a = 1$$$: $$$lcm(a, b) = b$$$ and $$$gcd(a, b) = 1$$$, thus if $$$b$$$ is prime, it's a valid pair;

Case $$$a \gt 1$$$ and $$$gcd(a, b) = 1$$$: $$$lcm(a, b) = ab$$$ and gcd(a, b) = 1. But $$$ab$$$ cannot possibly be prime. Thus, pairs of coprime numbers are invalid.

Case $$$a \gt 1$$$ and $$$gcd(a, b) = k \ne a$$$: This is a case where $$$a$$$ and $$$b$$$ are non-coprime, and $$$b$$$ is not a multiple of $$$a$$$. We prove by contradiction. Assume $$$\frac{lcm(a, b)}{k} = prime$$$, then $$$lcm(a, b) = \frac{a \cdot b}{k} = k \cdot prime$$$. Let $$$m = \frac{a}{k}$$$ and $$$n = \frac{b}{k}$$$, then $$$\frac{km \cdot kn}{k} = k \cdot prime$$$, and we have $$$m \cdot n = prime$$$. This is a contradiction. Thus, we proved that for a pair of non-coprime numbers with a gcd smaller than $$$a$$$, the statement is invalid.

In the end, we are left with only the case where $$$1 \lt a \lt b$$$ and $$$gcd(a, b) = a$$$. It's obvious to pick $$$b = a \cdot prime$$$.

For implementation, I first generated all the primes up to 1e7, and used binary search to search for the number of primes that can be used to obtain $$$b$$$ while not exceeding $$$n$$$. This is my submission.

I used the following approach for Problem D:

Idea:

Please notice that if k benches have to be distributed across n rows, atleast one of them will have ceil(k/n) desks.

Now, let the ith row contain ceil(k/n) desks. Let x = ceil(k/n).

Notice that this row initially had m empty spots. Now our task is to choose the locations of desks in such a way that the length of longest bench is minimised. If we calculate this minimal length, l, this will be our answer, because all other rows will have <= ceil(k/n) desks.

Please notice that m - x spots will remain empty in the row.

Our goal is to use these empty spots (gaps) to create discontinuities.

So, if m - x gaps are there, a group of x continuous desks can be divided into m - x + 1 smaller parts of continuous desks.

Now the largest of them will have ceil (x / (m - x + 1)) desks, which is the answer to the problem.

Please notice that this formula can be transformed to floor as floor(m / (m - x + 1)), which has been used in the code below.

void solve () {
    int n,m,k; cin >> n >> m >> k; 

    int x = (k + n - 1) / n;  // ceil (k / n); 
    cout << m / (m - x  + 1) << "\n";  
}