Codeforces Round #946 (Div. 3) Разбор

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

№	Пользователь	Вклад
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	Dominater069	153
9	nor	153

1974A - Рабочий стол телефона

Разбор

Решение

nt = int(input())
 
for t in range(nt):
    line = input()
    x, y = [int(q) for q in line.split()]
    mm = (y + 1) // 2
    x -= (mm * 5 * 3 - y * 2 * 2)
    x = max(x, 0)
    mm += (x + 5 * 3 - 1) // (5 * 3)
    print(mm)

1974B - Симметричное кодирование

Идея: MikeMirzayanov

Разбор

Решение

def solve():
    n = int(input())
    b = input()
    cnt = [0] * 26
    for c in b:
        cnt[ord(c) - ord('a')] = 1
    tmp = ''
    for i in range(26):
        if cnt[i] > 0:
            tmp += chr(ord('a') + i)
    a = ''
    for c in b:
        a += tmp[-1 - tmp.find(c)]
    print(a)
    
 
for _ in range(int(input())):
    solve()

1974C - Красивые пары троек

Идея: MikeMirzayanov

Разбор

Решение

def solve():
    n = int(input())
    a = [int(x) for x in input().split()]
    cnt = dict()
    ans = 0
    for i in range(n - 2):
        triplet = (a[i], a[i + 1], a[i + 2])
        mist = [0] * 3
        mist[0] = (0, a[i + 1], a[i + 2])
        mist[1] = (a[i], 0, a[i + 2])
        mist[2] = (a[i], a[i + 1], 0)
        for trip in mist:
            ans += cnt.get(trip, 0) - cnt.get(triplet, 0)
            cnt[trip] = cnt.get(trip, 0) + 1
        cnt[triplet] = cnt.get(triplet, 0) + 1
    print(ans)
    
    
for i in range(int(input())):
    solve()

1974D - Ingenuity-2

Идея: MaxBuzz

Разбор

Решение

inv = {'N':'S', 'S': 'N',
    'E': 'W', 'W': 'E'}

def solve():
    n = int(input())
    s = input()
    x, y = 0, 0
    for c in s:
        if c == 'N':
            y += 1
        if c == 'S':
            y -= 1
        if c == 'E':
            x += 1
        if c == 'W':
            x -= 1
    if x % 2 == 1 or y % 2 == 1:
        print('NO')
        return
    ans = ['R'] * n
    if x == y == 0:
        if n == 2:
            print('NO')
            return
        ans[0] = ans[s.find(inv[s[0]])] = 'H'
    else:
        for i in range(n):
            if s[i] == 'N' and y > 0:
                y -= 2
                ans[i] = 'H'
            if s[i] == 'S' and y < 0:
                y += 2
                ans[i] = 'H'
            if s[i] == 'E' and x > 0:
                x -= 2
                ans[i] = 'H'
            if s[i] == 'W' and x < 0:
                x += 2
                ans[i] = 'H'
    print(*ans, sep='')
    
    
for _ in range(int(input())):
    solve()

1974E - Деньги покупают счастье

Идея: RobinFromTheHood

Разбор

Решение

T = int(input())
big = float('inf')
for _ in range(T):
    m, x = map(int, input().split())
    c = []
    h = []
    for i in range(m):
        ci, hi = map(int, input().split())
        c.append(ci)
        h.append(hi)
    mh = sum(h)
    dp = [0] + [big] * mh
    for i in range(m):
        for j in range(mh, h[i]-1, -1):
            if dp[j-h[i]] + c[i] <= i*x:
                dp[j] = min(dp[j], dp[j-h[i]]+c[i])
    for i in range(mh, -1, -1):
        if dp[i] != big:
            print(i)
            break

1974F - Игра с отрезанием

Идея: MikeMirzayanov

Разбор

Решение

def solve(tc):
    a, b, n, m = map(int, input().split())
    ver, hor = [], []
    for i in range(n):
        x, y = map(int, input().split())
        ver.append((x, y))
        hor.append((y, x))
    deleted = set()
    hor.sort()
    ver.sort()
    ans = [0, 0]
    u, d = 1, a
    l, r = 1, b
    hl, hr = 0, n - 1
    vl, vr = 0, n - 1
    for i in range(m):
        c, k = input().split()
        k = int(k)
        if c == 'U':
            u += k
            while vl <= vr and ver[vl][0] < u:
                if ver[vl] not in deleted:
                    ans[i % 2] += 1
                    deleted.add(ver[vl])
                vl += 1
        if c == 'D':
            d -= k
            while vl <= vr and ver[vr][0] > d:
                if ver[vr] not in deleted:
                    ans[i % 2] += 1
                    deleted.add(ver[vr])
                vr -= 1
        if c == 'L':
            l += k
            while hl <= hr and hor[hl][0] < l:
                if (hor[hl][1], hor[hl][0]) not in deleted:
                    ans[i % 2] += 1
                    deleted.add((hor[hl][1], hor[hl][0]))
                hl += 1
        if c == 'R':
            r -= k
            while hl <= hr and hor[hr][0] > r:
                if (hor[hr][1], hor[hr][0]) not in deleted:
                    ans[i % 2] += 1
                    deleted.add((hor[hr][1], hor[hr][0]))
                hr -= 1
    print(ans[0], ans[1])


