#	User	Rating
1	Benq	3747
2	tourist	3656
3	Miracle03	3587
4	ksun48	3530
5	Radewoosh	3511
6	maroonrk	3434
7	jiangly	3432
8	Um_nik	3422
9	ecnerwala	3400
10	peehs_moorhsum	3384

#	User	Contrib.
1	1-gon	214
2	Um_nik	191
3	sus	183
4	Errichto	180
5	awoo	179
6	tourist	178
7	-is-this-fft-	172
8	Radewoosh	171
9	maroonrk	169
9	Ashishgup	169

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    int n;
    cin >> n;
    vector<int> v(n);
    for (int &e : v) {
        cin >> e;
    }
    vector<int> a = v;
    sort(a.begin(), a.end());
    for (int i = 0; i < n; i++) {
        if (v[i] != a[1]) {
            cout << i + 1 << "\n";
        }
    }
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
    return 0;
}

1512B - Almost Rectangle

Author: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

#define forn(i, n) for (int i = 0; i < int(n); i++)

int main() {    
    int t;
    cin >> t;
    forn(tt, t) {
        int n;
        cin >> n;
        vector<string> f(n);
        vector<pair<int,int>> p;
        forn(i, n) {
            cin >> f[i];
            forn(j, n)
                if (f[i][j] == '*')
                    p.push_back({i, j});
        }

        p.push_back(p[0]);
        p.push_back(p[1]);
        if (p[0].first == p[1].first) {
            p[2].first = (p[2].first + 1) % n;
            p[3].first = (p[3].first + 1) % n;
        } else if (p[0].second == p[1].second) {
            p[2].second = (p[2].second + 1) % n;
            p[3].second = (p[3].second + 1) % n;
        } else
            swap(p[2].first, p[3].first);

        f[p[2].first][p[2].second] = '*';
        f[p[3].first][p[3].second] = '*';
        forn(i, n)
            cout << f[i] << endl;
    }
}

1512C - A-B Palindrome

Author: MikeMirzayanov

Tutorial

Solution

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

void no() {
  cout << "-1" << endl;
}

void solve() {
  int a, b;
  cin >> a >> b;
  string s;
  cin >> s;
  for (int times = 0; times < 2; times++) {
    for (int i = 0; i < (int) s.size(); i++) {
      int j = (int) s.size() - i - 1;
      if (s[i] != '?') {
        if (s[j] == '?') {
          s[j] = s[i];
        } else if (s[i] != s[j]) {
          no();
          return;
        }
      }
    }
    reverse(s.begin(), s.end());
  }
  a -= count(s.begin(), s.end(), '0');
  b -= count(s.begin(), s.end(), '1');
  int ques = count(s.begin(), s.end(), '?');
  bool emptyMid = (s.size() % 2 == 1 && s[s.size() / 2] == '?');
  if (a < 0 || b < 0 || a + b != ques || (emptyMid && a % 2 == 0 && b % 2 == 0)) {
    no();
    return;
  }
  if (a % 2 == 1 || b % 2 == 1) {
    int i = s.size() / 2;
    if (s[i] != '?') {
      no();
      return;
    }
    s[i] = (a % 2 == 1 ? '0' : '1');
    if (a % 2 == 1) {
      a--;
    } else {
      b--;
    }
  }
  if (a % 2 == 1 || b % 2 == 1) {
    no();
    return;
  }
  for (int i = 0; i < (int) s.size(); i++) {
    if (s[i] == '?') {
      int j = s.size() - i - 1;
      if (a > 0) {
        a -= 2;
        s[i] = s[j] = '0';
      } else {
        b -= 2;
        s[i] = s[j] = '1';
      }
    }
  }
  cout << s << endl;
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

1512D - Corrupted Array

Author: MikeMirzayanov

Tutorial

Solution

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

void no() {
  cout << "-1" << endl;
}

void solve() {
  int n;
  cin >> n;
  vector<int> b(n + 2);
  for (int &x : b) {
    cin >> x;
  }

  multiset<int> have(b.begin(), b.end());
  long long sum = accumulate(b.begin(), b.end(), 0LL);
  for (int x : b) {
    have.erase(have.find(x));
    sum -= x;
    if (sum % 2 == 0 && sum <= 2'000'000'000 && have.find(sum / 2) != have.end()) {
      have.erase(have.find(sum / 2));
      for (int y : have) {
        cout << y << " ";
      }
      cout << endl;
      return;
    }
    sum += x;
    have.insert(x);
  }
  no();
}

int main() {
  int tests;
  cin >> tests;
  while (tests-- > 0) {
    solve();
  }
  return 0;
}

1512E - Permutation by Sum

Author: MikeMirzayanov

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

void solve() {
    int n, l, r, s;
    cin >> n >> l >> r >> s;
    l--; r--;
    for (int first = 1; first + (r - l) <= n; first++) {
        int sum = 0;
        for (int i = l; i <= r; i++) {
            sum += first + (i - l);
        }
        if (sum <= s && s - sum <= r - l + 1) {
            int needAdd = r - (s - sum) + 1;
            vector<int> ans(n);
            set<int> non_blocked;
            for (int i = 1; i <= n; i++) {
                non_blocked.insert(i);
            }
            for (int i = l; i <= r; i++) {
                ans[i] = first + (i - l);
                if (i >= needAdd) {
                    ans[i]++;
                }
                non_blocked.erase(ans[i]);
            }
            if (ans[r] > n) {
                continue;
            }
            non_blocked.erase(ans[r]);
            for (int i = 0; i < l; i++) {
                ans[i] = *non_blocked.begin();
                non_blocked.erase(non_blocked.begin());
            }
            for (int i = r + 1; i < n; i++) {
                ans[i] = *non_blocked.begin();
                non_blocked.erase(non_blocked.begin());
            }
            for (int i : ans) {
                cout << i << " ";
            }
            cout << "\n";
            return;
        }
    }
    cout << "-1\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
}

1512F - Education

Author: sodafago

Tutorial

Solution

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
    int n, c;
    cin >> n >> c;
    vector<int> a(n);
    vector<int> b(n - 1);
    for (int &e : a) {
        cin >> e;
    }
    for (int &e : b) {
        cin >> e;
    }
    b.push_back(0);
    ll ans = 1e18;
    ll cur = 0;
    ll bal = 0;
    for (int i = 0; i < n; i++) {
        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];
    }
    cout << ans << "\n";
}

