flamestorm's blog

By flamestorm, 2 years ago, In English

Thanks for participating!

1703A - YES or YES?

Idea: flamestorm

Tutorial
Solution

1703B - ICPC Balloons

Idea: flamestorm

Tutorial
Solution

1703C - Cypher

Idea: mesanu

Tutorial
Solution

1703D - Double Strings

Idea: MikeMirzayanov

Tutorial
Solution

1703E - Mirror Grid

Idea: mesanu

Tutorial
Solution

1703F - Yet Another Problem About Pairs Satisfying an Inequality

Idea: flamestorm

Tutorial
Solution

1703G - Good Key, Bad Key

Idea: mesanu

Tutorial
Solution
  • Vote: I like it
  • +72
  • Vote: I do not like it

| Write comment?
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Quickly

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    most satisfying G solution : state : dp[i][j] means at ith element we use exactly j bad keys. trans : either we have to use bad key at ith place or it already been use before.

    #include <bits/stdc++.h>
    using namespace std;
    
    /* UserName SeniorLikeToCode [Abhishek Gupta (AKGEC 3rd year)]; */
    
    #define int     long long
    #define endl    '\n'
    
    void solve() {
        int n, k; cin >> n >> k;
        vector<int> a(n); for (auto &i : a) cin >> i;
    
        int dp[n + 1][40], ans = 0;
        memset(dp, 0, sizeof(dp));
    
        for (int i = 0; i < n; i++) {
            dp[i + 1][0] = dp[i][0] + a[i] - k;
            for (int d = 0; d <= min(32ll, i + 1) ; d++) {
                dp[i + 1][d + 1] = max(dp[i][d + 1] + (a[i] >> (d + 1)) - k, dp[i][d] + (a[i] >> (d + 1)));
            }
        }
        for (int i = 1; i <= n; i++) for (int d = 0; d <= 33; d++) {
            ans = max(ans, dp[i][d]);
        }
    
        cout << ans << endl;
    }
    
    signed main() {
        ios_base::sync_with_stdio(NULL);
        cin.tie(NULL); cout.tie(NULL);
    
        int test = 1; cin >> test;
        while (test--) solve();
    }
    
    
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey I would like to request a clarification: why do you report answer as the maximum of dp[i][j] over all values of i and j? should it not be just maximum value of dp[n][j] over all values of j?

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

        I also want to ask this question,did you get the answer?

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

          Because of their definition "dp[i][j] means at ith element we use exactly j bad keys". Note that we can definitely use more than 33 bad keys, but it won't matter because after 33 bad keys all elements to the right will be 0. So, considering dp[i][j] for i < n is equivalent of handling all cases where a[k] becomes 0 for all k > i (note ai >= 0). If the definition was "at most j bad keys", then we could just answer max over j of dp[n][j], but the transition would be different.

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

        Sorry for the late reply, for the answer Think like you brute forcing and you can use j keys, now after using j keys, You dont know which previous step give you the best answer. So new question arises at any stage did we know the best answer ? the answer is "NO" , for any ith step we are checking complete ith step. That's the simplified reason why we are checking complete i * j for the last answer.

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

      Hey! I was solving this problem using DP and I,ve written almost the same code.

      Please have alook at my submission:262108989.

      I dont understant the reason it is giving WA of tc4.

      I am new to DP and I have been trying to debug since all night. please help

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for fast tutorial

»
2 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Amazing contest !! ..E is tricky one!

»
2 years ago, # |
Rev. 2   Vote: I like it +60 Vote: I do not like it

F is solvable with prefix sums in $$$O(n)$$$.

For each $$$i$$$ count the number of elements, where $$$j \leq i$$$ and $$$a_j<j$$$ ($$$pref_i$$$). And for each $$$i$$$ where $$$a_i<i$$$ just add $$$pref_{a_i-1}$$$ to the answer.