t = int(input())
for i in range(1, t + 1):
    solve(i)

1974G - Деньги теперь покупают меньше счастья

Идея: RobinFromTheHood, izban, Aksenov239

Разбор

Решение

from heapq import *
for _ in range(int(input())):
    m, x = map(int, input().split())
    c = [int(x) for x in input().split()]
    budget = 0
    Q = []
    for i in c:
        if budget >= i:
            heappush(Q, -i)
            budget -= i
        elif Q and -Q[0] > i:
            budget += -heappop(Q)-i
            heappush(Q, -i)
        budget += x
    print(len(Q))

#define int long long int n; cin >> n; vector<int> nums(n, 0); for (int i = 0; i < n; i++) cin >> nums[i]; int ans = 0; map<int, map<int, int>> mp1,mp2,mp3; map<int, map<int, map<int, int>>> mp; for (int i = 0; i < n - 2; i++) { ans += mp1[nums[i]][nums[i + 1]] + mp2[nums[i]][nums[i + 2]] + mp3[nums[i + 1]][nums[i + 2]] - 3*mp[nums[i]][nums[i + 1]][nums[i + 2]]; mp1[nums[i]][nums[i + 1]]++; mp2[nums[i]][nums[i + 2]]++; mp3[nums[i + 1]][nums[i + 2]]++; mp[nums[i]][nums[i + 1]][nums[i + 2]]++; } cout<<ans<<endl;

map<pair<int, int>, int> mp; int sol( int j, int l, int x, vector<array<int, 2>>& v ){ if( j >= v.size() ) return 0; if( mp.count( { j,l } ) ) return mp[ {j, l} ]; int res = sol( j + 1, l + x, x, v ); res = sol( j + 1, l + x, x, v ); if( l >= v[ j ][ 0 ] ) res = max( res, v[ j ][ 1 ] + sol( j + 1, l + x - v[ j ][ 0 ], x, v ) ); return mp[ {j, l} ] = res; } void __(){ int n, x; scan( n, x ); vector<array<int, 2>> v( n ); for( int i = 0; i < n; i++ ){ scan( v[ i ][ 0 ], v[ i ][ 1 ] ); } int ans = sol( 0, 0, x, v ); print( ans ); mp.clear(); cout << "\n"; }

#include <bits/stdc++.h> #include <iostream> #include <vector> #include <string> #include <set> #include <cmath> #include <unordered_map> #include <cctype> #include <algorithm> using namespace std; #define ll long long int int main(){ int t; cin >> t; while (t--) { int n; cin >> n; vector<int> a(n); for(int i=0; i<n; i++) cin >> a[i]; ll ans = 0; for(int j=0; j<3; j++){ map<pair<int,int>, vector<int>> check; for(int i=0; i<n-2; i++){ if(j == 0){ check[{a[i+1], a[i+2]}].push_back(a[i]); }else if(j == 1){ check[{a[i], a[i+2]}].push_back(a[i+1]); }else{ check[{a[i], a[i+1]}].push_back(a[i+2]); } } for(auto x:check){ int count = 1; vector<ll> count_push; sort(x.second.begin(), x.second.end()); for(int i=1; i<x.second.size(); i++){ if(x.second[i-1] == x.second[i]){ count++; }else{ count_push.push_back(count); count = 1; } } count_push.push_back(count); ll val = accumulate(count_push.begin(), count_push.end(), 0LL); for(auto y:count_push){ ans -= y*(y-1)/2; } ans += (x.second.size()*(x.second.size()-1))/2; } } cout << ans << "\n"; } }

#include<bits/stdc++.h> using namespace std; #define ll long long int mod=1000000007; void solve(){ int m,x; cin>>m>>x; vector<int> cost(m,0),hap(m,0); for(int i=0;i<m;i++){ cin>>cost[i]>>hap[i]; } unordered_map<int,int> mp; mp[0]=0; set<int> s; s.insert(0); for(int i=0;i<m;i++){ int money=x*i; int k=mp[-1*(*s.lower_bound(-1*money))]; int spent=-1*(*s.lower_bound(-1*money)); if(cost[i]<=money){ int k1=hap[i]+mp[-1*(*s.lower_bound(-1*(money-cost[i])))]; if(k1>k){ spent=-1*(*s.lower_bound(-1*(money-cost[i])))+cost[i]; } k=max(k,k1); } mp[spent]=k; s.insert(-1*spent); } cout<<mp[-1*(*s.lower_bound(-1*(x*(m-1))))]<<endl; } int main(){ cin.tie(0)->sync_with_stdio(0); int t=1; cin>>t; while(t>0){ solve(); t--; } }