int main() {
    int n;
    cin >> n;
    while (n--) {
        solve();
    }
    return 0;
}

1512G - Short Task

Author: MikeMirzayanov

Tutorial

Solution

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

Comments (187)

Write comment?

ProportionalConstant

5 months ago, # |

← Rev. 2 →

Is there any simpler solution for B?

→ Reply

jineshparakh

5 months ago, # ^ |

For both the *'s in the matrix at least one of these 3 conditions will hold:
1. They will form a horizontal edge(both having the same row)
2. They will form a vertical edge(both having the same column)
3. They will form a diagonal

After that, a rectangle can be made using some basic casework.
You can refer to My Submission

lawarganayra

I did that , but got wrong answer, could you please help! 112540024

bhavyaganatra

I think error is in below line:

poin1 = make_pair(0,first_x);

It should be like this: poin1 = make_pair(first_x,0);

Here is the test case in which your code will fail:

1
3
...
..*
..*

lostkevin

Why is my array subscript wrong from 1, instead of taking module, it is in the form of n-x-1

sumj25

include

using namespace std; int main(){ int t; cin>>t; while(t--) { int n,i,j; cin>>n; string A[n][n],B[n][n]; int C[2],D[2],k=0; for(i=0;i<n;i++) { for(j=0;j<n;j++) { cin>>A[i][j]; if(A[i][j]=="*") { C[k]=i; D[k]=j; k++; } } }

if(C[0]==C[1])
    {

        int r=(C[0]+1)%n;
        int p=(C[1]+1)%n;
       A[r][C[0]]="*";
       A[p][C[1]]="*";
    }

if(D[0]==D[1]) { int r=(D[0]+1)%n; int p=(D[1]+1)%n; A[D[0]][r]="*";

A[D[1]][p]="*";
    }
    else{
       A[C[0]][D[1]]="*";
         A[C[1]][D[0]]="*";
    }


      for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
            cout<<A[i][j];

            cout<<endl;
    }
}

}

can anyone tell me what is i'm doing wrong because i'm getting runtime error.

drunk_phoenix