Here is my solution 163953789.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    You beat me by 1 second, gonna say the same thing.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you please explain a bit more?

    the prefix sum approach isn't really clear to me?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      For every element we can store how many element we have encountered before it, that have v[i] < i

      int c = 0;
      for(int i = 0; i < n; i++)
      {
          cnt[i] = c;
          // 1 Based Indexing
          c += (i + 1 > v[i]);
      }
      

      Now for every element we can find whether we have it's value in range and whether we can find element so that we can satisfy the 2nd part in the condition i.e. i < v[j], other conditions are already satisfied

      int ans = 0;
      for(int i = n - 1; i >= 0; i--)
      {
          // We check for an element only when the element itself follows the v[i] < i rule
          // AND
          // Only when its index is in our range 1 to n-1 (skipped 0 because there are no elements before it)
          // THEN
          // we find how many elements are before the index equal to i since there is strict inequality
          if (i + 1 > v[i] && v[i] > 1)
          ans += cnt[v[i] - 1];
      }
      

      My Submission

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you plz tell me why your code is giving correct ans for the case when a[i]-1 becomes -1. Beacause that should give a garbage value

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      My bad, thanks for noticing. Probably it is $$$0$$$ in this case.

      Now the code is correct.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it -10 Vote: I do not like it

    Can G be solved by DP ?

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I will say that it was a good contest. Thanks for the quick tutorial

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey! Can anyone clarify why my solution is showing TLE on Test Case 10 (Problem D), my approach is similar as that mentioned in the Editorial. Thanks! 163871330

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +6 Vote: I do not like it

    Your problem lies here I suppose:

    Spoiler

    When you wrote ans = ans + '1' what the code did was calculate ans + '1' then assign that resulted string to ans, which made this operation $$$O(N)$$$. Use ans += '1' next time.

    Bonus: Here's your very same code accepted with those changes.

  • »
    »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    You just need to speed up the I/O. Just add this line (before defining t int your main funtion). ios::sync_with_stdio(false);cin.tie(nullptr); After that, tabulate the code correctly and you'll get AC.

»
2 years ago, # |
Rev. 2   Vote: I like it +5 Vote: I do not like it

I think problem F can be done in O(n) time.

As mentioned, we only need to consider indices i such that a_i < i. Call such indices "good". We can make a prefix array such that the ith element is the number of good indices less than or equal to i.

Now consider all possible pairs (i,j) that work for a fixed good index j. The number of possible values for i is the number of good indices less than a_j, which is stored within the prefix array. The answer can then be found by summing across all good indices j.

The prefix array can be created in 1 pass, so that takes O(n) time. The summing across all good indices can also be done in 1 pass, so this is O(n) time again.

Code for this can be found in my submission

Edit: Apparently got sniped lmao

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you plz tell me why your code is giving correct ans for the case when a[i]-1 becomes -1. Beacause that should give a garbage value

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I specifically excluded it in the if condition to handle that bug if a[i] < i+1 and a[i] > 0:

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have done the same. What do you mean by "sniped" ?

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Someone else said a similar thing while I was typing my message

»
2 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Problem G was a good one.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For the problem D we can use unordered_set<string> cache to store the strings. Then for each string, bruteforrce divide the strings in two and check whether both of these strings exist in the cache or not. Simple

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    to be honest though, you should be very cautious on using hash-based data structures in codeforces. Some people are masters of hacking and can easily find hundreds, even thousands of hash collisions.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      Thats true... I think one way we can avoid is by making 2 or three hashes differently and storing in each of them. That way the chance of getting same hashes reduces significantly

»
2 years ago, # |
Rev. 2   Vote: I like it -15 Vote: I do not like it

This code of mine for question D(double strings) is giving TLE on test 3 and I don't know why. Please help me where is the problem?

#include<bits/stdc++.h>
using namespace std;
#define ll long long int

char check_string(ll k,vector<string> &v){
    if(v[k].size() == 1) return '0';
    for(ll i=0;i<v.size();i++){
        if(i == k) continue;
        for(ll j=0;j<v.size();j++){
            if(j == k) continue;
            if(v[i]+v[j] == v[k]) return '1';
        }
    }
    return '0';
}

int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        vector<string> v(n);
        for(ll i=0;i<n;i++){
            cin>>v[i];
        }
        string s;
        for(ll i=0;i<n;i++){
            s += check_string(i,v);
        }
        cout<<s<<endl;
    }
    return 0;
}
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can F be solved by Fenwick tree??

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes

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

      can u explain please why the index in segment tree is ai ( which could be 1e9 ) insted of indexes of original array

  • »
    »
    2 years ago, # ^ |
    Rev. 3   Vote: I like it +7 Vote: I do not like it

    any solution which can count pairs where $$$i < a_j$$$ where $$$a_i < i, a_j < j$$$ in all $$$i$$$ and $$$j$$$ is a valid solution. therefore Segment Trees and Fenwick Trees are valid solutions, so are prefix sums.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes. I have done it using segment tree. here is my solution 163925757

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Honestly, F was too easy with Segment Trees (or Fenwick Trees, those two have identical purposes). I think any person with some experience of common segment tree problems would easily solve it.

»
2 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Let's see in the hacking phase if people learned to use the map instead of the unordered_map. beethoven97 I summon you!

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

