chokudai's blog

By chokudai, history, 10 months ago, In English

We will hold AtCoder Beginner Contest 169.

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

We are looking forward to your participation!

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

»
10 months ago, # |
  Vote: I like it -25 Vote: I do not like it

Editorial in english must also be posted as soon as in japanese.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Will it make any difference for you ??

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

    I'll post my solutions after the round ends.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      where will You post It ?

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

      Atcoder should pay you for this...

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

      In F, i take input of the interval as pairs and sorted the vector of pairs ,then find the median of that interval. Then do the necessary arithmetic as pointed out by Geothermal in here. This approrach fails in few test cases. What's wrong with my approach with F? Can anyone point out what am i missing? Link of my submission

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

        I believe that for the $$$n$$$ even case, you select the wrong two indices to form the median. Use $$$\frac{n-1}{2}$$$ and $$$\frac{n}{2}$$$, rather than $$$\frac{n}{2}$$$ and $$$\frac{n+1}{2}.$$$

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Your suggesstion did help to pass some test cases which were not passing earlier, but still few test cases are failing. Can't think of counter test case which could Hack my code.submission

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

            You don't need to sort vector of pairs. Simply sort individually.

            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I know from the editorial but the problem is that I don't understand why my solution is wrong?

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

                Your solution is wrong because you have sorted vector of pairs. Let these be pairs. 1 5 2 3 After sorting either they will remain same or 2 3 1 5 There is no possible way answer will be wrong in both the cases because for finding median array needs to be sorted.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Thanks, finally i contructed a test case where my code fails.

                  Test Case
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it

I hope it would be a great Contest

»
10 months ago, # |
Rev. 3   Vote: I like it +9 Vote: I do not like it

Excited that I will learn something new!

Update: Learned when to use double when not to use doubles and how to use doubles!

»
10 months ago, # |
  Vote: I like it -80 Vote: I do not like it

2nd and the 3rd question seems easy but is really tricky... i dont know on which cases my code is getting wa...can anyone please help

»
10 months ago, # |
Rev. 2   Vote: I like it -23 Vote: I do not like it