let's say the '*' are at position ( x1 , y1 ) ans ( x2 , y2 ) respectively if they're on same row or same column (i.e x1==x2 or y1==y2) then print the asterisks in a adjacent row or column of this column else print them at position (x1 , y2 ) and ( x2 , y1 ) ( in this way they'll form a rectangle with sides parallel to the original matrix ) ;

starkspi

Can someone check my problem C submission and tell the test case I am failing because I tried very hard but not able to figure it out even jury is not showing the test case I failed. Kindly help me I am an absolute beginner your support means a lot to me

sikandarjun

Please post your code so that we can debug it...

FiREWARRiOR

https://codeforces.com/contest/1512/submission/112922007

here is my solution for C. I think I have done the same thing but it's not working

aditya_01

you can do stress testing between your code and solution code

anipnwr

how can you generate those strings randomly??

hogrider

B problem


for testis in range(int(input())):
    n = int(input())
    m = []
    x = -1
    y = -1
    a = []
    for i in range(n):
        l = input()
        m.append(l)
    for i in range(n):
        for j in range(n):
            if m[i][j]=='*':
                a.append([i,j])
  #  print(a)
    x1 = a[0][0]
    y1 = a[0][1]
    x2 = a[1][0]
    y2 = a[1][1]
   # print(x1,y1,x2,y2)
    if x1==x2:
        if x1>0:
            x3 =  x1 -1
            x4 =  x1 -1
            y3 = y1
            y4 = y2
        else:
            x3 = x1 + 1
            x4 = x1 + 1
            y3 = y1
            y4 = y2
    elif y1 == y2:
        if y1>0:
            y3= y1 -1
            y4 = y2 -1
            x3 = x1
            x4 = x2
        else:
            y3 = y1 + 1
            y4 = y2 + 1
            x3 = x1
            x4 = x2
    else:
        x3 = x1
        y3 = y2
        x4 = x2
        y4 = y1
    for i in range(n):
        s = ""
        for j in range(n):
            if i==x1 and j==y1:
                s = s + '*'
            elif i==x2 and j==y2:
                s = s + '*'
            elif i==x3 and j ==y3:
                s = s + '*'
            elif i==x4 and j==y4:
                s = s + '*'
            else:
                s = s + '.'
        print(s)

muditPRO

Don't know if you will found this simpler but you can do like note the two cordinates which are star and if they are not in same row or column simply exchange the x cordinate and y cordinate resp to find the other two cordinates and if they are in same row or column simple increase the cordinates which are same suppose in same row incrment the row cordinate by 1 modulo n.

imtiazzarif

112627220 check mine hope you will get it

sumitkushwaha1999

find the rows columns of given stars as r1,c1, and r2,c2. if r1==r2 then using boundary conditions increment or decrement. do the same thing for c1 and c2. then new stars indexes will be r1c2 and r2c1. https://codeforces.com/contest/1512/submission/112609651

^ | my submission.

Ajayjangid511

Can do simply this way... ~~~~~ void Solve() { int n; cin >> n; char mat[n][n]; int row[2], col[2]; int m = 0; forn(i, 0, n) { forn(j, 0, n) { char x; cin >> x; mat[i][j] = x; if (x == '*') { row[m] = i; col[m] = j; m++; } } } if (row[0] == row[1]) { mat[(row[0] + 1) % n][col[0]] = '*'; mat[(row[0] + 1) % n][col[1]] = '*'; } else if (col[0] == col[1]) { mat[row[0]][(col[0] + 1) % n] = '*'; mat[row[1]][(col[0] + 1) % n] = '*'; } else { mat[row[0]][col[1]] = '*'; mat[row[1]][col[0]] = '*'; } forn(i, 0, n) { forn(j, 0, n) { cout << mat[i][j]; } cout << endl; } } ~~~~~

djv007

114219070

the problems were really educational , and I guess codeforces in now competing with at atcoder regarding how fast can they publish editorial XD ( at least for beginner/div3 rounds ) . time to upsolve .

stefdasca

+26

Videos out for E, F, G

spookywooky

+21

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

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

Adi_Max

i tried that but some test cases r failed ,please let me know my mistakes ,my solution 112546189

lazy_and_slow

you took everything long long except the sum variable lol 112575126

wysoserious

Hi, I did the same, however got wrong answer. I apologize if it's too much to ask, but can you please review my code? I compared your code with mine, and it appears I did all the necessary things and yet code fails on the second test case. My submission — 112881623

It is testcase 1 of second testcase, you answer -1 where the answer is 1:

1
1
1 1 1

Letscode_sundar

4 months ago, # ^ |

can you please find the mistake in this 116030741

i am following the same method that you mentioned.

parthsharma6321

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.com/contest/1512/submission/112547774 Verdict: wrong answer jury found answer, but participant did not (test case 88)

prajjwal007

1
8 2
?????0000?
correct ans is 1000000001

Thank you!

Dwyte

I got that one correct, but still getting wrong answer on test case 2, can you check mine as well? Thank you.

https://codeforces.com/contest/1512/submission/112930573

Geothermal

← Rev. 4 →

+67

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.)

+41

After being hacked and dropping to 344th place, it's nice to be back on top B)

code_warrior

How did so many good coders like you got hacked on A?

See my post above--the validator is incorrect, and the inputs used for hacking do not satisfy the constraints of the problem. I'm assuming a fix will be issued sometime later today and everyone's solutions will be restored.

Mong_Mang

Can you please tell all the extensions name on the last 3 rows? How can I get those extension. Please reply.

kaiyu

+11

Here is the link to the extension : https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn?hl=en

swapnil159

Can you tell us which extension are you using to see the rating change on right?? UPD: Sorry for asking again, just saw the comment above.

chilly_willy

+39

just git gud lmao

MikeMirzayanov

+13

Yep, sorry for it. It is fixed now: https://codeforces.com/blog/entry/89476#comment-778860

rini_19

s = ???11? a = 2 b = 4

In this test case '?' at index 1 & 2 should be converted to '1' first and then '?' at index 0 and 5 should be dealt.

btme