why this solution 163935126 giving TLE ? Anybody please help

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    because memset function fills the DP using its size --> O(N), here it is N = 1e5 so your dp gets filled for all test cases which can be upto 1e4, so ~1e9 operations per second are performed.

    use this
»
2 years ago, # |
Rev. 2   Vote: I like it +3 Vote: I do not like it
  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For the testcase:

    1
    32 100
    2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
    

    your code gives a negative answer. The dp needs to be able to go from dp[i-1][31] to dp[i][31] without decreasing it by k.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Here is a little trick. We know, that answer always $$$0$$$ or bigger (because we can just open chests for free). That means answer is not only $$$max(dp[n][i]) \; for \; all \; i < 32$$$, but $$$max(dp[i][j]) \; for \; all \; i < n \; all \; j < 32$$$

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Thank you for the very good contest, all the problems are enjoyable

I learn some new thing from problem G

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell why using vector in this solution for problem E gives wrong answer? Replacing vector with plain array makes it accepted. Submission link

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Look at the case when x = 0, you are accessing sum[x-1] or sum[-1]

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You're right. I guess it was luck that it got accepted with c array.

»
2 years ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

someone hacked my D (163901816) can anyone provide me test case ?

»
2 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

DP solution for G. Lang: PyPy3-64 ____________________________________________________________________________________

t = int(input())
 
 
for _ in range(t):
    n, k = map(int, input().split())
    *arr, = map(int, input().split())
 
    MAX_HALF_CNT, NINF = 1, -2**63
    max_coins = max(arr)
    while max_coins >> MAX_HALF_CNT:
        MAX_HALF_CNT += 1
    MAX_HALF_CNT += 1
 
    dp = [[NINF] * MAX_HALF_CNT for _ in range(n)]
    # dp[i][half_cnt] 打开第i个抽屉后所能得到的最大硬币数,其中使用了half_cnt次坏钥匙,
 
    dp[0][0] = arr[0] - k # 用好钥匙,减k
    dp[0][1] = (arr[0] >> 1) # 用坏钥匙,减半
    # print(dp)
    for i in range(n-1):
        for h in range(MAX_HALF_CNT):
            dp[i+1][h] = max(dp[i+1][h], dp[i][h] + (arr[i+1] >> h) - k)
            if h + 1 < MAX_HALF_CNT:
                dp[i+1][h+1] = max(dp[i+1][h+1], dp[i][h] + (arr[i+1] >> (h + 1)))
            else:
                # 啥都没了
                dp[i+1][h] = max(dp[i+1][h], dp[i][h] + 0)
 
    print(max(dp[n-1]))

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Could help me G problem?i use dp to slove it ,but i cant fine my problem.thank u very much

problem G

TAT...my english is poor ,but i try to share my idea

j:the number of good key

pw(2,x)=2**x

when we open the i th box ,if we use j good keys so we use (i-j) bad keys.but pw(2,33)>1e9,so i think the number of good key is lower than 33.

if the number of bad key is upper than 33,we can see it as 1e14.

