April Cook-Off 2020 Discussion

general
7

Refer to solution - > CodeChef: Practical coding for everyone

8

how to do minops??

9

but how would you keep a track of number of operations this way, or we don’t need them that is the case ?

10

https://www.codechef.com/viewsolution/32065125

MATbreak
can someone help me to find out the error??

11

See this solution → CodeChef: Practical coding for everyone

12

When will the Submit button be activated for MATBREAK?

13

TOWCNT : Can be done using concept of slope. Maintain min and max slope for both left and right lines. Only those lines whose tops are between these slope values will be visible. Now modify the min/max slope accordingly. Few more small things to be kept in mind, like the inputs for lines may not always be in sorted order of their x coordinates, etc.
Complexity = O(n^2)

Think for yourself what I mean, and if it doesn’t strike, reply here.

1 Like
14

For KARRAY, can anyone help me figure out my idea goes wrong?

  • First of all, G(i, j) is just i XOR j.

  • If we consider the value added from a position x to a position y for the ith bit:

  1. If both have the same bit state, then there is no contribution.

  2. If they have different bit states, then 2i * ay is added to ax.

  • Therefore, we only need to store the sum for a given bit i for each of its states.

  • Now the next year the sum for the ith bit in the on state is just 2i into sum of off state and vice-versa. Repeat this k times.

  • Add the corresponding sums for bits to the original number

I suspect the mistake is in the second last step but I can’t seem to prove or disprove it, can anyone help?

Edit: Also have rating changes updated only on discuss but not the main site ? I’m 6 star on the normal site, but 5 star here.

1 Like
16

I haven’t attempted this one… Can you help me MINOPS… My solution TLE’d but I wanted to know if my approach was right or wrong solution link → CodeChef: Practical coding for everyone

17

My Solution
I did Exactly the Same thing,But Why I got Wrong Answer.

18

I hope that the sample test cases must be clearer for a better understanding of problem .

1 Like
19

This post was flagged by the community and is temporarily hidden.

20

I thought this approach too, but O(n^2) solution wouldn’t mean 4e8 operations, leading to >1 second time limit?

21

Please help me with my solution for MINOPS, I can’t figure out why it is giving WA.

22

You shouldn’t use the \verb!pow()! function because you might overflow while doing so. Instead, you should use modular exponentiation, which is discussed in this article here: Binary Exponentiation - Algorithms for Competitive Programming

2 Likes
23

MATBREAK - giving wrong answer. Please help anyone
long long product = a;
long long current = aa;
for(int i = 2;i <= n;i++){
long long int powerval = power(current,2i-1,mod)%mod;
product = (product%mod+ (powerval)%mod)%mod;
current = ((powerval%mod)*(current%mod))%mod;
}
cout<<product;

24

Read the constraints carefully, n can only be upto 2000 in a given test, 20,000 is the maxmimum sum over all test cases, so the worst case is actually 10 tests of size 2000 which takes only 4 x 107 operations.

2 Likes
25

thanks a lot, makes sense.

26

PROBLEM CODE: LIFTME
#include<bits/stdc++.h>
#include

using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
long long int n,q,a,lastrnumber=0,sum=0;
cin>>n>>q;

    for(long long int i=0; i<q*2; i++)
    {
        cin>>a;
        sum=sum+abs(lastrnumber-a);
       lastrnumber=a;
    }
    cout<<sum;

}
return 0;

}

why it failed ?

27

You should take input of both the numbers(f,d) other wise they would get mixed up and you would end up taking d as f in the next iteration. And sum += abs(current-f); sum +=abs(f-d);current = d;

1 Like