← Rev. 3 →

CODE

ll c; cin>>c;

//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?

burak

Do not use pow, I do not know your intended solution but pow can result in both precision error and linear calculation (which makes your whole algorithm $$$O(n\;maxB)$$$ if you iterate through $$$n$$$ values and use pow to calculate some power $$$a^b$$$ in $$$O(b)$$$ time instead of $$$O(log\;b)$$$ time with binary exponentiation.)

no its not working!!!!!!!!!!

AB.devil

Well, it should TLE. For every query, you are looping from 2 to c to find appropriate n.
Instead, you can for all values of c store the minimum n and then answer queries in constant time.

Darshan_Bhangale

Use Binary Exponentiation to calculate the value of a raised to b. pow function has a time complexity of O(n). while Binary Exponentiation has a time complexity of O(log(n)).

harsha99

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

You can because it is roughly ~40MB (in case of ints) and in CF the memory limit for most of the problems is 256MB.

vineet16

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

AdityaGupta1326_iitr

time limits were too tight for G bcz bruteforce with slight optimization gives AC in c++ . submission link

Mr.HITMAN

Correct solutions of Problem A are getting Hacked because of wrong test case input..

Please disqualify any such hacks..

for A..

input [which is wrong]

1
7
1 1 1 1 1 2 2

It shows successfull hacking attempt

__algebra__

Problem G with bigger constraint INVDIV

dhritishman22

Div 3 contests were great when Vohuh was a problem setter.

RohitS.Singh

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.

thank you for helping ..

try to seperate if(s[i]='?'&&s[n-i-1]='?') case from rest of the other case and do in separate loop

thank you again!! got the error.

jaimin027

Thankyou so much brother!

not_nubskr

My code passes this and a=9 and b=6 one as well but still failing: https://codeforces.com/contest/1512/submission/112927803

Coding_2_OP

What's wrong in the 112530668 code. Is any case I am missing?. Its showing wrong on testcase 42. I think all the cases are taken. Any help will be highly appreciable. Thanks in advance.

yonghu369

1 9 6 ?????????0?????

//ans //101010000010101

Zealotrahl

Can anybody provide knapsack dp solution for problem E;

jpratik15

It will give TLE , I guess

amar277

Here is my submission Take a look at this https://codeforces.com/contest/1512/submission/112546632

dedsec_29

Can you explain your dp state, what does dp[i][j] denote?

i means no. of elements which add upto j i.e. sum

Can you please explain your approach in brief? I am unable to understand.
Thank you in advance.

ChemicalWarfare

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?

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

faraz16iqbal

Solution for C failing. Can someone help?

YareYare

Try this test

Test

1
9 6
??????0??0????1

Answer isn't -1

is there any way i could see test case 88 in problem C .

yistarostin

WA4 on D for std::accumulate(.., 0) instead of 0LL I thought C++ is a bit smarter and can convert 0 to 0LL while operating with vector<ll>

I am a fool

JaxYoung

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

Continued_Story

same question

If there exists an array a, the sum of the elements must be in array b.
Since the maximum sum can be 1e9 in that case(b_i <= 1e9), so the sum of the elements of a + this sum (again which appears in b) can be at most 2e9.

Thank you for your reply, but I still can't understand.

I see that. But as I said before, if sum > 2e9, have.find(sum / 2) != have.end() should be false. That's to say the if statement result remains the same without evaluating sum <= 2e9.

I am so confused that the only possible exception I would say is b[i] has element larger than 1e9.

The main problem was you were using a multiset of integers.
I changed it to long long and it worked.
AC submission https://codeforces.com/contest/1512/submission/112652296
I guess have multiset when given arbitrarily large values does not point to end().

Thank you! That's really weired, I always want to save the memory as more as possible. As you guess, I think it's a good problem to consider.

soutrikdas

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 ?

In that block one variable name has a typo:

Spoiler

	else
		{
			x3=x1;
			y3=y2;
 
			x4=x2;
			y3=y1;
		}

Thank you very much for going through my code, I tried with the corrected code and it got accepted.

arpit92_8

