I cant understand d, can someone explain the approach

i tried storing the increasing differnce of a[i] — b[i] (and consecutively increasing a[i]) in maps but am getting TLE.Can someone tell me why my time complexity is getting f-ed.Can someone also tell me the optimizations.my submission :((

i hoper they will add text tutorial too

I have a doubt in my submission for problem B where I iterate on the string b and whenever I match a character of it with "a" i increment the ptr j of b and then increase the variable cnt. Finally I print the answer as a.size + b.size -cnt . But it fails somewhere, can anyone help me give a case where my solution fails or the problem with my approach?267685947

Video editorials is a great addition to codeforces, I hope we normalize it. However text editorials is much important than video editorials so please don't stop doing it.

can anyone tell me in problem B answer is n+m-longest common subsequence of both strings? is it correst

267826797 ques b) can anyone why its not giving right output or on which test case it fails

someone please hack this solution:- https://codeforces.com/contest/1989/submission/267711789

Nice try! However, not all users on CodeForces are good at English, they may find it difficult to understand this video. May the authors upload text tutorial too?

But Shayan got TLE in his submission 267715088, can we get updated tutorial for D?

upd: sorry, he got WA

Disappointing judging for the D problem, I had made an O(n) submission without including

ios_base::sync_with_stdio(false); cin.tie(nullptr);

and it didn't pass due to TLE, but after including this block and submitting an O(nlogn) code, it did.

I am assuming normally optimizations like these should not be a factor but due to the tight constraints, they resulted in TLE.

Problem Statement for D sucks

I hope they add the Text editorials soon

Please someone point out on which case this code fails for question B 267781357

[deleted]

[deleted]

Weak test cases in D. But anyway, good round indeed.

can someone tell me why i go wrong answer at test 2 267864473

This solution for problem D is getting a runtime error on the 9 th testcase. I can't seem to find the issue. Can you guys help!

https://codeforces.com/contest/1989/submission/267869614

Nice problems

Has anyone been able to write a non-DP solution to D?

I'm using sorting, and despite all my optimizations, I still get TLE on test 10. Here: https://codeforces.com/contest/1989/submission/267885902

Can someone tell is it possible to optimize this code for problem D: public static long SmithingSkills2(int[][] arr, int[] metals){

Arrays.sort(arr, new Comparator<int[]>() {
         @Override
         public int compare(int[] o1, int[] o2) {
             double ratio1 = (double)o1[1] / o1[0];
             double ratio2 = (double)o2[1] / o2[0];

             if(ratio1 != ratio2){
                 return Double.compare(ratio2, ratio1);
             }else{
                 if(o1[1] == o2[1]) return Integer.compare(o1[0], o2[0]);
                 return Integer.compare(o2[0], o1[1]);
             }

         }
     });

     PriorityQueue<Long> pq_metals = new PriorityQueue<>(Collections.reverseOrder());
     for(int i : metals) pq_metals.add((long)i);

     long total_ans = 0;

     for(int[] weapon : arr){

         while(!pq_metals.isEmpty() && pq_metals.peek() >= weapon[0]){

             long ele = pq_metals.poll();
             long a,x,y;

             a = ele;
             x = weapon[0];
             y = weapon[1];

             long low = 1, high = (long)Math.pow(10,3);
             long n = 0;
             while(low <= high){
                 long mid = low + (high - low)/2;

                 if((long)a - (long)mid * x +(long)mid * y >= (long)x){
                     n = mid;
                     low = mid+1;
                 }else{
                     high = mid-1;
                 }
             }
             n++;
             total_ans += 2*n;
             a = a - n*x + n*y;

             pq_metals.add(a);

         }

     }
     return total_ans;
 }

Code explanation: 1. Sort the weapon array according to their bi / ai values in decreasing order. 2. Build a priority queue for metal ingots (let's call it pq). 3. Start iterating over the sorted weapon array. 4. For the current weapon, the task is to calculate the maximum possible experience for the i-th weapon. 5. To do this, start picking elements (denoted as ele_i) from the priority queue. 6. For the i-th weapon, determine the maximum possible experience, which can be calculated using binary search. 7. Update solution accordingly

Can some one tell me why this is wrong for B

import java.util.*; public class Main{ public static void main(String args[]){ Scanner sc=new Scanner(System.in); int t=sc.nextInt(); sc.nextLine(); while(t-->0) { String a=sc.nextLine(); String b=sc.nextLine(); int n=a.length(); int m=b.length(); int k=0; if(n>m) {
HashMap<Character,Integer> hashmap=new HashMap<>(n+1); for(int i=0;i<n;i++) {
char ch=a.charAt(i); hashmap.put(ch, hashmap.getOrDefault(ch, 0) + 1); } int count=0; for(int j=0;j<m;j++) { char ch1=b.charAt(j); if(hashmap.containsKey(ch1) && hashmap.get(ch1)>0) { hashmap.put(ch1,hashmap.get(ch1)-1); } else{ count=count+1; } } System.out.println(n+count); } else{ HashMap<Character,Integer> hashmap=new HashMap<>(m+1); for(int i=0;i<m;i++) {
char ch=b.charAt(i); hashmap.put(ch, hashmap.getOrDefault(ch, 0) + 1); } int count=0; for(int j=0;j<n;j++) { char ch1=a.charAt(j); if(hashmap.containsKey(ch1) && hashmap.get(ch1)>0) { hashmap.put(ch1,hashmap.get(ch1)-1); } else{ count=count+1; } } System.out.println(m+count); } } } }

Solution of d provided in video got wrong answer on test case 21

In problem D, I am getting Runtime error on test 14. Not able to figure out the issue. Pls someone help. My submission: 269094484