Shayan's blog

Educational Codeforces Round 167 (Rated for Div. 2) — Video Tutorial
By Shayan, 4 months ago, In English

Hi,

Here is the video editorial of all the problems of Educational Codeforces Round 167 (Rated for Div. 2). I hope it helps.

1989A — Catch the Coin

1989B — Substring and Subsequence

1989C — Two Movies

1989D — Smithing Skill

1989E — Distance to Different

1989F — Simultaneous Coloring

  • Vote: I like it
  • +91
  • Vote: I do not like it

»
4 months ago, # |
  Vote: I like it +4 Vote: I do not like it

I cant understand d, can someone explain the approach

→ Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 2   Vote: I like it +7 Vote: I do not like it

    First,we can consider that each $$$c_i$$$ is independant.So,we can calc the answer of each $$$c_i$$$.Then we calc their sums.

    Then,obviously,we can discover $$$i$$$ is important for us to use it if there is $$$j$$$,$$$a_j\le a_i$$$ and $$$a_j-b_j\le a_i-b_i$$$。Because we can use $$$j$$$ to replace $$$i$$$ and we can save more objects.

    Therefore,we can let $$$d_i=a_i-b_i$$$ and sort $$$(a_i,d_i)$$$ in the order of $$$a_i$$$.Then a useful $$$(a_i,d_i)$$$ means there isn't $$$j<i$$$,$$$d_j\le d_i$$$.So we can record $$$k=\min_{1\le j<i} d_j$$$，$$$d_i<k$$$。

    Like this:

    [submission:267715465]

    Then,we use dp algorithm to solve it. Let $$$f_i$$$

    is the answer that we have $$$i$$$ objects.

    Obviously,$$$f_i=f_{i-d_j}+1$$$,$$$j$$$ is the maxnum $$$x$$$,$$$a_x\le i$$$.

    Because $$$a_i\le 10^6$$$,we only calc for $$$i\le 10^6$$$.

    For $$$i>\max a$$$,we can reduce it to $$$i-kd$$$ by use $$$max a$$$.$$$k=\lfloor\frac{i-\max a}{d}\rfloor+1$$$

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
      ← Rev. 3   Vote: I like it 0 Vote: I do not like it

      If you have some spare time, may you please explain why this solution 267833774 using binary search gets TLE? I would think that the complexity is something like 1e6 * log2(1e6) which I think should pass

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Is the upper_bound function in your code, not being called multiple times. If that is the case, then the worst-case complexity will be N*N*logN. I wrote a similar looking code and faced the same problem. I am not 100% sure about your code though.

        → Reply
»
4 months ago, # |
  Vote: I like it +1 Vote: I do not like it

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 :((

→ Reply
»
4 months ago, # |
  Vote: I like it +12 Vote: I do not like it

i hoper they will add text tutorial too

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 dbcebd eddedad answer:10 since the first letter of b may not in a.

    → Reply
»
4 months ago, # |
  Vote: I like it +35 Vote: I do not like it

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.

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    I also think so. And I'm Chinese, I can't watch the videos on youtube.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    consider this a-> abc b->xaxbxcx here lcs is 3(abc) so according to you ans must be 3+7-3 but actual ans is 9 ie 3+7-1

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      thanks

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        why???

        Answer is 7 for this test case

        → Reply
        • »
          »
          »
          »
          »
          4 months ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          no. a is substring.keep this in mind while thinking about subsequence and not to distort continuity of a in making b.

          → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Well no its not . Suppose you get first strings abcde and the other as bfd , the actual answer of this will be 7 , it is basically the longest sequence of string a which is also subarray of string b.

    → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    consider a test case where a=contest and b=teast
    then according to your code answer is 7 but answer is 10

    → Reply
    • »
      »
      »
      4 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      i am getting ans as 10

      → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        I don't know the testcase but it is due to in between in string b when we start checking it is in a or not. I also get wrong answer at same test case but my approach was different

        → Reply
  • »
    »
    4 months ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    I don't know dp but your solution fails in the below test case.
    Test case a = abc and b = bbaacc
    then according to your code answer is 8 but answer is 7.
    answer string = bbaabcc

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    The authors are gonna upload the text tutorials. Not uploading the text tutorials in favor of video editorials would be a retarded decision. Video tutorials are just like a bonus for whoever learns better by watching.

    → Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

upd: sorry, he got WA

→ Reply
»
4 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem Statement for D sucks

→ Reply
»
4 months ago, # |
  Vote: I like it +6 Vote: I do not like it

I hope they add the Text editorials soon

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

[deleted]

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Bro when are you starting post contest discussions on youtube

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    These video tutorials are unofficial, text editorials will be released soon by the contest authors.

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can u explain the idea of your approach

    → Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Your idea is incorrect because whenever you get that b[i] == a[j] you are assuming that taking that a[j] will give you the best answer that isn't necessarily true. For example, there is this test case:

    1 bba abb

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/1989/submission/267869614

→ Reply
»
4 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Nice problems

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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.me/contest/1989/submission/267885902

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    4 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think the expected time complexity is : O(nlogn + mlogm + nlogm * log(1000)).

    → Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello, Could somebody check why my solution is too slow? I get TLE on TEST 7. Thanks :) https://codeforces.me/contest/1989/submission/270892685

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I am new , need help on substring and subsequences, why won't it work if I get the longest common subsequence between string a and string b and then return the result as : sizeof(a)+sizeof(b)-sizeof(LCS of a,b) ? .

→ Reply