(https://codeforces.com/contest/1512/submission/112504223)

Can someone please help me out in B I have worked out every cases but still it's not working!

My concept is that if they are not on the same row or same column then interchange the rows and column

if they are on the same row and the row is 1st row the add the val to both the row index

if they are on the last row then subtract the val from the row index

similarly for the same columns

here val=col1-col2 for cases of same row

and val=row1-row2 for cases of same col

zen_coder

I just had a quick read but it seems:

val=abs(col1-col2);

this is at most n-1. In your test choose n=5, Place both your stars on the same line, in the middle but at first and last columns row+val and row-val will definitely be out of [0;n-1]

112592328 help me problem C

112593336 Problem C! 7 12 ??00?101??1?0?100?? 1100110111110110011

do this in order

first -> ?1 ?0 10 11 00 second -> ?? finaly -> if(n&1) the mid position

RAMESSESII

Since, no high rated contestants tagged the ratings to the problems, how to determine — What could be the problems rating? It's just to assess oneself.

1800O-R_Bust

-12

Speedforces.

 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?

Candidate_noob

If the sum is even and less than equal to 2e9 && it is present in the set named "have".

that just means that after you have subtracted x from the sum, sum should be even so that the question constraint of first n elements sum to n+1 — "This is twice the sum of all the elements in a + x." is satisfied. And then "sum <= 2'000'000'000", we're simply checking if it is an int, to be foundable in "have" multiset. And lastly finding the sum/2 in "have".

why we have to check for the sum less than equal to 2e9? and what is this way of writing 2e9 with single quotation marks???

1-> well multiset "have" is of int data type, so must be less that |2^31-1|. 2-> and multiset does evertything that a set does, in addition it allows duplicate elements and remove or insert operation is O(lgn), that's why we use a multiset here.

Thank you for your reply and what about this 2e9 with strange quotation marks?

and why we have to use this multiset and accumulate I am coming across this multiset data structures for the first time?

digishek

Can someone explain how binary search solution of F works ?

In problem C, why are you both looping to the end (i < (int) s.size()) and not half, and doing it twice reversing the liste?

The inner loop should be enough?

for (int times = 0; times < 2; times++)
{
    for (int i = 0; i < (int) s.size(); i++) 
    {
    ....
    }
    reverse(s.begin(), s.end());
}

Joi2049

Yeah, I was thinking this as well.

I just tested it. It is accepted: https://codeforces.com/contest/1512/submission/112957063

Noctambulant

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

codinginveins

7 weeks ago, # ^ |

https://cp-algorithms.com/algebra/prime-sieve-linear.html

18ucs134

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

nitrousoxide

The convention might by platform-dependent, but sometimes in C++ (-1)/2 = 0. As a result, if at a point you have already made enough money to buy the computer/take the course for the next level, you won't need to spend an extra day to make the money.

Thank you very much.. I was initially adding ai for each day at least once. But as you said if already we have enough money we need not spend a day.

Mushfiq4513

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.com/contest/1512/submission/112549540

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

can you check it?

mnishhh

Same with me. In final testing my solution for G gave tle on test 1 which was accepted at the time of contest. Please help:

They tested again, Accepted :)

dvjakhar31

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?

1000101

I got it. they are at first dividing the number by some prime which divides it. d[x] for the number x. (Remember we got the prime using the sieve.)

Now, Notice that for $$${prime}^{r}$$$ we will have the divisor function equals

$$${prime}^{r} + {prime}^{r-1} + {prime}^{r-2}+ ..... + 1.$$$

If you think about it for some time then you will realize that that's what the expression $$$s[i]=s[i]*d[i]+1$$$ when ran in a loop till it is divisible with "j" is doing.

the remaining part "j" (which gives us s[j]) has gcd equals one with this prime exponent so we can using the above expresssion simply multiply it.

and get $$$s[i]=s[i]*s[j].$$$

Eurus7

Check Second approach in this article for clear understanding

https://www.geeksforgeeks.org/sum-factors-number/

thank u! got it like...

1+p1+p1^2 = p1(p1+1)+1 and so on

vaibhav_verma

Can anyone check my C question . I can't find the testcase where I'm wrong. Anyone please help . https://codeforces.com/contest/1512/submission/112536520

Thanks in Advance:)

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.

Let me explain this...

suppose some number has prime divisors a, b, c and all are prime so using above formula we can write

d(a.b.c)=d(a).d(b).d(c)

Now d(a)=a+1, d(b)=b+1, d(c)=c+1

so d(a.b.c)=(a+1)(b+1)(c+1)

If we expand the R.H.S we get,

d(a.b.c) = a.b.c+a.b+a.c+b.c+a+b+c+1

and that is what d(a.b.c) would be if you calculate, so both are equal.

Let's take 30 as an example.

=> 30 = 2*3*5

so using above formula d(30)=2*3*5+2*3+2*5+3*5+2+3+5+1

=> d(30)=72 & also d(30)=(2+1)*(3+1)*(5+1)=72.

Ask me if you have any doubt.

DemonForces

because if a decomposition of A of this form is p1 ^ a1 * p2 ^ a2 ... and a decomposition of B of this form is q1 ^ b1 * q2 ^ b2 ... then the sum of divisors of A equals to: (1 + p1 + p1 ^ 2 + .... p1 ^ a1) * (1 + p2 + p2 ^ 2 + .... p2 ^ a2) ... -> because no matter how we take numbers from each the parentheses are divisors of A and they are all present.