Комментарии (122)

Написать комментарий?

Thyl

6 месяцев назад, # |

Thanks for the contest ! Good Problems !

→ Ответить

RobinFromTheHood

← Rev. 2 →

+38

Thank you for the excellent coordination and organization! I joked about physicists because I am one :)
Please encourage all physicists to code!

eshetumartha294

6 месяцев назад, # ^ |

guys... In problem C why are we subtracting count of triplets form answer (- cnt.get(triplet, 0) ) from our answer each time we add cnt.get(trip, 0) ?

aaradhyakul

if 111 has already been come accross, then the cnt dict already contains extra 110,101 and 011 corresponding to it. These three triples should not be counted as beautiful if we come across 111 again.

dinyeah

To avoid counting same triplets as a beautiful pair. For example, if you are currently dealing with the triplet "321" then you are inserting 301, 021, 320 and 321 itself into the cnt dictionary. Now, if you come across "321" again in the array then "321" and "321" should not be counted as a beautiful pair. So you have to subtract the count of same triplets.

kiato_kid_2008

Thanks for the good contest Graet Problems

ZhockDen

Problem C was quite tough than average!! Acceptance rate is less than 50%. Anyways another good round by Vladosiya

Kai_007

I would rather say C and D should be swapped in terms of difficulty.

ankitlal

← Rev. 3 →

+18

Simplest Implementation for Problem D

void solve(int test)
{

    int n;
    cin >> n;

    string s, ans;
    cin >> s;

    map<char, int> mp, turn;

    for (auto e : s)
        mp[e]++;

    if ((mp['N'] + mp['S']) % 2 != 0 || (mp['W'] + mp['E']) % 2 != 0)
    {
        no;
        return;
    }

    if (n == 2 && (mp['N'] == 1 || mp['W'] == 1) )
    {
        no;
        return;
    }

    turn['E'] = 1, turn['W'] = 1;

    for (auto e : s)
    {
        if (turn[e] % 2)
            ans += 'H';

        else
            ans += 'R';

        turn[e]++;
    }
    cout << ans << "\n";
}

retinue

This is really clean. I was thinking the same idea but it turned out to be way complicated when I actually coded it. Thank you!

_Charan

can someone explain Q3 solution?

AkiLotus

+16

For a more functional explanation: to avoid redundant counting, we'll iterate once through every triplets, count every triplet to the left of it that would make a beautiful pair.

In notation, denoting $$$cnt(x)$$$ is the current counter for triplet $$$x$$$, then for each triplet $$$(a_i, a_{i+1}, a_{i+2})$$$ being iterated:

Add $$$cnt((0, a_{i+1}, a_{i+2})) + cnt((a_i, 0, a_{i+2})) + cnt((a_i, a_{i+1}, 0))$$$ to the final answer. This is the process of pairing the current triplet with the ones before it that have at most one error.
Still, we need the two triplets to have precisely one error actually. So the completely identical pair(s) must be excluded. Therefore, subtract $$$3 \times cnt((a_i, a_{i+1}, a_{i+2}))$$$ from the final answer. The constant factor $$$3$$$ was because if there were any such element, they would have been counted $$$3$$$ times at the previous steps.
Add $$$1$$$ to $$$cnt((a_i, a_{i+1}, a_{i+2}))$$$, $$$cnt((0, a_{i+1}, a_{i+2}))$$$, $$$cnt((a_i, 0, a_{i+2}))$$$ and $$$cnt((a_i, a_{i+1}, 0))$$$. This is to include the current triplet to be counted at further iterations.

Take the 8th test in the sample:

5
2 1 1 1 1

We'd have three triplets, $$$(2, 1, 1)$$$, $$$(1, 1, 1)$$$ and $$$(1, 1, 1)$$$, and initially $$$ans = 0$$$.

Iterate through the first. It's obvious that answer remains at $$$0$$$ because there's nothing to the left of it to pair with. Still, after this, $$$cnt((2,1,1))=cnt((0,1,1))=cnt((2,0,1))=cnt((2,1,0))=1$$$.
Iterate through the second. We can add $$$cnt((0,1,1))+cnt((1,0,1))+cnt((1,1,0))=1+0+0=1$$$ to the final answer, thus now $$$ans = 1$$$. Also, now $$$cnt((2,1,1))=1$$$, $$$cnt((1,1,1))=1$$$, $$$cnt((0,1,1))=2$$$, $$$cnt((2,0,1))=cnt((2,1,0))=cnt((1,0,1))=cnt((1,1,0))=1$$$.
Iterate through the third. We add $$$cnt((0,1,1))+cnt((1,0,1))+cnt((1,1,0))=2+1+1=4$$$, yet we have to subtract $$$3 \times cnt((1,1,1)) = 3 \times 1 = 3$$$, therefore final answer is $$$2$$$.

