Is there any simpler solution for B?

Videos out for E, F, G

E

F

G

We can do D in O(n) by observing two cases:

1. One of the biggest two numbers was choosen as x, and the other one is the sum of all smaller numbers.

2. Any smaller number was choosen for x and the biggest number is the sum of all other numbers.

Can someone point out the mistake in this? tried so many times but cant find it. the case is also not visible to debug. https://codeforces.me/contest/1512/submission/112547774 Verdict: wrong answer jury found answer, but participant did not (test case 88)

Is something wrong with the input validator for A? Perhaps I'm being dumb, but I can't find the error in my hacked solution, and it seems strange to me that the top twenty or so participants from the original ranklist have all been hacked. Moreover, a friend of mine reported that the test case 1 3 1 1 1 gives an "unsuccessful hacking attempt" verdict, when it should give invalid input, leading me to suspect that invalid test cases are being used to hack solutions. (UPD: I'm also hearing that the case 1 3 1 2 100 is successfully hacking solutions, which definitely shouldn't be happening, as there are more than two distinct elements in the array.)

//for(int i=0;i<=c;i++) {cout<<seive[i]<<" ";}cout<<endl;
if(c==1) ret(1);

//assert(c<
for(int i=2;i<=c;i++){
    map<ll,ll> mp;
    ll n=i;
    while(n!=1){
       if(seive[n]==1) {mp[n]++;break;}
       mp[seive[n]]++;
       n/=seive[n];
    }
    ll sum=1;
    for(auto x:mp){
       sum*=(((ll)pow(x.first,x.second+1)-1)/(x.first-1));
    }
    //deb(i,sum);
    if(sum==c) ret(i);
}

ret(-1);

why its giving TLE for problem G?

hold on can u declare an array of size 1e7 ?? wouldn't that give run time error

Time limits were too tight for problem G. Java and Python users are bound to get TLE, quite unfair.

Problem G with bigger constraint INVDIV

Problem C : https://ideone.com/dZeurz can someone please tell me a testcase where my solution fails i am not able to figure it out.

Can anybody provide knapsack dp solution for problem E;

Hi! Thanks for the editorial! Can anyone here check my submission for problem C and tell me in which test cases, my program failed? I am trying to find a corner case for so long.

If you don't have time to read my code, could you at least give me some counterexamples so I can test my code on them?

Thank you!

Here's my code: https://ideone.com/TZb6bR

Solution for C failing. Can someone help?

Why should we check whether the sum is below 2e9?