so when we open some box,if we use good keys ,we got a[i]/(pw[(i-j)] -m cost

and we use bad keys ,we got a[i]/(pw[(i-j)] -m

so DP[i][j] is mean open i boxes use j good keys.

Dp[i][j]=Dp[i-1][j]+ bad keys or DP[i][j]=DP[i-1][j-1] + good keys

so whats wrong with me TAT

  • »
    »
    2 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Suppose that n and k are very large And the optimal operations are always use bad keys. In this case obviously we use more than 32 bad keys but your solution don't considers this and gives the wrong answer.

    To fix it : for calculating answer iterate over all dp values and get maximum instead of only dp[n — 1] (because if we do this we consider above case):

    for(int i = 0; i < n; i++)
       for(int j = 0; j < 32; j++)
           ans = max(ans, dp[i][j]);
    

    My submission : 163915709

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For first 30 minutes i think in E we need to make matrix by add 1. Later i eays accepted this Problem

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for the fast editorial

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Another F approach. We can create p where p[i] = (a[i] < i), after that create a prefix sum on that array and iterate over a and do the following:

  • check if p[i] = 1, otherwise continue
  • check if a[i] >= 2, otherwise continue
  • add prefsum[a[i] — 1] to the answer

So why do we need a[i] >= 2 statement? If a[i] < 2, then there is no way to satisfy this inequality. a[i] >= 0, i >= 1, therefore a[i] < i < 1 < j can't be satisfied. Check out my implementation if you are interested 164005949. What do you think about this one?

P.S Well, just find out some guy already told about the same approach...

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Simple recursive DP solution for G here.

»
2 years ago, # |
  Vote: I like it +5 Vote: I do not like it

map<string, bool>? Why not just use a set<string>?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone tell me why this dp solution is getting WA, doesn't make any sense to me? https://mirror.codeforces.com/contest/1703/submission/163945776

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You also have to update your answer while calculating dp so as to counter cases when you use more than 30 bad moves. One such example will be, 60 chests containing 2 coins and lets say k = 1e9.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      You are saying that i have to take the max of the whole matrix?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Not really the whole matrix, max of $$$dp[i][30]$$$ over all chests $$$i$$$ + your current logic will be sufficient.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Video Solutions of complete problemset.

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

F can be solved in linear time. submission

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Ratings did not seem to update. Anyone else having this problem?

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone please tell why am I getting Memory Limit Exceeded in Problem E? I am just using a 2D Array. Link to my submission :- https://mirror.codeforces.com/contest/1703/submission/163908463

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello sir, There are two layers of recurrence in your code, so your code's time complexity is $$$O(n^2)$$$, and when $$$n = 200000$$$,you will get TLE.

    I solved this problem with set, and my time complexity is $$$o(n \log n)$$$.

    This is my code:

    # include <bits/stdc++.h>
    #define ll long long
    #define re register
    #define il inline
    using namespace std;
    string s[100010];
    int main()
    {
    	int t;
    	scanf("%d", &t);
    	while (t--)
    	{
    		int n; bool f = 0;
    		scanf("%d", &n);
    		set <string> str;
    		for (int i = 1; i <= n; ++i)
    		{
    			cin >> s[i];
    			str.insert(s[i]);
    		}
    		for (int i = 1; i <= n; ++i)
    		{
    			f = 0;
    			for (int j = 1; j < s[i].size(); ++j)
    			{
    				string a = s[i].substr(0, j), b = s[i].substr(j, s[i].size());
    				if (str.find(a) != str.end() && str.find(b) != str.end())
    				{
    					printf("1");
    					f = 1;
    					break;
    				}
    			}
    			if (f == 0) printf("0");
    		}
    		printf("\n");
    	}
    	return 0;
    }
    
    

    Although there are two lawers of recurrence in my code, but $$$s[i].size \le 8$$$, so my code doesn't go TLE.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey, Thanks for the reply but I am asking about Problem E, Mirror Grid. The solution that you have explained is Problem D, Double Strings.

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You are creating new 2D array every test case.

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you so much for replying. Can you tell what should be approach for this problem?

      • »
        »
        »
        »
        2 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        To be honest I didn't solve this problem and now I don't have time now because the contest starts in 2 minutes.

        To fix your problem (MLE) you can create 2D array before first test case. (before while (t > 0) line)

    • »
      »
      »
      2 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Because in the editorial they are also creating a 2D array for each test case.

»
2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I solved F in O(n) Here is my solution: 163897273

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Good solution for problem G!

»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone suggest more problems similar to G?(like DP states like this)

»
2 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Deleted

»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In G, reason why we have to iterate over all dp array instead of only go through dp[n][0-32] is that during the transferation of dp array, once the second dimension hit the boundary, we would lose one stratey, which is using the bad key. Because we were supposed to do dp[i][33]=dp[i-1][33-1]+a[i]>>32(or 33?im not sure), but the boundary force us to only do dp[i][32]=dp[i-1][31]+a[i]>>32(?)-k, which is using the good key, taking all the cost painfully. so u see how the bad key strategy is lost during the process, besides iterating all dp array, we can also do dp[i][j]=dp[i-1][j-1] when a[i]>>j==0.

»
13 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

is there a formula shows where cell i,j maps to when rotate 90, 180, 270 degrees in problem E?

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

// By: TESFAMICHAEL TAFERE

include <bits/stdc++.h>

using namespace std;

int main() { int n;

cin >> n;
string s;
while (n--)
{
    cin >> s;
    // transform(s.begin(), s.end(), s.begin(), ::toupper);
    //  if (s.compare("YES") == 0)
    //      cout << "YES\n";
    //  else
    //      cout << "NO\n";

    // The time complexity for transform() is O(n) where n is the length string.
    // we can do this in O(1) by the following

    if (s.compare("YES") == 0)
    {
        cout << "YES\n";
    }
    else if (tolower(s[0]) == 'y' && tolower(s[1]) == 'e' && tolower(s[2]) == 's')
        cout << "YES\n";
    else
        cout << "NO\n";
}
return 0;

}