vinayakverma290605

thanksbuddy,, i understood the editorial of C only after reading ur explanation

redraven

5 месяцев назад, # ^ |

Hey! do we have to consider duplicates? like if there are 5 occurences for a triplet {a,b,c} and {0,b,c} occurs 2 times, Will it be 5*2?

ritesh_gupta97

For Task 5, my recursive code works fine, but on memoizing, it gives a different answer on the last sample case, Why is this happening, and how to rectify it?

MyCode E

int rec(vi &c, vi &h, int cur_mon, int m, int salary, int x, int happiness, vvi &dp){
    if(cur_mon>m)   return 0;

    if(dp[cur_mon][happiness]!=-1) return dp[cur_mon][happiness];
    int op= rec(c,h,cur_mon+1, m, salary+x, x, happiness, dp);

    if(salary>=c[cur_mon]){
        op= max(op, h[cur_mon] + rec(c,h,cur_mon+1, m, salary-c[cur_mon]+x, x, happiness+h[cur_mon],dp));
    }
    return dp[cur_mon][happiness]=op;
    // return op;
} 

void solve(int test)   
{
    debug(test)
    int m, x;   cin>>m>>x;
    vi c(m+1,0), h(m+1,0);
    rep(i,1,m)  cin>>c[i]>>h[i];

    vector<vector<int>> dp(m+1, vector<int>(50001,-1));
    cout<<rec(c,h,1,m,0,x,0, dp)<<nline;
    
}

Roronoa__Zoro

There are 3 changing states in your code i,e curr_month , happiness , salary but the dp you have created is consisting of only 2 variables.

Got it, now I tried two other approaches: Both get TLE at 10 Case 262001589 262002708, Can you please look into this and help?

navneetk12

For a 3-D dp, the number of states are too much to pass the case 10. hence it fails

Shouldn't it pass with map, it will store only feasible combinations? 50(m)*50(type of h)*50(type of rem salary) = 1.25*1e5

How can the tc be 50*50*50. There are 50 months and the number of ways to choose them are 2^50 . The upper bound of your code can be (50 *1e8 * 1e3) . But due to memoization it will be lower than that. Lets suppose all of the values of costare such that sum of any subset taken will be different then there will be large number of different values of cost so your map will have a huge amount of keys . But as we can see the happiness is 1e3 at max , so the total happiness can be upto 50 * 1000 ie 5e4 (where as cost can change upto 1e8 * 50) . So somehow you need to make your dp dependent on only index and happiness at max.

Oh, you are right.

I was struggling with the same issue for over a couple of hours, I recommend 261999415, there's a minor constraint that u need to consider.

If for a particular happiness value, If we have more amount with me in some other recursive call, i need not implement my current recursive call with a lower amount left with me, because that shall cause an issue in the future.

Because we have 3 parameters to consider, we have to consider also the amount that we spend for a particular index with particular happiness value, for which i have used the sp matrix.

Hope that helps !

sankooru14

here what do you mean by issue in future? can you explain it further?

also can you find out error in my code?262040594

SuperMo

salary can get up to 1e9 so we can't store it as a state, I'm not quite sure yet but I think this classical problem will help you solve E : https://atcoder.jp/contests/dp/tasks/dp_e

it's knapsack but with a technique called dimension rotation

Nurali16

It 's sad that we didn 't even have time to read the problem 1974E - Money Buys Happiness, because of the long code in 1974D - Ingenuity-2 . Despite this, the problems were very good.

par4dox

I wonder how submissions increases rapidly in the last half hour

flaemo

I wonder !

-2.71

Python Forces ! , Thanks Vladosiya

Mehul_Gupta

In my opinion, questions were really good, but quite implementation based (at least in C++).

red.frost24

Here's an alternate solution for problem C using only sorting: solution (C++)

The solution is not so fast since I have used sorting 3 times, but it is nonetheless O(n logn)

vstiff

Sorting 3 times is fast (proof: 261990288), passing vector of vectors to calc is slow

ohhh shoot

I can't believe I passed vector by value. I realized that just now. Wrote many c++ programs but never made that mistake, and today I did it TT.

This solution deserved to TLE. Thank you for pointing out the real bottleneck of the solution, I need to be a lot more mindful next time onwards, ig.

manyu19

we can also apply principle of exclusion and inclusion by help of nested maps but that can be space inefficient solution but here it worked.

sajid_01

tuple can be used instead of in nested map mp, storing the exact same triple: map<tuple<int, int, int>, int> similar;

