While practicing DP problems on various sites, I came across this problem:- https://www.hackerearth.com/practice/algorithms/dynamic-programming/introduction-to-dynamic-programming-1/practice-problems/algorithm/leaf-and-limelight-attack-circuit/description/ on HackerEarth.

According to the editorial, we pre-process the values in the solution. Queries are divided into even and odd. DP[i] gives the solution for ith query. So, DP[1] = 1, DP[3] = 25, DP[5] = 101.

So, they have derived a formula which is :-

DP[i] = DP[i-2] + (i-2)2 + (i-1) + (i-2)2 + 2(i-1) + (i-2)2 + 3(i-1) + (i-2)2 + 4(i-1) which gets reduced to

DP[i] = DP[i-2] + 4i2 — 6*(i-1)

So my question is, how was this formula derived? What was the approach in deriving this ?

704A - Thor Hello everyone, I've just started competitive programming and love this site! So, I took part in Round #366, and I am getting a Runtime error on test 3 in Problem Thor. I tried to find it, but I couldn't find it. So, if anyone can point out what is causing the Runtime error in the code below:-

public class Thor {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line1 = br.readLine();
        StringTokenizer tokenizer = new StringTokenizer(line1," ");
        int n = Integer.parseInt(tokenizer.nextToken());
        int q = Integer.parseInt(tokenizer.nextToken());
        
        int[] notifs = new int[n+1];
        long[] res = new long[q+1];
        long sum=0L;
        
        for(int i=0;i<q;i++){
            String ip = br.readLine();
            StringTokenizer token = new StringTokenizer(ip," ");
            int type = Integer.parseInt(token.nextToken());
            int var2 = Integer.parseInt(token.nextToken());
            switch(type){
                case 1:
                    notifs[var2]++;
                    sum++;
                    break;
                case 2:
                    int r = notifs[var2];
                    sum-=Long.parseLong(String.valueOf(r));
                    notifs[var2]=0;
                    break;
                case 3:
                    int rem = var2;
                    int j=1;
                    while(rem!=0){
                        if(notifs[j]>=rem){
                            notifs[j]-=rem;
                            rem-=var2;
                            break;
                        }else{
                            rem-=notifs[j];
                            notifs[j]=0;
                        }
                        j++;
                    }
                    sum-=Long.parseLong(String.valueOf(var2));
            }
            res[i]=sum;
        }
        
        for(int i=0;i<q;i++){
            System.out.println(res[i]);
        }
    }
}

Thanks :)