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);
    }
}

Maybe it will not be bad to expand a little bit on how k * k < s will result in either k or k — 2, l didn't realize this fact during the contest qwq.

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^2)$$$
My Solution: Submission

Consider that $$$s < 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

Guys I can see my rank on friends standing but not on common standings page, will my submissions be skipped?

I didn't copy from anyone else. I copied SieveOfEratosthenes which was available before contest on gfg page which doesn't violate cf rules. So why can't I see myself on final standings page?

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?

Great Contest!

What's the approx limit of operations in 1 sec on CF ? In prob E, what's the final tc of the whole code. imo its [1o^3 * (n / ln(n))] which is still 7 * 10e8. Wouldn't it give tle given 2 secs?

How easy is problem c,but it still trouble me a long time

Don't forget to praise the moon!

There is an O(1) solution for D. It is as follows (Python 3):

for _ in range(int(input())):
    n, m, k = map(int, input().split())
    distribute = -(-k // n)
    groups = m - distribute + 1
    ans = -(-distribute // groups)
    print(ans)

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 D O(1)

int minimumLongestBench(int n, int elements) {
    int numOfSeparators = n - elements;
    return n / (numOfSeparators + 1);
}

void solve() {
    int n, m, k;
    cin >> n >> m >> k;
    int elementsInMostCrowdedRow = (k % n == 0) ? k / n : k / n + 1; // after deviding on all rows
    cout << minimumLongestBench(m, elementsInMostCrowdedRow) << endl;
}