Thanks for your valuable suggestion

thuctapsinh

Thank you so much! Tuple make my code much simpler. I don't know why my first implement of my idea using map<string, int> wrong answer on test 7. Then I implement the same idea with map<tuple<int, int, int>, int> and got accept. I'm really confused. Here is two version of my code 262693385 and 262688887, Could someone please point out my mistake in version of the code that uses map<string, int>?

BetaHarshith

In question C , it is given 4 seconds , as per what i know one second has 10^8 iterations , so 4 sec should have 10^32 iterations and max n value is 2*10^5 , so n^2 soln at worst has 4*10^10 iterations and max testcases are 10^4 so an overall T.C of 4*10^14 which is approx 2 sec , but why n^2 solns got failed , im just curious , i did using map ,but got tle in bruteforce , please correct me if i am wrong .

Aditya8676

+10

in 4 seconds, we should have atmost 4*(10^8) iterations not 10^32.you had done mathematical error.

djm03178

If you're assuming 1 second = $$$10^8$$$, then 4 second is $$$4 \times 10^8$$$, not $$$10^{32}$$$. $$$10^{32}$$$ is 1000000000000000000000000 times larger than $$$10^8$$$.

my bad , sorry for wrong calculation , lol all these days i was doing wrong calculation .

rpmdoestuff

Problem G has to be Antimatter Dimensions-inspired. Which one of you writers plays the game?

Wasif_Shahzad

my solution to d which was the most troll solution I've ever written. I just brute-forced while trying to have device 2 follow the path of device 1. I was very unsure of it passing but it somehow got AC. Can someone please help in formal proof (not mathematical) of why this works? submission: 261894801

try_my_hardest

hahaha I think that's very funny, especially because I did basically the same thing. You can think of it this way, the two objects alternate between accepting each type of instruction. It might be easier to understand with my code. 262066699

So there are four (but only two that pass) cases when we restrict ourselves to one dimension, either y or x, let's just choose y for now. So the amount of upwards instructions is either even or odd, and the amount of downwards instructions is also either even or odd. Ignoring the two cases where they have opposite parities, there are two cases left, where they are either both even or both odd. If they are both even, they will obviously end up at the same point, they will both receive the same amount of instructions. Then, there is the case where both instructions are odd. If the first object takes one extra up and one extra down instruction, it essentially doesn't move, and we now have an even amount of upwards and downwards instructions, which just reduces to our first case. We can also apply the same logic to the x dimension, leading to the solution.

TheSensei

Can someone explain to me, why my code for Problem C is giving WA on test case 8, it got accepted during the contest, but failed in System testing.

261837444

ans-=j.second*j.second;

Those lines in your code seem to be very questionable overflows (as the map key/values are all pair<int, int>, tested with C++17 32bit to make sure int is 32bit). Resubmitting with pair<ll, ll> passed that test.

I don't really know how it escaped the original testset.

Quick fix without changing data type:

ans-=1LL*j.second*j.second;

1e3bonzakura

+12

Anyone else used Segment Trees on problem G?

It's a bit of an overkill, but it was my first idea and it worked.

ogfemboy

yea even i felt seg tree was the most instictive solution, but turned out the problem was pretty simple

Hamza_Refai

Good Problems!

destroyer_sam

problem E is exactly same as Knapsack -2 from Atcoder dp contest. Just add the extra condition: on any given month , if minimum cost required to come up with happiness h should be less than the money earned till the previous month.

Check out my submission here : 261998965.

Yup its state rotation idea

rishiraj1905

https://codeforces.me/contest/1974/submission/266618059 can u help me where i am going wrong

demitronization

can you please tell me what am i doing wrong here??

Code below

ll rec(int i, int hap, vl &c, vl&h, vector<vector<int>> &dp, int x){
    if(hap==0){
        return 0;
    }
    if(i<0){
        return 1e10;
    }

    if(dp[i][hap]!=-1){
        return dp[i][hap];
    }

    ll take = 1e10;
    if(h[i]<=hap){
        take = c[i] + rec(i-1, hap - h[i], c,h,dp,x);
        if(take>=x*(i-1)){
            take=1e10;
        }
    }

    ll dont = rec(i-1,hap,c,h,dp,x);

    dp[i][hap] = min(take,dont);

    return dp[i][hap];

}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    gin(t);
    while (t--)
    {
        lin2(n,x);
        vl cost, hp;
        ll sum=0;
        loop(i,0,n){
            lin2(a,b);
            cost.pb(a);
            hp.pb(b);
            sum+=b;
        }

        vector<vector<int>> dp(n+1, vector<int> (sum+1,-1));
        ll ans=0;
        
        revloop(i,sum,0){
            if(rec(n-1,i,cost,hp,dp,x) <= (x*(n-1))){
                ans= i;
                break;
            }
        }
        cout<<ans<<endl;
        // Always check if the input is 2n
    }
    // cout<<fixed<<setprecision(10);
    // cerr<<1000*((double)clock())/(double)CLOCKS_PER_SEC;
}