// the solution code
if (sum % 2 == 0 && sum <= 2'000'000'000 && have.find(sum / 2) != have.end()) {

I mean that b[i] has a constraint 1 <= b[i] <= 1e9. So if sum > 2e9 then sum / 2 > 1e9, as b[i] <= 1e9, we can't find sum / 2 in b[i]. Thus sum <= 2e9 should be redundant. But I got a wrong answer without it, and passed for adding it.

Appreciate for anyone who could explain it.

My WA submission: 112590439 My AC submission: 112590535

Can Someone help me with B , 112546789 I checked the test cases, and its still hard to decipher, perhaps someone has faced the same problem as me ?

 if (sum % 2 == 0 && sum <= 2'000'000'000 && have.find(sum / 2) != have.end())

Can someone please tell me what is the meaning of this condition?

Can someone explain how binary search solution of F works ?

Can anyone help me by sharing the code of O(n) complexity sieve of problem G!!

112599399 This is my submission of problem F. Please someone tell me whats wrong with this..

MikeMirzayanov

I submitted G solution and got TLE in test case 1, but during the contest test, 1 was passed.

After final testing, I submitted Previous G's solution and got Accepted.

Contest time code: https://codeforces.me/contest/1512/submission/112549540

After final testing: https://codeforces.me/contest/1512/submission/112601755

can you check it?

In G's code can someone explain this line plz:

s[i] = s[i] * d[i] + 1;

Like how are we calculating when two same prime divisors comes (for eg. 4=2*2) and why/how it works?

Where does this comes from. Is there some there theorem? Seems like some property like that of phi function but I can not figure out why.

Use the multiplicativity of the function d(n):

d(a⋅b)=d(a)⋅d(b) if gcd(a,b)=1.

If java coder use Arrays.sort() then We got TLE in problem D :) , Please solve this Supermagzzz

112527550

[Problem G] Same Code getting TLE and AC verdict. TLE Code — link AC Code — link Is it a joke?!

Can someone help me find the loophole in this approach for Problem C?

It keeps failing Test 2

112630518

how to calculate d(a*b) when a%b==0 and b is a prime by using linear sieve of Eratosthenes? Thanks.

Any proof for problem F ? why is it enough to calculate the number of days we should spend on a certain job a_i to get >= c and repeat this process taking the minimum for all jobs taking into consideration how many days will we stay in all the previous jobs ?

Hello, i am very new to codeforces(this was my first contest)

My code for problem C works perfectly well on my compiler, running it with valgrind gives no memory errors, but the diagnostics fail multiple test cases(which ran successfully on my compiler). I don't understand this!!

Can someone please help me?

This is my code:

Thank you

In problem E, can someone help me understand this:

 ans = min(ans, cur + max(0ll, c — bal + a[i] — 1) / a[i]);
        ll newDays = max(0ll, b[i] — bal + a[i] — 1) / a[i];
        cur += newDays + 1;
        bal += a[i] * newDays — b[i];

I got the idea of what this is trying to do but i can't understand how exactly the mathematical operations are working.

In problem G since O(NlogN) is sufficient can someone please tell why can't we do something of type

int fact[1000003];

for(int i=1;i<N;i++)
    for(int j=i;j<N;j+=i)
    fact[j]+=i;

and store the first occurences of every value and rest will be -1.

It seems like solution of D from editorial doesn't fit in time.

UPD Oh, I'm wrong

in problem G the multiplicativity of the function d(n) : d(a⋅b)=d(a)⋅d(b) if gcd(a,b)=1. is their any proof for it?

Why is E not doable with knapsack? https://codeforces.me/contest/1512/submission/113093207 Passed sample cases but WA on TC2

Can anyone please tell me why I am getting Wrong answer on test 2(test case 392) for problem 1512C (A-B Pallindrome). I tried lot but unable to find a case where it fails.

Here is my code :

#include <bits/stdc++.h>
using namespace std;
#define lli long long int 
#define ff first
#define ss second
#define endl '\n'
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int a,b;
        cin>>a>>b;
        string s;
        cin>>s;
        int n=s.size(); int flag=0;
        if((a+b)!=n)
        {
            cout<<"-1"<<endl;
            continue;
        }
        for(int i=0; i<(n/2); i++)
        {
            if(s[i]=='0')
            {
                if(s[n-1-i]=='0')
                a-=2;
                else if(s[i]=='1')
                {
                    flag++;
                    break;
                }
                else
                {
                    s[n-1-i]='0';
                    a-=2;
                }
            }
            if(s[i]=='1')
            {
                b-=2;
                if(s[n-1-i]=='?')
                {
                    s[n-1-i]='1'; 
                }
                if(s[n-1-i]=='0')
                {
                    flag++;
                    break;
                }
            }
            if(s[i]=='?')
            {
                if(s[n-1-i]=='0')
                {
                    s[i]='0';
                    a-=2;
                }
                else if(s[n-1-i]=='1')
                {
                    s[i]='1';
                    b-=2;
                }
            }
        }
        if((n&1)==1)
        {
            if(s[n/2]=='0')
            a--;
            else if(s[n/2]=='1')
            b--;
        }
        if((a<0)||(b<0)||(flag!=0))
        {
            cout<<"-1"<<endl;
            continue;
        }
        for(int i=0; i<n; i++)
        {
            if(s[i]=='?')
            {
                if(((n&1)==1)&&(i==n/2)) // for middle element if n is odd
                {
                    if((a&1)==1)
                    {
                        s[i]='0';
                        a--;
                    }
                    else
                    {
                        s[i]='1';
                        b--;
                    }
                }
                else if(a>1)
                {
                    s[i]='0';
                    s[n-1-i]='0';
                    a-=2;
                }
                else
                {
                    s[i]='1';
                    s[n-1-i]='1';
                    b-=2;
                }
            }
        }
        if((a<0)||(b<0))
        {
            cout<<"-1"<<endl;
            continue;
        }
        cout<<s<<endl;
    }
    return 0;
}

Can someone help and tell me why my solution is failing at test case 13 for prob D

https://codeforces.me/contest/1512/submission/115064448

G is such a great question!

