CandidFlakes's blog

By CandidFlakes, history, 4 months ago, In English

This is the problem. This is my WA attempt.

What I have observed is that a maximum of (n/2-1) maxima is possible for an array of size n, where n is even. So initially I created another array q such that the final array a = p+q , has all elements equal. Then I greedily tried to create (n/2-1) maximas by swapping the elements of array q( In the code it's ans array). I am willing to explain more if clarification is needed. Please just give me the hint, I want to solve it myself.

I will be thankful for any help!

Full text and comments »

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

By CandidFlakes, history, 15 months ago, In English

I was trying to solve this problem.

I went through it's tutorial and understood the following approach, Because the greatest common factor of b[i] and b[i+1] is a[i], and the greatest common factor of b[i+1] and b[i+2] is a[i+1], so b[i+1] is not only a multiple of a[i], but also a multiple of a[i+1], so when we construct the b array as b[i] = common multiple of a[i] and a[i+1].

But, in the tutorial they have taken Least common multiple. Please point me out the reason for taking the least common multiple because I am able to come up with some examples in which even if I don't take LCM(just take general common multiples) then also I get correct result.For example, consider a = {4,2}, then b could be {4,8,2}, here you can see b[2]=8 and b[2]!=lcm(a[1],a[2])=4.

What are the reasons which make it necessary to take LCM?
I will be thankful for any help!

Full text and comments »

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

By CandidFlakes, history, 15 months ago, In English

Please look at this submission. I am getting out of bounds error on line number 42. I have checked my code multiple times and also made sure that the vector 'a' is accessed up to i=a.size()-2 only, so that a[i+1] doesn't go out of bound.

Please help me identify my mistake.

I will be thankful for any help!

Full text and comments »

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

By CandidFlakes, history, 15 months ago, In English

I am trying to solve this question.

I have made use of unordered map to store the frequency of each doll size and then I count the sets by subtracting the difference between the consecutive frequency, If we are considering element a then we look for the frequency of element a-1, if the frequency of element a-1 is less than frequency of element a, then we increase the count of set by frequency(a)-frequency(a-1). It seems to be working fine but I am getting TLE in test case 28. Here, is my submission.

Why am I getting TLE? Please suggest changes to remove this TLE error.

I will be thankful for any help!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By CandidFlakes, history, 15 months ago, In English

I am trying to solve this question. I am facing difficulty in understanding the diagram of test case 2. As far as I have understood this question, the question asks to check whether is it possible to create 180 degree rotated image by changing colour of any possible combination of blocks exactly k times. If we look at the sample test case 2, it's image is

So, it's 180 degree rotated image should look like this

But, in the question the rotated image is give like this

I am unable to understand how is it possible? Please explain the logic behind it.

My next question is that suppose we have n=1. Then the answer should be "YES" if and only if k%2==0, because if we change the colour of the block odd times then the final colour of the only block will be changed (making it impossible to form 180 degree rotated image of the original block). But, I have made submission with this logic and the output was wrong answer. Please correct me where am I thinking wrong?

I will be thankful for any help!

Full text and comments »

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

By CandidFlakes, history, 15 months ago, In English

I am trying to solve this problem using DP.

I am able to observe that if I approach it using recursive backtracking, then there are 20^20(20*20*20..... 20 times for each garment) sub-problems, including overlapping sub-problems. Also, the total spending can be anything from 0 to 200(both inclusive).

How can I calculate the number of non-overlapping sub-problems for this problem?

I will be thankful for any help!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By CandidFlakes, history, 15 months ago, In English

I am trying to solve this question. Here is my submission. One of the test case which it is failing is  But, I think my answer which is 4 for this case is correct. Let me explain this, Starting from the beginning of sorted array l, suppose that everyone who says that the number of liars is less than or equal number of people left after excluding the person who says this and excluding the people who are truth speakers must be telling the truth.

So, in this case sorted array l is {0,1,1,2,2,4,7,8,9}. Hence, following the above ideology the number of truth speakers must be 0,1,1,2,2(total 5). Hence the number of liars is 9-5=4.

Where am I doing wrong? I will be thankful for any help!

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By CandidFlakes, history, 15 months ago, In English

I have been trying to solve this question.

After trying enough I read the tutorial but I am unable to understand it. I have attached the screen shot of the tutorial where I am facing problem below.  The tutorial says that for n>1 and n is odd, there exists no solution because, b_n = (a_1 + a_2 + ... + a_n)%n = (1+2+3+....+n)%n = (n*(n+1)/2)%n = 0 and b_1 is already 0, and there can't be two zeros in the array b. Hence, no solution for n>1 and n is odd.

But, my doubt is that why can't I apply the same logic with n>1 and even, the same way I can prove that b_n = 0 and b_1 already 0. Hence, no solution for n>1 and n is even. Please correct me. Where am I understanding it wrong? I will be thankful for any help.

Full text and comments »

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

By CandidFlakes, history, 16 months ago, In English

I was trying to solve this question. After trying enough i finally read the tutorial. Suppose the minimum number, is a[0]=600. Then we need to calculate how many elements of size 2*600-1=1999 can we form i.e. we simply need to divide each of the a[i] by 1999 and add each of them. But this code is giving wrong results.

#include <bits/stdc++.h>
using namespace std;

#define MULTI int _T; cin >> _T; while(_T--)

typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

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

    MULTI
    {
      int n;
      cin>>n;
      vector<int> a(n);
      long long sum = 0;
      for(int i=0;i<n;++i)
      {
        cin>>a[i];
      }
      for(int i = 0;i<n;++i)
      {
        sum+=(a[i])/(2*a[0]-1);
      }
      cout<<sum<<endl;
    }
}


I will be thankful for any help!

Full text and comments »

  • Vote: I like it
  • -6
  • Vote: I do not like it

By CandidFlakes, history, 16 months ago, In English

I solved this question. Here is my submission 214189574. Now suppose, we have number of days, m = 50000 and the total number of participants = 50000(maximum limit) and suppose that an answer exists. So, the answer would be something like a worst case series like 50000 participants for day 1, 49999 participants for day 2, 49998 participants for day 3,......, 1 participants for day 50000. Then, the total number of operations performed in total days = (50000/2)*(50000+1)=1250025000 operations and as a thumb rule I remember that modern computers can perform 10^8 operations/second. So, it should take 12.5 seconds but my code is running within the 2 second time constraint. Why is this happening? Why am I not getting a TLE error?

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it