Next-> d (a) = (1 + p1 + p1 ^ 2 + .... p1 ^ a1) * (1 + p2 + p2 ^ 2 + .... p2 ^ a2), d (b) = (1 + q1 + q1 ^ 2 + .... q1 ^ b1) * (1 + q2 + q2 ^ 2 + .... q2 ^ b2) i.e. gcd (a, b) = 1 then no p and q coincide. hence d (a * b) = d (a) * d (b)

9Curd1Cream

nice bro, got the intuition now.

WhatIf

Can someone please help me out with problem D
My idea was to sort the given array and check if the sum of first nth terms is smaller or greater then the last element, if greater then return -1.
else to check if sum of first n — 1 terms is equal to a specific element, if not then I tried subtract one element and tried to add n + 1 th element in order to sum reach to n + 2th element.

Here is the implementation of the same

You compared with n+2 element, but if the real sum is in n+1'th position? It is possible last elemnt is x!

my idea: if the a[] exist, the sum of a[] can be in position n+1 or n+2. if the sum is in n+1, then x can be 1 to n+2, except n+1. if the sum is in n+2, then x can be 1 to n+1.

Thank you, I realise my mistake.

Can anyone tell testcase 2 — 65 for C ? I am getting error on that case

Zahid_Hasan_Sahin

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

112527550

dhruv7888

I don't know much java , but as much as I have heard Arrays.sort() is implemented using quick Sort and is hence O(N^2)

Collections.sort() getting Accepted :) bah

acChris

Can you help me? #113113659 I use Collections.sort(), but I is still wrong...

You can check my solution :+) 112626918

IshtiaQ99

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

It's happened to me. Got TLE. Then they again tested G, I got AC.

Undercover_pi

Im so happy because I became pupil !!

alokmaurya_81

Me too

chirag_h

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

It keeps failing Test 2

112630518

Try this

Thanks! I get my mistake now

john9925

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

Problem G

Adith082

Problem D Video Tutorial Link : https://www.youtube.com/watch?v=adoB7YeXNqA

Nash2829

I tried problem E but I am getting an orange message "out of bounds" on the line 112. Please help, if possible.. Link to my submission https://codeforces.com/contest/1512/submission/112629138

can someone explain why are we choosing elements like this in problem E :: If k>0, high(i,k)≥s and s−i≥low(k−1), then put the number i in the segment [l,r] , decrease s by i, decrease k by 1; Otherwise, we will not put the number i in the segment [l,r].

.......

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 ?

Consider a pair of days today and tomorrow.

If we got enough money to to an exam today it is allways benefical to do it today, never tomorrow.

This means by induction that for a given number of exams, there is no better solution than doing the exams as early as possible.

sharingan_coder

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

avdp

Try this TC!

mstallion

Test your code on this testcase.

3 1

1??0

2 1

???

Hope it helps

gyan_p_t

Can anyone help me ,why my solution is giving wrong answer Problem C.

My_Solution

bsaiteja35

Anyone, please post their 1512-C-B-Palindrome solution in Java.

Naim_Hasan

Does anyone feels implementation of E is more complicated?

My idea is-

Let k = r-l+1 Segment length.

Take first k numbers in a vector a and let sum = summation of elements in a. Keep last = n.

Now we can increase our last_element in a upto n and also increase sum.

So while (a.back() < last and sum < s) { a.back()++, sum++ };

transfer the last_element to another vector. last--.

After the process ends check transferred_elements_sum == s or not.

If yes, we find out which elements were unused and we print them with our used elements carefully.

Otherwise print -1.

Submission

Hackapie

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.

Drstrange_

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.

Agrawal31

This approach will give TLE, due to the second loop. Since starting j from i*i in the sieve of eranthoses prunes a lot of iterations.

SanjayMarreddi

Hi,

Could someone please help me in knowing which case I am missing in my Solution for Problem — C.

I am getting the following error message : wrong answer jury found answer, but participant did not (test case 42)

I think my code is not returning any output for testcase-42. Could not figure out it.

PS : This was my first time asking a query here. Please forgive me if I missed some info here.

Thanks!

punk_tech

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

UPD Oh, I'm wrong

mcendu

I would like to point out formatting issues in this post. The reference solution should be put into boxes, but it is not. Also, the reference for E has thousand separators; while it is valid C++, it broke the Codeforces syntax highlighter.

asldknflksajdgl

-11

