I am solving the problem https://codeforces.net/problemset/problem/1033/C. I could not get the editorial and found the comment https://codeforces.net/blog/entry/62287?#comment-462858 useful. I have implemented the solution as per the comment, but it is giving WA
WA
import java.util.*; import java.io.*; import java.math.*; public class Coder { static StringBuffer str=new StringBuffer(); static int n; static int a[]; static void solve(){ int dp[]=new int[n]; for(int i=0;i<n;i++) dp[i]=-1; for(int i=0;i<n;i++){ int cur=a[i]; boolean isAll=true; for(int j=i+cur;j<n;j+=cur){ if(a[j]>cur && dp[j]==0){ isAll=false; break; } } for(int j=i-cur;j>=0;j-=cur){ if(a[j]>cur && dp[j]==0){ isAll=false; break; } } if(isAll){ dp[i]=0; }else{ dp[i]=1; } } } public static void main(String[] args) throws java.lang.Exception { BufferedReader bf; PrintWriter pw; boolean lenv=true; if(lenv){ bf = new BufferedReader( new FileReader("input.txt")); pw=new PrintWriter(new BufferedWriter(new FileWriter("output.txt"))); }else{ bf = new BufferedReader(new InputStreamReader(System.in)); pw = new PrintWriter(new OutputStreamWriter(System.out)); } // int t = Integer.parseInt(bf.readLine().trim()); // while (t-- > 0) { String []st=bf.readLine().trim().split("\\s+"); n=Integer.parseInt(st[0]); a=new int[n]; st=bf.readLine().trim().split("\\s+"); for(int i=0;i<n;i++) a[i]=Integer.parseInt(st[i]); solve(); // } pw.print(str); pw.flush(); // System.outin.print(str); } }
AC
/** * author: tourist * created: 07.10.2018 20:09:43 **/ #include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n; cin >> n; vector<int> a(n), pos(n); for (int i = 0; i < n; i++) { cin >> a[i]; a[i]--; pos[a[i]] = i; } string win(n, '?'); for (int x = n - 1; x >= 0; x--) { int i = pos[x]; win[i] = 'B'; int j = i; while (true) { j -= (x + 1); if (j < 0) { break; } if (win[j] == 'B') { win[i] = 'A'; break; } } j = i; while (true) { j += (x + 1); if (j >= n) { break; } if (win[j] == 'B') { win[i] = 'A'; break; } } } cout << win << '\n'; return 0; }
My doubt is that why can't we do like WA and why should we loop using elements instead of indexes?
Please explain why the earlier approach is giving WA and not later.