#include<bits/stdc++.h>
using namespace std;
long long q, j, x, n, a[10000001], f[10000001];
main(){
	n=10000000;
	for (int i=1; i<=n; i++){
		for(j=i; j<=n; j+=i)a[j]+=i;
		if(a[i]<=n&&!f[a[i]])f[a[i]]=i;
	}
	cin>>q;
	while(q--){
	    cin>>x;
	    cout<<f[x]-(!f[x])<<endl;
	}
}

why such a brute force solution could solve problem G? 1e6*1e6=1e12,isn't it?

Can someone please explain me the solution for E (editorial one), I have been trying for a long time but unable to understand how this condition came :

(s — sum <= r — l + 1).

null

Could someone explain for me the logic behind this part in the editorial code for problem G, please?

      int j = i;
      s[i] = 1;
      while (j % d[i] == 0) {
        j /= d[i];
        s[i] = s[i] * d[i] + 1;
      }
      s[i] *= s[j];

I knew it was related to the multiplicativity of d(n) but I couldn't fully understand.

And this is

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

const int N = (int) 1e7 + 100;

long long s[N];
int d[N];
int ans[N];

int main() {
  fill(d, d + N, -1);
  d[1] = 1;
  for (int i = 2; i * i < N; i++) {
    if (d[i] == -1) {
      d[i] = i;
      for (int j = i * i; j < N; j += i) {
        if (d[j] == -1) {
          d[j] = i;
        }
      }
    }
  }
  s[1] = 1;
  for (int i = 2; i < N; i++) {
    if (d[i] == -1) {
      d[i] = i;
      s[i] = i + 1;
    } else {
      int j = i;
      s[i] = 1;
      while (j % d[i] == 0) {
        j /= d[i];
        s[i] = s[i] * d[i] + 1;
      }
      s[i] *= s[j];
    }
  }
  fill(ans, ans + N, -1);
  for (int i = N - 1; i > 0; i--) {
    if (s[i] < N) {
      ans[s[i]] = i;
    }
  }
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    int c;
    cin >> c;
    cout << ans[c] << endl;
  }
  return 0;
}

Thanks in advance!

Hello I am new to programming. Just finished "1512A — Spy Detected!". And now I read the tutorial. I am wondering is my way more efficient than the tutorial and code showed?

My idea was to assume the first element of array is spy. Then compare first element until you hit different element. In that moment we have two options first element is spy or the one we just discovered. if (a[0]!=a[n-1] && a[0]!=[n-2]) is simple way to find out who is spy.

I would like a feedback on this idea, is this good approach or not? **I wrote my code in C

I solved E using simpler approach in O(N)

if we have $$$s$$$ and $$$r-l+1=k$$$, so $$$\frac{(k)(k+1)}{2}$$$must be greater or equal to$$$s$$$

First we will subtract the k Values from s (we will Know later Why) $$$m=s-\frac{(k)(k+1)}{2}$$$ and if we try to distribute m oranges in k boxes, then every box will have m/k orange(floor division), and remainder will be r oranges, r<k

k Boxes: $$$b_1, b_2, b_3, b_4, ....b_{k-1}, b_k$$$

k Boxes: $$$\frac{m}{k},\frac{m}{k}, \frac{m}{k}, \frac{m}{k}, ....\frac{m}{k}, \frac{m}{k}$$$

so we will distribute remainder and each box will take 1 orange until we have 0 remainder(I know that there is some boxes that we won't take orange).we will distribute remainder from right to left

after we distribute remainder we will distribute k values that we subtracted in the first: 1, 2, 3, .....k;

example will clarify:

suppose that we have $$$r-l+1=k=4, s=13, m=13-\frac{(4)(4+1)}{2}=3$$$

we will make each box have $$$\frac{m}{k}=\frac{3}{4}=0$$$ and we have $$$r=3$$$

k Boxes: $$$b_1, b_2, b_3, b_4$$$

distribute quotiont: $$$0,\ 0,\ 0,\ 0$$$

distribute remainders: $$$0,\ 1,\ 1,\ 1$$$

distribute K values that we subtract in the first : $$$1,\ 2,\ 3,\ 4$$$

the summation of three rows above: $$$0+0+1,\ 0+1+2,\ 0+1+3,\ 0+1+4$$$

the summation of three rows above: $$$1,\ 3,\ 4,\ 5$$$ $$$= 13$$$

mysubmission