For problem G, I've tried the O(10^7log(10^7)) solution in python 3 as well as pypy3 but getting TLE(Code attached) However, For C++ editorials, its using an O(n) operation in the second for loopfor (int i = 2; i < N; i++) Isn't this unfair for python guys :( or any suggestions on the below code (apart from switching lang)?

(PS: Please be gentle, I'm a novice and might not know all strategies...)

#################### start #########################
def all_factors(N):
    """return count of factors of numbers [1...N] in O(nlogn) time"""

    fac = [1] * (N + 1)
    for i in range(2, N + 1):
        for j in range(i, N + 1, i):
            fac[j] += i
    return fac

N = 10**7+10
fact = all_factors(N)
hmap = {}
for i in range(len(fact) - 1, 0, -1):
    hmap[fact[i]] = i

# print('ready...')
for _ in range(int(input())):
    c = int(input())
    if c in hmap:
        print(hmap[c])
    else:
        print(-1)
#################### end #########################

MikeMirzayanov Geothermal and all other top coders

Can someone help me with problem C? https://codeforces.com/contest/1512/submission/112930573

Not sure what's wrong with my solution...

Filled the center if the string has odd length. Filled the single pairs. 0? 1? ?0 ?1 Filled the rest of the pairs. (? on both sides)

I am getting wrong answer on test case 2. What could that test case be? Need some hints thanks...

Pheonixcoder34

In the A-B palindrome solution,why are we reversing the string in for loop?

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?

OleschY

← Rev. 9 →

Write $$$n=p_1^{a_1} \cdot p_2^{a_2} \cdot ... \cdot p_m^{a_m}$$$ with $$$p_i$$$ primes. Then $$$d(n)=(1+p_1^1+...+p_1^{a_1})\cdot(1+p_2^1+...+p_2^{a_2})\cdot...\cdot(1+p_n^1+...+p_n^{a_n})$$$ (This was a wrong formula first, thanks to put_peace for correcting it!)

Let {$$$q_i$$$} and {$$$r_i$$$} be sets of primes with empty intersection. Let $$$Q=q_1^{b_1} \cdot q_2^{b_2} \cdot ... \cdot q_m^{b_m}$$$ and $$$R=r_1^{c_1} \cdot r_2^{c_2} \cdot ... \cdot r_k^{c_k}$$$. Then $$$gcd(Q, R)=1$$$ and $$$d(Q \cdot R) = d(Q) \cdot d(R)$$$ using the formula for $$$d$$$.

This isnt a formal proof, but it outlines the idea for a proof.

See also https://en.wikipedia.org/wiki/Euler%27s_totient_function the totient function is similar to $$$d$$$ here.

put_peace

3 months ago, # ^ |

$$$d(n)=(a1+1)⋅(a2+1)⋅...⋅(am+1)$$$, I think this is not correct.

Oh, you are totally right. What I wrote was the amount of divisors not the sum of divisors!

Your comment below is right. If I replace my error with $$$d(n)=(1+p_1^1+...+p_1^{a_1})\cdot(1+p_2^1+...+p_2^{a_2})\cdot...\cdot(1+p_n^1+...+p_n^{a_n})$$$ then it's correct. Thanks for the heads up!

Just to see how it is correct, $$$d(p^{a}).d(q^{b}).d(r^{c}) = (1 +p + p^{2} + ... + p^{a}).(1 +q + q^{2} + ... + q^{b}).(1 + r + r^{2} + ... + r^{c})$$$
if you expand the RHS, you can verify that it will give $$$d(p^{a}q^{b}r^{c})$$$

yes got it,
we can even think of it like
d(p^a) as sigma(p^ai) where 0<=ai<=a
similarly, d(p^a.q^b.r^c) = sigma(p^ai.q^bi.r^ci) for all 0<=ai<=a 0<=bi<=b 0<=ci<=c
its like all combination of powers till a,b,c which can be written as
d(p^a.q^b.r^c) = (1+p+p^2+...+p^a).(1+q+q^2+...+q^b).(1+r+r^2+...+r^c)
here the rhs its same as choosing power of p and power of q and power of r (i.e same as getting all possible combinations for d(p^a.q^b.r^c)) same as d(p^a).d(q^b).d(r^c)

waltz47

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

satyamshree22

113151207

This is my approach , it works but i think i could do better logic wise , any one with a better approach please help me

_M_P_A_S_A_G_2

Why task E has 1900 rating? It's quite simple

helvetic4

deleted

nandita91

for problem almost rectangle1512B][SUBMISSION:113711769 - Почти прямоугольник my output is matching with the recquired one but submission gives wrong answer please tell why? //my code:

include<bits/stdc++.h>

using namespace std; int main() { int t,n,i,j; stack<pair<int,int>>st;

cin>>t;
while(t--)
{
    cin>>n;
    char ar[n][n];
   for(i=0;i<n;i++)
    for(j=0;j<n;j++){
    cin>>ar[i][j];
    if(ar[i][j]=='*')
        st.push({i,j});}
   int x1=st.top().first,y1=st.top().second;
   st.pop();
     int x2=st.top().first,y2=st.top().second;
if(x1!=x2&&y1!=y2){
    ar[x1][y2]='*';
    ar[x2][y1]='*';
}
 if(x1==x2){
    ar[(x1+1)%n][y2]='*';
    ar[(x1+1)%n][y1]='*';
}
if(y1==y2){
    ar[x1][(y1+1)%n]='*';
    ar[x2][(y1+1)%n]='*';
}
for(i=0;i<n;i++){
    for(j=0;j<n;j++)
            cout<<ar[i][j]<<" ";
             cout<<endl;}

}

_MINECRAFT___

I find a new solution of Problem C. awa ~~~~~

using namespace std;

string solve(int a, int b, string str) { if (a + b != str.size()) return "-1"; if (a % 2 && b % 2) return "-1"; for (int i = 0; i < str.size() / 2; i++) { char &A = str[i], &B = str[str.size() — 1 — i]; if (A != B && A != '?' && B != '?') return "-1"; else if ((A == '?' && B != '?') || (A != '?' && B == '?')) if (A == '0' || B == '0') a -= 2, A = B = '0'; else b -= 2, A = B = '1'; else if (A == '0' && B == '0') a -= 2; else if (A == '1' && B == '1') b -= 2; } for (int i = 0; i < str.size() / 2; i++) { char &A = str[i], &B = str[str.size() — 1 — i]; if (A == '?' && B == '?') if (a > 1) a -= 2, A = B = '0'; else if (b > 1) b -= 2, A = B = '1'; } if (str.size() % 2) { char &final = str[(str.size() — 1) / 2]; if (final == '0') a--; if (final == '1') b--; if (final == '?') if (a) final = '0', a--; else if (b) final = '1', b--; } if (a == 0 && b == 0) return str; return "-1"; }

int main() { if (fopen("input.txt", "r")) freopen("input.txt", "r", stdin);

int t;
cin >> t;
while (t--) {
    int a, b;
    string str;
    cin >> a >> b >> str;
    cout << solve(a, b, str) << endl;
}

return 0;

~~~~~

uday09

Can some one suggest some edge or additional testcases for problem D...Iam getting wrong ans on 86th testcase

shivanshshukla60

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

DeepBisman

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

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

muhtasim2020

4 months ago, # |

Can you help me finding why I am getting WA in this code?? https://codeforces.com/contest/1512/submission/115197444

kumasento

G is such a great question!

lcyyy

#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?

oh..just forget what i said ,hahaha

sc9

Could someone please help me out with part C? Submission 115966879

I failed test case 42. Apparently, my program outputs '-1' while the right output is 101010000010101.

As suggested by comments, I tried out "1 9 6 ?????????0?????", but I got the output 000110101011000 instead of -1. Could someone please provide the right test case or point out what is wrong with my code?

maschere.

Can someone explain me the given solution from problem E? I read the tutorial and implemented the solution in a different way, while the given solution does a lot of stuff that aren't said in the tutorial.

Here are the questions:

1) Why are we searching for the first number first to be used in the subset?

for (int first = 1; first + (r - l) <= n; first++)

2) Why are we computing sum as the max sum we can get from a sequence ranging from: first to first + (r-l)? The tutorial said that we want a maximum sum we can get from a sequence ending at a certain number to be >= s, why is this solution instead checking that this maximum sum sum is <= s? Similarly why do we want s - sum <= r - l + 1?

int sum = 0;
for (int i = l; i <= r; i++) {
    sum += first + (i - l);
}

if (sum <= s && s - sum <= r - l + 1)

3) What is needArr? Why after an index >= needArr instead of computing ans[i] = first + (i - l) we actually want to add 1 to a[i] so a[i] = first + (i - l) + 1?

int needAdd = r - (s - sum) + 1;
for (int i = l; i <= r; i++) {
     ans[i] = first + (i - l);
     if (i >= needAdd) {
         ans[i]++;
     }
     non_blocked.erase(ans[i]);
}

Any help would be appreciated, thanks in advance!

kaashmonee

Hi, I'm pretty confused on my solution for B. It feels like I have a correct implementation; however, the judge says I have a RUNTIME ERROR: Exit code is -1073741819. It does not offer any additional information, so I was wondering if anyone had any ideas for how to go about debugging this issue?

My solution is here: https://codeforces.com/contest/1512/submission/117051385.

lms: "long long multiset"

Thank you very much in advance.

manojthakur123450

in problem D on testCase 17 i got TLE in java how to remove it. i have done it in O(nlogn)- 1. [submission:117376993][link of solution is ](https://codeforces.com/contest/1512/submission/117376993)

aim100

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).

nikhilnagrale2

my solution is fairly straightforward and understandable. you can check out here

Thanks, It helped.

Hidder

3 months ago, # |

null

JOOG

2 months ago, # |

I liked problem E. By the way, solution code could be shorter. Check my solution.

doing_cloth

7 weeks ago, # |

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

that part

      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

the whole code

Thanks in advance!

sanketmishra

2 weeks ago, # |

127575912 can someone please tell me why I am failing on 88th iteration of 2nd test case ? Question- ab palindrome.

Supermagzzz's blog

include

MikeMirzayanov

This is my approach , it works but i think i could do better logic wise , any one with a better approach please help me

include<bits/stdc++.h>

include <bits/stdc++.h>