you need to check the following:

if(min(take,dont)>i*x)return dp[i][hap] = 1e10;

I think this could solve the issue for now.

However, I guess recursive solution is giving TLE. I did bottom-up and that got accepted

Hey I have used the same concept as knapsack 2 only but did using recursion...but I am getting wrong answer on test case 14... Can you help me in finding out the error? 262061702

replace INT_MAX with 1e15.

got it!!thanks!

vatsal3812

In the same code, if I go from i 0 to n-1 instead of n-1 to 0, I get wrong answers for input 1 only. Why this is happening? Can you please help.

RANJAN888

I need help with time complexity Since m is 50,and no. of testcases are 1000. Sum of m over all testcases should be 5e4 which after multiplying with 1e5(sum of Σh over all testcases) comes out to be 5e9. And 5e9 should give TLE.

https://codeforces.me/contest/1974/submission/266618059 can u help where i am going wrong

Anas986

Hi everyone, can someone explain the idea behind how we would arrive at this solution? Specifically why theres a mp['W'] + 1 and mp['E'] + 1? and not for N and S?

void solve() { ll n; cin >> n; string s; cin >> s; map<char, ll> mp, rover; lp(i, n) mp[s[i]]++; if ((mp['S'] + mp['N']) % 2 == 0 && (mp['E'] + mp['W']) % 2 == 0 && (n > 2 || s[0] == s[1])) { rover['N'] = mp['N'] / 2; rover['S'] = mp['S'] / 2; rover['W'] = (mp['W'] + 1) / 2; rover['E'] = (mp['E'] + 1) / 2; lp(i, n) { if (rover[s[i]] > 0) cout << 'R'; else cout << 'H'; rover[s[i]]--; } cout << endl; } else { cout << "NO" << endl; } }

raghavmadan1034

One of the concise and clear implementation of problem D-

Spoiler