I'm so sad, it took me less time to D than it took me to do B and I haven't even done C. Everytime, I miss one of B-D. I'm cursed D:

  • »
    »
    10 months ago, # ^ |
      Vote: I like it -42 Vote: I do not like it

    I am missing something in B and getting WA again and again. Any hints please!

    • »
      »
      »
      10 months ago, # ^ |
      Rev. 2   Vote: I like it +19 Vote: I do not like it

      I'd love to help but I think that is not allowed (correct me if I'm wrong, I'm new to CP), will definitely help after the contest ends.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yes please man now

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it -10 Vote: I do not like it

          so you have to realize anytime the answer overflows out of limit(of data type) or become > 10^18. also if there is even 1 0, ans = 0. Code:

          include <bits/stdc++.h>

          using namespace std;

          typedef long long ll; typedef unsigned long long ull; typedef unsigned int uint; typedef long double ld;

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

          int n;
          cin >> n;
          ll t;
          ld ans = 1;
          for (int i = 0; i < n; i++)
          {
              cin >> t;
              if (ans != -1)
                 ans *= t;
              if (ans > 1000000000000000000 || ans < 0)
                 ans = -1;
              if (t == 0)
                 ans = 0;
          }
          cout << (ll)ans;
          return 0;
          

          }

          • »
            »
            »
            »
            »
            »
            10 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I forgot <0 :(

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

            I had the same code, only difference was that i used long long for 'ans' instead of long double and i got WA on one of the test cases .Changed to long double and got AC.Why?

            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Because long long data type could be overflowing from the multiplication of say 10^12 and 10^12.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      same here bro..

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it -9 Vote: I do not like it

      maybe create a function?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same here bro :(

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I solved problem C, and I don't even understand why it works.

»
10 months ago, # |
  Vote: I like it -9 Vote: I do not like it

i cry

»
10 months ago, # |
  Vote: I like it -9 Vote: I do not like it

w a n n a d i e.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Will a CE submission be calculated into the overall penalty?

I submitted two pieces of codes in the wrong language and will my overall penalty increase by 10 min?

»
10 months ago, # |
  Vote: I like it +6 Vote: I do not like it

How to solve F?

  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it +12 Vote: I do not like it

    For F, we can notice that ans is simply summation of i from 1 to n of (number of subsets of length i with sum s) * (2 ^ (n — i)).

    So now let dp[x][j] = summation of i from to n of (number of subsets of length n with sum x) * (2 ^ (n — i)) for the prefix 1..j

    Now, apply normal knapsack to combine answers, but since you're adding length 1 to your previous sums, we will have to divide them 2

    dp[x][j] = dp[x][j — 1] + (dp[x — a[j]][j — 1] * modinv(2))

    Answer is dp[s][n]

    You can even do it in O(n) space without needing the second dimension, like a normal knapsack, moving backward.

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

How to solve E!

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

    If n is odd, get the maximum median (sort array of B's and get its median) and the minimum median (sort array of A's and get it's median). The answer is max median — min median +1.

    If n is even, sort the arrays and do: max median = B[n/2] + B[(n/2)-1], min median = A[n/2] + A[(n/2)-1]. This way we avoid working with not integer numbers. So the answer is still max median — min median +1.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh god I was trying to use sweep type algorithm and check for each end point, but your answer is much much easier. Could not implement my approach but will try to refine it

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks for your approach but can you prove it!

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I am not able to understand why every value between min and max can be attained? Can you explain plz.

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

        From the minimum median, you just need to icrease the median by 1 to go to the next value (in case of n pair, increase first the biggest one and after the smaller one in the middle). You can do this until reach the maximum median.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Could you please give the proof of this approach?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks to 1358C, idea is very similar. You can observe minimum median will be median of array x and maximum medium will be median of array y.

    So values in the range median of array x to median of array y will be covered. Take care when size of array is even.

    Submission

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the second part, there are essentially two tricks for the problem 1) Sort the array. If the value at index i is 0, then we cannot return -1(no matter what). 2) Multiplying two extremely large numbers even when the data type is long long int will result in negative values, which will result in wrong answers. So, a*b>=c is equivalent to b>=(c/a)(take care of the border cases) Link to my code https://atcoder.jp/contests/abc169/submissions/13810433

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Okay, so in the 3rd question, I simply multiplied a and b, and applied the floor function for the product. Link to my code in C++ https://atcoder.jp/contests/abc169/submissions/13814577

»
10 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I just wonder how to solve B,C...

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i was getting TLE Second Question

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I'm guessing you may have tried to multiply all the numbers together in Python or a similar language? Since the intermediate products can have $$$O(N)$$$ digits, multiplying them takes $$$O(N)$$$ time, so this approach takes $$$O(N^2)$$$ time in the worst case.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you tell what's wrong here and why typecasting solution is not accepted in C++?

      ll a;
      double b; 
      cin >> a >> b;
      cout << (long long)(a*b) << "\n";
      
      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        use long double b;

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

        This will be WA because of precision error. Instead do (a*(b*100))/100 While calculating b*100, make sure you take round(b*100), otherwise things like 23.999999(due to double's precision) will be floored down to 23.

»
10 months ago, # |
  Vote: I like it +29 Vote: I do not like it

My solutions to all problems are at https://codeforces.com/blog/entry/78195.

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

    This is the solution of the second question.

    void solve() { cin>>n; vectorv(n); for(ll i=0;i<n;i++)cin>>v[i]; sort(v.begin(),v.end()); ll p=1,f=0; for(ll i=0;i<n;i++){ if(v[i]>=1000000000 and p>100000000){p=1000000000000000001;break;} if(v[i]>1000000000 and p>=1000000000){p=1000000000000000001;break;}

    p=(p*v[i]);
    //if(v[i])
    
    if(p>1000000000000000000)break;
    }
    if(p<=1000000000000000000)
    cout<<p;
    else cout<<"-1";

    }

    My code is giving WA on one case. Can you tell me why ?

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

Can someone please tell why this fails for C?

n = input().split()
i1 = int(n[0])
i2 = int(float(n[1]) * 100.0)
i = i1 * i2
print(i // 100)
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You need to round it, rather than taking its floor. For example float('2.51') = 2.509999999..., so int(float('2.51')*100) = 250.

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

In C, why is math.trunc(a*b) in python giving WA,but in CPP, this is accepted-

ll a;
long double b;
cin>>a>>b;
ll ans;
ans=a*b;
cout<<ans;
»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

nvm, got it

»
10 months ago, # |
  Vote: I like it -7 Vote: I do not like it

can anybody find mistake in my D solution.

#include<bits/stdc++.h>
using namespace std; 
bool ispower(int x,set<int> s)
{
	int f=0;
	int p=1;
	while(x%2==0)
	{
		p*=2;
		x=x/2;
		f=1;
	}
	if(x==1 && s.find(p)==s.end())return true;
	if(f==1)return false;
	int t=sqrt(x);
	for(int i=3;i<=t;i+=2)
	{
		int p=1;
		while(x%i==0)
		{
			f=1;
			x=x/i;
			p*=i;
		}
		if(f==1 && x==1 && s.find(p)==s.end())return true;
		if(f==1)return false;
	}
	return false;
}
bool isprime(int x)
{
	for(int i=2;i<=sqrt(x);i++)if(x%i==0)return false;
	return true;
}
int main()
{
	
	long long x;
	cin>>x;
	long long ans=0;
	int r=sqrt(x);
	set<int> s;
	bool seive[r+1];
	for(int i=2;i<=r;i++)seive[i]=true;
	for(int i=2;i<=r;i++)
	{
		if(seive[i])
		{
			for(int j=i;j<=r;j*=i)
			{
				if(x%j==0)
				{
					x=x/j;
					ans++;
					s.insert(j);
				}
			}
			for(int j=2*i;j<=r;j+=i)
			{
				seive[j]=false;
			}
		}
	}
	if(x>=2 && s.find(x)==s.end() && (ispower(x,s) || isprime(x)))ans++;
	cout<<ans;
	return 0;
}
  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You are not looking for primes greater than √x.

    Try for 4000000028.

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

Any care to explain why is this wrong for problem C ?


#define int long long void solve() { int a,b; double c; cin >> a; cin >> c; b = (c*100); int res = (a*b); res/=100; cout << res; }

It gives WA for random_12.txt

Edit : I always define int as long long in my template.

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

    I'd guess the issue is double precision. Precision is an issue in general, but in particular, the answer here can be up to $$$10^{16}$$$, which is too large for the number of precision bits in a double.

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But here multiplications are in long long, the only place where precision could affect is assigning "b = c*100".

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

        Ah, right; my bad--I misread the solution. The issue is precision in that conversion: I changed b = (c*100) to b = (c*100+0.5) and the solution was accepted.

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Thanks for the solution.

          Any advice on how to avoid these errors in future ?

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

            You need to understand why this error happened. The reason is that if you read a number as a double (lets say 10) the double can be represented as 9.9999... or maybe 10.000...01 (both of which are 10 indeed woth a very small error intrinsic to the floating point representation)) but in c++ if you convert them to an integer it truncates the value automaticaly, so the result could be either 9 or 10. The solution would be doing the comversion as x_int = round(x_double) or x_int = x_double + 0.5.

            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Thank you very much. This is what I was looking for.

              Being skeptic, if x_double is 4.50 is there any chance I will get 5 instead 4 using your suggested solution ?

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

                Yes, it would be a problem. But you did not quite get how to use what I said. If a number has at most x decimal digits, you may want to multiply it to 10^x and convert to integer, so you do int_x = 10^x*double_x+0.5 (but if double_x has more the x digits this may not work correctly)

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Now I got it. Thanks for the help.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  10 months ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  but why is this a problem as it is already given in the question that the B is a number with two digits after the decimal point,hence it is always fixed that we are not losing any value for the above solution after multiplying by 100. So why is this so???

            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
              Rev. 3   Vote: I like it -8 Vote: I do not like it

              deeper explaination Essentially, there's some natural imprecision in the way decimal datatypes are stored in C++ (and in most other languages). C++ stores decimals, like all numbers, in binary, rather than base 10, and in binary, numbers like 0.1, 1.6, and 3.4 are actually repeating decimals. Because of that, when C++ tries to store that kind of number, it will actually store a value that's very close, but slightly higher or slightly lower.

              The problem here, though, is that if you get a value slightly lower than, say, 1.01, then when you multiply it by 100, the result will be slightly lower than 101, and will thus get rounded down to 100, giving you an incorrect answer. To deal with this, we add some value (I used 0.5, but it could be much smaller and still work) to ensure that our result will be larger than 101, rather than smaller. i mean to say in easy words there is no like 3.33 that is actually 3.3333333.....so this is making the answer change .Do comment for any queries the above explanation shows why round function works and floor or ciel function don't credits Geothermal

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

            Do not assume double arithmetic is correct. Often it is not, the result is only near to the mathematic correct result.

            Deal with that or use integers.

            • »
              »
              »
              »
              »
              »
              »
              10 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              I didn't, that's why I converted double to int and then calculated the result.

              I am yet to find any solution which always works for doubles.

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

              I disagree with that. You just need to unserstand how big the error can be in the worst case, often the error is smaller than 1, so you can often get the integer part right for sure if the constraints allow that

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

                That is the strategy I would call "deal with it".

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use long double instead of double

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does long double over double changes anything ? considering value of is B < 10, having 2 digits are decimal point.

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

        I used this formula: answer = floor( a * long double(b) )

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yes, that works well. I used the similar thing to get AC later. Thanks for the answer.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Range of input is too big which will have precision loss. Try using long long and long double

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Why does long double over double changes anything ? considering value of is B < 10, having 2 digits are decimal point.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What is the approach for problem E — Count Median ??

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the fourth question, I simply used the Sieve of Eratosthenes to get the prime numbers less than 1e6, after that I iterate from 2 to the largest prime less than 1e6, and simply code out for the number of ways the number can be broken down! Just be careful when we multiply two numbers of digits 5 and 6! Link to my code- https://atcoder.jp/contests/abc169/submissions/13855795

»
10 months ago, # |
  Vote: I like it -24 Vote: I do not like it

what is my mistake in my code???

include

using namespace std;

int multiply(int array[], int N) { int pro = 1; for (int i = 0; i < N; i++) t = t * array[i]; return t; } int main() { int N; cin>>N; int array[N]; for(int i=0; i<N; i++) { cin>>array[i]; } multiply(array,N); if(array == 0) { cout<<0<<endl; } else if( (multiply(array,N)) > (1000*1000*1000*1000*1000*1000)) {

cout<< -1 <<endl;}
   else
   {
       cout<<multiply(array,N)<<endl;
   }

  return 0;

}

»
10 months ago, # |
  Vote: I like it -32 Vote: I do not like it

what is my mistake in my code for B???

include

using namespace std;

int multiply(int array[], int N) { int pro = 1; for (int i = 0; i < N; i++) t = t * array[i]; return t; } int main() { int N; cin>>N; int array[N]; for(int i=0; i<N; i++) { cin>>array[i]; } multiply(array,N); if(array == 0) { cout<<0<<endl; } else if( (multiply(array,N)) > (1000*1000*1000*1000*1000*1000)) {

cout<< -1 <<endl;}
   else
   {
       cout<<multiply(array,N)<<endl;
   }

  return 0;

}

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it
»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it
  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    store 1e18 in a variable and then do the rest. I think that will do the job!!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve c? I multiplied a*b and took floor(a*b). What's wrong? submission

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

    See, Double can store large values but on the cost of significant digits,in Long you will get more significant digits before decimal point but then you can not store digits after the decimal points

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      But I also tried (long)(b*100)*a/100. What's wrong with this?

»
10 months ago, # |
  Vote: I like it +1 Vote: I do not like it
»
10 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Please someone help me out with Problem C ....... My Submission

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Precision issue. Do long long x = round(b*100) and AC

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

i thought C would give precision error if i use long double. i tried almost 6/7 types of approach(wrong) without using floating point. about 3 minutes before the contest would end, i simply tried using long double and output it with type casting to long long and it worked! wow -_-

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats wrong wit C

import java.math.BigDecimal; import java.util.Scanner;

public class Main {

public static void main(String args[])
{
    Scanner sc=new Scanner(System.in);
    long a=sc.nextLong();
    long b=(long)(sc.nextDouble()*100);
    long ans=(a*b)/100;
    System.out.println(ans);

}
  • »
    »
    10 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My Simple and short Solution for C (Used Bigdecimal Library in JAVA)

    void solve() throws Exception{
    	BigDecimal bd1 = new BigDecimal(ns());
    	BigDecimal bd2 = new BigDecimal(ns());
    	bd1 = bd1.multiply(bd2); 
    	pn(bd1.toString().split("\\.")[0]);
     
    }
    
    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You can do it this way but still whats wrong in my code.

      • »
        »
        »
        »
        10 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Test it out where the floating point value is stuff like 1.12, 1.13, etc (if Java handles floating point the same as python those two cases should show you the issue). Floating point error in this line is your issue:

        long b=(long)(sc.nextDouble()*100);

»
10 months ago, # |
Rev. 7   Vote: I like it +19 Vote: I do not like it

I usually get one hit on both Codeforces and Atcoder, but this time seems horrible xD

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Whats wrong in D

import java.util.Scanner;

public class Main {

public static void main(String args[])
{
    Scanner sc=new Scanner(System.in);
   long n=sc.nextLong();
   long copyn=n;
   long x=(long)Math.sqrt(n);
   long copyx=x;
   long ans=0;
   for(int i=2;i<=x;i++)
   {
       int count=1;
       while(n%((Math.pow(i,count)))==0)
       {

           n= (long) (n/Math.pow(i,count));
           count++;
           ans++;
       }

       while(n%(Math.pow(i,count))==0)
       {
           n= (long) (n/Math.pow(i,count));
       }
   }

   if(copyn==1)
   {
       System.out.println(0);
   }
   else

   if(n>x)
   {
       System.out.println(1+ans);
   }
   else
   {
       System.out.println(ans);
   }

}

}

»
10 months ago, # |
  Vote: I like it -15 Vote: I do not like it

What is the problem with this solution of C?Can someone help?

include<bits/stdc++.h>

using namespace std; typedef long long ll;

define mod 1000000007

int main() { ll a; float b1; cin>>a>>b1;
b1=b1*100; ll b=b1; ll s=a*b; s=s/100; printf("%lld\n",s); }

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Maybe precision issues? Try doing b1 = round(b1*100)

    • »
      »
      »
      10 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Well, if the input is 1.890000 then it becomes 189.000000 and then 189 by typecast. There shouldn't be any problem.

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

        You dont understand how it works. The number may be interpreted as 188.99999999... which is the same as 189.00000 but when you cast to int in c++ the value is truncated, it sort of an undefined behaviour, the value may be casted to 188 or 189, use the round to avoid that.

        • »
          »
          »
          »
          »
          10 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, I got it. That was the problem actually. Thanks a lot.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    awesome one ! me i just define b as long double and took long long c=a*b and then i cout c and it works also as simple as that

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody help me why this submission for D fails at 18th testcase? submission

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

can some one explain to me why my 1st test case not working of B question

(https://atcoder.jp/contests/abc169/submissions/13891717)

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have a similar problem too: https://atcoder.jp/contests/abc169/submissions/13892048

    What is more, the first test case (hand_01.txt) on AtCoder's Dropbox looks like this:

    Input: 2 4294967296 4294967296

    Output: -1

    I compiled my program locally using different compilers and there was nothing wrong with my code ://

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://atcoder.jp/contests/abc169/submissions/13900202 [WA] https://atcoder.jp/contests/abc169/submissions/13900438 [AC]

Both are identical solutions for problem B of AtCoder Beginner Contest 169. Does anyone knows why this happen?

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I got a beautiful solution for F: the answer is just the coefficient of x^s in polynominal (2 + x^a1)(2 + x^a2)...(2 + x^an) here '^' is for power. we can just ignore higher order coefficient than x^s.

https://atcoder.jp/contests/abc169/submissions/13847100

please ignore unremoved code for problem D, E.

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

In B:
For the statement: if(inp[i] <= 1e18/ans) I got WA. But when i wrote : if(inp[i] <= 1000000000000000000/ans) I got AC. Is there any differences between 1e18 and 1000000000000000000?? Otherwise what is the reason??

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

    You should cast 1e18 to long long otherwise the result of the division becomes a float.

»
10 months ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

In editorial there is a typo in problem D English version.

Wrong:$$$O(N)$$$

Correct:$$$O(sqrt(N))$$$

Capture.png

»
10 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Can AnyBody please tell how can i reduce the submission time of my solution to the problem F?

https://atcoder.jp/contests/abc169/submissions/13920879

I have seen people getting AC in less than 100ms while mine is giving AC in 1000 ms.

thanks in advance. :).

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In the editorial of problem F it says:

dp[i][j] = When the choices for the first i options is already determined, the number of combination such that the sum of ak for each k that the first option was chosen is equal to j

What does it even mean?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think it just means, dp[i][j] refers to how many ways we can reach sum equal to j using i elements

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

Can anyone help me debug my solution? I get TLE on 6-7 test cases, no idea why. Thank you!

#include <iostream>
#include <vector>
using namespace std;

int solve(long long n) {
    if (n == 1) {
        return 0;
    }
    vector<int> f;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            f.push_back(i);
            n /= i;
        }
    }
    if (n > 1) f.push_back(n);

    int ans = 0;
    int i = 0;
    while (i < f.size()) {
        int j = i + 1;
        while (j < f.size() && f.at(j) == f.at(i)) j++;
        int count = j - i;
        i = j;
        int sum = 0;
        for (int x = 1; count >= sum + x; x++, ans++) sum += x;
    }
    return ans;
}

int main() {
    long long n;
    cin >> n;
    cout << solve(n) << endl;
}
  • »
    »
    10 months ago, # ^ |
      Vote: I like it +4 Vote: I do not like it
    for (int i = 2; i * i <= n; i++) 
    

    i * i can overflow since n goes upto $$$10^{12}$$$
    Use long long instead.

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

      T_T I don't know how I missed that. Thanks!

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is my wrong with my code in problem-c? https://atcoder.jp/contests/abc169/submissions/13926562

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For problem D, Maybe this sounds stupid, But can someone please explain why is it optimal to compute for each prime and its powers first, then similarly with next prime and its powers, and so on instead of going from 2 onwards ?

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    same thing I was also wondering .

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide any proof for problem-E for both odd and even case.

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If we increase one value by $$$1$$$ and leave the rest as it is, then median can stay the same or increase by $$$1$$$ for odd $$$n$$$ and stay the same or increase by \frac{1}{2}

    Unable to parse markup [type=CF_MATHJAX]

    is even. Now let's set $$$X_i = A_i$$$ and increase all of them one by one till we reach $$$X_i = B_i$$$. At first median equals median of $$$A_i$$$, and after all operations equals median of $$$B_i$$$ and at each step it will either stay the same or increase by $$$1$$$ in case of odd $$$n$$$ and by $$$\frac 12$$$ for even $$$n$$$ thus will reach all integers for odd $$$n$$$ and halfintegers for even $$$n$$$ from range $$$[\text{median}(A_1, \ldots, A_n), \text{median}(B_1, \ldots, B_n)]$$$.

    To prove we can't reach any other value we only need to see, that median of an integer sequence is an integer for odd $$$n$$$ and a half integer for even $$$n$$$ and see that we can't reach a value outside that segment, but this is straightforward conclusion from the fact, that if all values increase or stay the same, then the median can only increase or stay the same as well.

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

For problem F, it says f(T) is the number of different non-empty subsets satisfying the given condition. Now consider the first sample. It was given that f(T) is 2 ({1,2}, {3}). By the definition, shouldn't f(T) be 3 ({1,2}, {3}, {1,3}) ? Unless there is a translation issue.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

If anyone is still stuck at D here is a Solution

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am Facing problems in the C . No matter what I submit , I am shown wrong answer in 6/22 cases . I am not understanding where is the error or fault exists in that code .. If anyone knows , please give me the solution . My code is given below ::::

include<stdio.h>

int main() { long long int a,pro1; double b,pro=1.0; scanf("%lld %lf",&a,&b); b=b*100; pro=(a*b); pro1=(long long int)(pro/100); printf("%lld",pro1); return 0; }

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For big values of $$$a$$$ the variable $$$pro$$$ has simply not enough bits to store the exact result of $$$a*b$$$. In this case the double type truncates bits, which results in pro1 beeing some other value than the mathematecally expected one.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone help me where I'm going wrong in problem D, I'm getting hand_22 as the only test case as WA. Here is my code https://atcoder.jp/contests/abc169/submissions/14102528 Thanks

  • »
    »
    10 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ull i=1; You have this just before the for loop, but it should be inside it, so that the while loop always starts at 1. Since all the primefactors in mp are independent of each other.

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

      Thanks a lot for reading my code and identifying my mistake.

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me why I am getting runtime error in this solution https://atcoder.jp/contests/abc169/submissions/14630442

»
10 months ago, # |
  Vote: I like it 0 Vote: I do not like it

//**B**

include<bits/stdc++.h>

using namespace std; typedef long long int ll; typedef long double ld; int main() { int t; cin>>t; if(t==0)return cout<<0,0; long double s = 1; vector vec(t); for(int i=0; i<t; cin>>vec[i++]); sort(vec.begin(),vec.end()); for(auto &it: vec){ if(it==0)return cout<<0,0; if(s>1e18/it)return cout<<-1,0; s *= it; } cout<<(ll)(s)<<'\n'; }