Quickly

Thanks for fast tutorial

Amazing contest !! ..E is tricky one!

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.

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

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

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

Problem G was a good one.

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

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

Can F be solved by Fenwick tree??

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.

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

why this solution 163935126 giving TLE ? Anybody please help

why my dp solution doesn't work for G https://codeforces.me/contest/1703/submission/163929073

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

I learn some new thing from problem G

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

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

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]))

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

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

Thanks for the fast editorial

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...

Simple recursive DP solution for G here.

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

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

Video Solutions of complete problemset.

F can be solved in linear time. submission

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

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://codeforces.me/contest/1703/submission/163908463

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

Good solution for problem G!

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

Deleted

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.

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

// 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;

}