#define ll long long
#define pb push_back
int main(){
    ll t;
    cin>>t;
    while(t--){
        ll n;
        cin>>n;
        string s;
        cin>>s;
        vector<ll>u;vector<ll>d;vector<ll>e;vector<ll>w;
        vector<vector<ll>>mega;
        for(ll i=0;i<n;i++){
            if(s[i]=='N')u.pb(i);
            if(s[i]=='W')w.pb(i);
            if(s[i]=='E')e.pb(i);
            if(s[i]=='S')d.pb(i);
        }
        if((u.size()+d.size())%2==0 && (w.size()+e.size())%2==0){
            string ans=s;
            if(u.size()%2==1){
                ans[u[u.size()-1]]='R';
                ans[d[d.size()-1]]='R';
                u.pop_back();d.pop_back();
            }
            if(e.size()%2==1){
                ans[e[e.size()-1]]='H';
                ans[w[w.size()-1]]='H';
                e.pop_back();w.pop_back();
            }
            mega.push_back(u);mega.push_back(d);mega.push_back(e);mega.push_back(w);
            for(ll i=0;i<4;i++){
                for(ll j=0;j<mega[i].size();j++){//mega[i] is nothing but u,d,w,e
                    if(j>=mega[i].size()/2){
                        ans[mega[i][j]]='R';
                    }
                    else ans[mega[i][j]]='H';
                }
            }
            ll flagr=0,flagh=0;
            for(ll i=0;i<n;i++){
                if(ans[i]=='R')flagr=1;
                if(ans[i]=='H')flagh=1;
            }
            if(flagr==0||flagh==0)cout<<"NO"<<endl;
            else cout<<ans<<endl;
        }
        else{
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

devvikram22

why this gives TLE on case 10 — Problem E

kingm01

5th question me DP itna aasaan tha ki me agle Janam me bhi naa kar paun(laughing emoji-2)

formidablechief27

Questions C and D Detailed Video Editorial

English

C : https://youtu.be/wGj3J4W50HA

D : https://youtu.be/c6U-YiF0MCo

Hindi

C : https://youtu.be/8Sd-qodaa7w

D : https://youtu.be/hduAMjuv9co

jzavaglia

The statement for F is really easy to misread. The problem statements use (x, y) variables for (row, columns)

Given we're cutting on left and right, one would expect that was against the x variable, but it is against the y variable, and up / down cuts are against the y variables. I'll be more careful when reading, but that is slightly unfriendly to the reader.

Ayanokoji7

Easiest G ever:)

Kenshi01

In question F, my approach was to keep track of every y coordinate containing a chip for each row(same for column) in vectors, and maintain two pointers for rows and columns. And if there is a row being erased(similarly for column), I applied binary search to get the index of smallest and largest indices within the range bound by the two pointers for columns, to add to the scores.

But the submission is giving memory-limit-exceeded. 262010194

Can anyone identify the reason, I think the total space I am using is in order the O(n).

row[x1].size()>0

Be extra careful at such lines. If x1 isn't yet in the map, the map will allocate a new "block" of memory for that key, and thus as time goes on, it'll keep populating until MLE.

That doesn't yet consider the fact that for(int j=0; j<sh; j++) will TLE eventually (as the sum of sh in each test can reach $$$2 \cdot 10^9 - 2$$$ at maximum), but usually MLE will come first if possible anyway.

BinaryThinker

Hey Vladosiya

It appears there's an issue in the tutorial where the directions for how N and S affect the variable y are incorrectly stated. The current explanation mentions that N decreases y by 1 and S increases y by 1. However, N should increase y by 1 and S should decrease y by 1.

Thanks.

MaxBuzz

Actually it does not really matter, as long as everything is consistent in the code. Swapping the directions just mirrors the picture, but does not change whether a certain answer is correct or not.

But surely the NS-polarity does not agree with the attached solution (while the tutorial is supposedly an adaptation of my original analysis, the solution is not mine), so, Vladosiya, it is definitely better to make these the same.

Explanation for problem E -

You can observe that it is similar to classic knapsack but the constraints are different. here the maximum salary you can get is (m-1)*x which is nearly 1e8 range..so you can't store it as state. So now you have to see the problem in another way.. i.e. you know what is the maximum happiness you can get and i.e equal to sum of all happiness now you have to start from this maximum value of happiness till zero see for which happiness you got cost <=((m-1)*x)..and return it as answer so here your states will be f(index,happiness)

Caution :

Don't use memoization.. you will get TLE.. try to use tabulation method For reference you can check my submission 262090006 For reference video you can check out this (but in hindi language) — video

Ylandolsi

recusrive with memo accepted ! https://codeforces.me/contest/1974/submission/262148270

rishiraj729

https://codeforces.me/contest/1974/submission/266602354 why this is giving wrong answer can u help me plz

ustaad_bismillah

Please share the editorial solutions in C++ too.

shreyaskumar24

I got MLE in problem E. I'm using memoization to calculate the max happiness. Can anyone help me in optimizing the Memory in my code?

262108607

Kaleem_Raza_Syed

You are defining some dp[m][m * x], although m <= 50, but x is too large x <= 10 ^ 8. You are in total allocating m ^ 2 * x ints, which take a memory of (4 * 50 * 50 * 10^8)B = 1000GB.

yanguo

Who can teach me g questions orz. I can not understand the solution.(qwq)

bkchodi

-12

the question G is a modification of question E, but in this case the happiness values is assigned 1.

My algorithm: I used a greedy algorithm for solving the problem. I bought happiness in the current month and added it to my bought list. If at any month I am not able to afford it, then I removed the most expensive happiness from by bought list (i.e. not bought it).

Submission 262189832

JIUZHE666

good contest!

SlavaG

I am confused with Task-C and Kotlin.

Don't understand why this is TL https://codeforces.me/contest/1974/submission/262119536

and this is OK. https://codeforces.me/contest/1974/submission/262120101

The only difference is in keys of map. In the first case it is data class(x,y,z), in the seconde it is String "$x_$y_$z". For some reason solution with data class works very slow. Any guru of kotlin for help?

Also find out that this solution works https://codeforces.me/contest/1974/submission/262121710

Looks like test 14 is direct attack on default hashcode implementation. Is it intended? What is the good way to avoid such problems in future solutions? Should I not use data classes as keys?

AvaraKedavra

For problem E, Why does this code 262139086 TLE on test 14 ? It uses the same idea as in the editorial and has the same time complexity.

esod04

maybe due to the fact the j loop is going till 50000 instead of the sum of maximum happiness , have seen a similar problem happen to another user

yeah, but in the worst case, won't the sum of maximum happiness be around 50000 ?

yeah but the maximum sum of happiness over all test cases has an upperbound given by 10^5 as written in the last statement in the problem . Iterating over 50000 over a 1000 test cases breaches that limit , so taking the worst scenario every time doesn't help us here

Got it. Thanks !

copyPasteCoder

custom mashup I created a private mashup for it where i submitted 262139086, it took 15 sec.

Insightful

prime_Rick

can questions added in private mashups bypass the time limit ??

Hassan_Fathi

For those stuck in G, here's the same idea 105123E - Powerhouse of the Cell?

stoppppittttadiiii

someone please suggest the sources you practise problem e. and similar ones for practising dp.im a newbie here want to learn dsa first.

there is no fast learning , atcoder educational dp contest is good

Recursive dp for E :

https://codeforces.me/contest/1974/submission/262148270

thanks its really more easy to understand

https://codeforces.me/contest/1974/submission/266666722 why this is not working can u explain?

iwontfakeit

hey MikeMirzayanov what is this partial behaviour towards flagging solutions.

This user -> looneyd_noob is out of competition for the solution: https://codeforces.me/contest/1974/submission/261894175 but i also noticed the solution of this user -> Shaxx19 who is not out of the solution even having a very similar solution just variable name changed and some comments added and even submitted 10 minutes later; this is his solution https://codeforces.me/contest/1974/submission/261900757 the entire nested for loop is same with same indentation. Man he needs to get out of contest, you are doing very wrong and people's trust will reduce from this platform. Please get him out of competition.

Shaxx19

I noticed that someone has raised concerns regarding the similarity between my solution and another user's solution, and is requesting my disqualification from the competition.

I would like to clarify that my solution is indeed my own work. Any similarities to other submissions are purely coincidental, as the nature of coding often leads to similar logic and structures when solving the same problem. I have added proper comments to demonstrate my understanding of the code, which the other user hadn't.

bro there is no body coding and naming names likes this , offldfjsdlfj

it s very obvious that u sent ur solution to that guy and he made some modfication too avoid getting kicked out

skyEmperor_KA

Can anyone tell me, what's wrong in my submission of Que (E) {https://codeforces.me/contest/1974/submission/262210794}

F was a simple binary search problem if you are aware of 2D coordinates to 1D conversion trick.Submission

Sir custom hash make the operatin of unordered map always o(1) ?

It prevents your code from getting hacked by avoiding collisions while hashing. More Info

knm2005

Are there any good problems similar to this round C problem. I felt this is very unconventional in recent times

NokSyte

Task F huge plus plus Mann

Victor_Luis123

Could anyone explain me how to implement Problem G using segment trees? I did'nt understand that part in the editorial

nishant.dqy

My code for Q.C is failing on testcase 7 can anyone tell why:

Musaddiq

why could my knapsack solution be failing on E? My solution

Soumik_M

Can someone write a solution in C++ for Qo C There is no suitable hash function in unordered map for a tuple in C++ !

You can just use vector instead tuple and it will work without coding a hash function. In fact you can just use a pair for this problem so it exists a hash function in the STL :)

solution of c blowed my mind ,,never though of using map this way

Maxilla_0IQ

What will your expression after finding wrong answer on 1601th line of problem A?

techie-arpit

isn't the time complexity of solution of f given is O(m*n) ?

pagol

3 месяца назад, # ^ |

n+m

manmeet_ki_muskan

5 месяцев назад, # |

can anyone help me in writing the recursive dp code for the problem E? its similar to knapsack 2 of atcoder but the thing that is troubling me is in knapsack problem we have a constant capacity w but here w is the salary that is getting changed continously.So, unable to handle it. any kind of help is welcomed.

https://codeforces.me/contest/1974/submission/266665941 can u explain why this is working and this not https://codeforces.me/contest/1974/submission/266666722

hshekhar_0802

In the fifth question, I have implemented a somewhat different dynamic programming technique than suggested using an unordered_map and set. I have iterated through months 1 to n and during each iteration, I have updated the dp table using the following idea: Define following variables:
money: Total amount earned till that month (m-1)*x
k: happiness obtained at a cost of less than or equals to money
spent: the amount spent in obtaining a hapiness of k
Now, if cost[i]<money,
define k1: (happiness obtained in ith month) + (maximum happiness obtained at a cost of less than or equals to money- cost[i])
if(k1>k), we update spent to cost[i] + money spent in obtaining (maximum happiness obtained at a cost of less than or equals to money- cost[i]), and update dp[spent]=max(k,k1).
Now to locate the indices in the dp table, we can store the spent values in a set and use the lower_bound() function. Since lower bound function returns the minimum value in the set greater than equals to, and we need a spent index less than equals to some integer, the spent values can be stored in the set after multiplying with -1.

265689316

This is failing in some 104th case of test-2. What can be the mistake in my approach ?

24x7coldd

Can anyone help me why the solution 265737031 is giving a wrong answer on test 2, subtest case number 1504, any help is appreciated. Thank you. :)

codeforces98

OG problems!!

cryonai8x

can't we solve E using binary search ?? i tried binary approach dk why it is not working though ,267954800

ayush_5267

PLEASE Help me in submitting my solution in C problem[problem:1974C]. I am following the same approach as many have done in their solutions, which might be the only way to solve the problem. I am just creating a map to store all the triplets in form of a string, just with a slight change that where I get bi not equal to ci I am putting '0' instead of it. Here's the link to my submission: submission Please have a look Vladosiya.

SkyStalker_2.0

Problem E can also be solved using the multiset instead of the DP approach. The time complexity of my approach is O(nlogn).

Please find the submission link — 268804778

Happy Coding!

Блог пользователя Vladosiya