Codeforces Round #946 (Div. 3)

6 months ago, # |

+17

Looking forward to an AK, and GLHF to all participants, rated or not!

→ Reply

tbquan08hanoi

6 months ago, # |

you guys are doing so good... i'm trying my best just to stay at pupil

→ Reply

archiemahajan

6 months ago, # |

Hope to reach cyan this contest : >

→ Reply

saelcc03

6 months ago, # |

Mewing cat ready for the contest

bye bye

→ Reply

mraron

6 months ago, # ^ |

Spoiler

→ Reply

__NO__NAME__

6 months ago, # |

time for green

→ Reply

JigSaW__

6 months ago, # |

good luck for everyone:)

→ Reply

mushfiq_nehal

6 months ago, # |

Hope for a good contest.

Best wishes everyone <3

→ Reply

LiLRoSe

6 months ago, # |

wishing all GL , Hope i will become green in this round

→ Reply

0.01

6 months ago, # |

+17

Beautiful Contest...

I Loved Solving the problems...

Especially the relation "Money Buys Less Happiness Now" with "Money Buys Happiness" won my heart :)

→ Reply

6 months ago, # |

+16

Thanks for nice tasks.

Funny that I solved G by accident couple months ago.

→ Reply

123gjweq2

6 months ago, # |

E was tough

→ Reply

6 months ago, # ^ |

Teach me your ways big bro you’re so strong

→ Reply

123gjweq2

6 months ago, # ^ |

← Rev. 6 →

+11

E had a nice dp thing. Take dp[i][x] to mean the minimum number of pounds you need in order to obtain at least x happiness at month i.

The transitions are:

for a certain happiness x, we know that dp[i][x] is at most equal to dp[i — 1][x] (that is, the answer for the previous month). dp[i][x] can also be dp[i — 1][x — h[i]] + c[i] if c[i] + dp[i — 1][x — h[i]] <= the amount of money we have garnered so far.

dp[i — 1][x — h[i]] + c[i] represents the minimum cost to get at least x happiness assuming we buy happiness at month i. Of course, we can only afford this if it is less than our current amount.

We don't want x — h[i] to go below zero. So dp[i][x] = min(dp[i — 1][max(0, x — h[i])] + c[i], dp[i — 1][x]).

After this, in order to make the dp[i] represent the minimum number of pounds to get at least x happiness, we just let dp[i][a] = min(dp[i][a], dp[i][a + 1]) for a going from the sum of all happiness to 0. Aka just take suffix minimums.

The base case happens at month zero (or at month 1 actually since you technically have no money at month 1). The minimum number of pounds we need in order to obtain 0 happiness at month 0 is 0. The minimum number of pounds we need to obtain x >= 1 happiness at month 0 is infinity.

The answer will be the highest index in dp[m] who's value is not equal to infinity.

There was a lot happening in this problem.

→ Reply

https://codeforces.net/contest/1974/submission/261935786

6 months ago, # ^ |

Ohh I see it now! I thought of dp[m][h] but instead assumed min cost to get exactly h and couldn't move anywhere with transitions so weak.

Thankyou this solution is very good, I hope to achieve this level of dp sorcery soon.

→ Reply

Tanjiro_Nezuko

6 months ago, # ^ |

Try seeing this...

Very much like Knapsack when we take dp on values instead of weights.

→ Reply

6 months ago, # ^ |

Thanks, I just remember solving Knapsack — 2 on AtCoder I'm so stupid bruh.

→ Reply

PG_Mazen

6 months ago, # |

In problem C, I have wasted a lot of time in addition to 3 wrong answers because I thought that 1 <= ai <= 9

→ Reply

tickbird

6 months ago, # |

← Rev. 2 →

fail to solve D

hardest Div3 I've ever taken

byebye cyan hello green

→ Reply

teateart

6 months ago, # ^ |

Me too. I failed on C but succeeded on D. Even D takes a lot of time. Why we should move both the rover and the helicopter? If we may only move one, it will be much easier.

→ Reply

tickbird

6 months ago, # ^ |

yes, I do aware that but still, implementation was too heavy

there are too much corner cases, loc easily beyond 100

→ Reply

6 months ago, # ^ |

75, 3-4 ifs: 261907165

→ Reply

Emil_Aliyevv

6 months ago, # |

← Rev. 2 →

Div. 3 like Div. 2.5

→ Reply

6 months ago, # ^ |

more like Div3: Algorithms, Div 2+: Implementation. I spent over an hour trying to debug F.

→ Reply

6 months ago, # ^ |

I agree first 4 were all implementation based.

→ Reply

M1ngXu

6 months ago, # ^ |

yeah same, i only realized after like 30 min that they for some reason swapped the x-axis and the y-axis. couldn't solve G (in contest) then :(

→ Reply

AvaraKedavra

6 months ago, # |

← Rev. 2 →

+21

Though, I was not able to solve it, E was amazing.
Though, I was able to solve it, C was disgusting.

→ Reply

Six_Seconds

6 months ago, # ^ |

Does E have any connection with knapsack II of atcoder dp contest?

→ Reply

AvaraKedavra

6 months ago, # ^ |

Not sure, but the atcoder problem can be solved using the idea mentioned in point 5 of this blog

→ Reply

akashtadwai

6 months ago, # ^ |

I tried knapsack. It gave Memory Limit Exceeded.
Any better way to do it? My code: https://codeforces.net/contest/1974/submission/261922894

→ Reply

darkknight98

6 months ago, # ^ |

its actually because we can't have current money as our 2nd state in dp because x<=1e8 as a result 50*1e8 will always give MLE. we have to use happiness as our 2nd state of dp

→ Reply

akashtadwai

6 months ago, # ^ |

← Rev. 5 →

I'm struggling to write a recursive dp for the above-described state $$$dp_{idx,happiness}$$$. I've looked into many submissions but all of them have iterative dp solutions. It would be great if I could get a recursive dp solution. I tried to define $$$dp_{idx,hp}$$$ as maximum money I can have from $$$idx...n$$$ with happiness $$$hp$$$

→ Reply

kojak_

6 months ago, # ^ |

More or less.

→ Reply

Tanjiro_Nezuko

6 months ago, # ^ |

I have nice solution for C, using custom comparator for std::map. It came very handy. You may have a look :- https://codeforces.net/contest/1974/submission/261857159

→ Reply

slabi

6 months ago, # |

humiliating

→ Reply

VitaliiV

6 months ago, # |

The hardest div 3 I've ever seen.

→ Reply

amoad

6 months ago, # |

(corner_case)Forces

→ Reply

Silvally

6 months ago, # |

Can someone pls tell me how did you solve que C? I tried solving it using brute force and got TLE multiple times 261901233

→ Reply

amoad

6 months ago, # ^ |

that's a $$$O(N^{2})$$$ time complexity , you should try less

→ Reply

MJavad

6 months ago, # ^ |

Think of how find the number of beautiful pairs of triples that differ in the third element... then think of how to extend it

→ Reply

elseecay

6 months ago, # |

good tasks

→ Reply

MikeMirzayanov

6 months ago, # |

+36

In this round, there were three problems based on my ideas: 1974B - Symmetric Encoding, 1974C - Beautiful Triple Pairs, 1974F - Cutting Game.

→ Reply

Noluck_167

6 months ago, # ^ |

C was tough or it uses some specific technique that i wasn't aware of.

→ Reply

6 months ago, # ^ |

check the tuples where item of position K is unique. Tuples's positions = {0,1,2}

I will show logic for K=0, but similar logic can be used for K = 1 and K = 2.

For each tuple. Create a map that stores {1,2} as a key and a list of integers the 0s as values. Then sort that list. Then you can figure out how many items are strictly less than n, with a linear scan.

→ Reply

Noluck_167

6 months ago, # ^ |

i did the same but miscalculated the number of tuples.I think its time for solving some Combinatorics problems.

→ Reply

neo_programmer

6 months ago, # ^ |

I also thought of the same approach, but spent a lot of time implementing it and miscalculating

→ Reply

krishnagopalagarwal7

6 months ago, # |

Is there any solution for E using maps? If yes, can someone fix my code 261908381?

→ Reply

Itachi_Uchiha13

6 months ago, # ^ |

Well I tried to optimize your code, eliminated the use of one map in this submission 261926879. But it still gave TLE.

I initially also got a TLE during the contest on test case 14, that is because I did not notice the upper bound over all the test cases was on sum of hi and not m.

→ Reply

krishnagopalagarwal7

6 months ago, # ^ |

Thanks

→ Reply

krishnagopalagarwal7

6 months ago, # ^ |

This solution got accepted 261959135. But yeah now I am forming Happiness-money as key-value pair instead of money-happiness, considering the upper bound.

→ Reply

6 months ago, # |

Hardest Div 3 ... Only div 3 B solved ... can some one tell me the logic of C

→ Reply

iij

6 months ago, # ^ |

← Rev. 2 →

use a map for each triple:

count += the number of triples that have atleast 2 similar elements

count -= the number of triples that are the exact same

→ Reply

6 months ago, # ^ |

hmmm, do map can carry triplets .... i think i have to learn stl library in brief .. Thank you .

→ Reply

iij

6 months ago, # ^ |

← Rev. 2 →

I just used a map<vector<int>, int> and it passed.

→ Reply

6 months ago, # ^ |

Ah , got it .. Thanks

→ Reply

Timosh

6 months ago, # ^ |

map can carry any pair of datatypes(map<T,T>)

for the case of task C, it is possible to solve it using 4 maps, 3 of them are map<pair<int,int>,int> and the 4th one is map<tuple<int,int,int>,int>(for 3 equals)

→ Reply

__NO__NAME__

6 months ago, # |

is D that easy ? there are a lot of submissions...how to solve it

→ Reply

MudaMuda

6 months ago, # ^ |

the most important is to notice that the opposite directions like (N, S) and (W, E) are remove each other.

→ Reply

Shruti_07

6 months ago, # ^ |

For me 4th was easier than 3rd. I solved the 3rd one but wasn't able to optimize it. I just needed few min to submit 4th.

→ Reply

jayasting98

6 months ago, # ^ |

I paired up N with S and E with W. For each pair, I assign either both H or both R. For example, if some pair of N and S are assigned H, then they cancel out, and they effectively do not move the helicopter.

There will be unpaired ones left over. We just have both the H and R assigned to an equal number of unpaired ones for each direction, then they will end up in the same position. If H and R have equal of each, then that implies that the total number of unpaired ones must be even for each direction. For example, if we have NENNNE, then there are 4 N and 2 E, so we just let H and R have 2 N and 1 E each. NENNEE is not possible, because there are odd N, or odd E.

→ Reply

Wasif_Shahzad

6 months ago, # ^ |

the easiest solution would be to just follow the moves of other robot and brute force it. there is one specific case when following solution won't work and that is when we have one movement of each direction each. we can handle that separately. here's my submission

→ Reply

qwerlty123

6 months ago, # |

I took more than one hour to solve D

→ Reply

m_df

6 months ago, # |

Please add an option to filter out non-official (* asterisk) contestants. How can we see the real standings without such an option

→ Reply

pokeland157

6 months ago, # ^ |

There is a checkbox called "show unofficial" on the top right corner of the standings page, untick it

→ Reply

m_df

6 months ago, # ^ |

Thanks!

→ Reply

SuperMo

6 months ago, # |

how did so many people understood this: each character in the string s is replaced by its symmetric character from the string r (the first character of the string r will be replaced by the last, the second by the second from the end, and so on).

I feel like I lack the ability to guess the problem statement

→ Reply

MudaMuda

6 months ago, # ^ |

← Rev. 2 →

when I have difficulty in understanding the statement i directly go to the example, and I think the example was clear

→ Reply

_dexterDynamo_

6 months ago, # ^ |

Took me some time but using set and map kind of helped.

→ Reply

Filipe9

6 months ago, # ^ |

← Rev. 2 →

Yeah the wording of that problem tripped me up too. I interpreted it as each character in string r acts as a key with the value as the symmetrical character in string r. Then search each string s character in the hashmap to find its decoded character. It worked in the end

→ Reply

kakasuarez

6 months ago, # ^ |

I was only able to understand it because of the illustration that was provided.

→ Reply

MJavad

6 months ago, # ^ |

There is a picture in the problem statement that explains it

→ Reply

Shruti_07

6 months ago, # |

AHHHHHHH....should've tried 4th instead of wasting time on 3rd.

→ Reply

kakasuarez

6 months ago, # ^ |

Yeah, you're right. Thankfully I thought of this soon enough to solve D, otherwise I would have not been able to solve either of them in time.

→ Reply

krishna_08

6 months ago, # |

Hardest div 3 ever implementing C takes a lot of time and even D is also tough to implement

→ Reply

6 months ago, # ^ |

exactly , D took lots of conditions to print correct answer , it should be yes / no type with C and C should be D.

→ Reply

Rinkeshkumarsinha

6 months ago, # ^ |

I got tle in D couldn't optimize

→ Reply

noob_in_area

6 months ago, # ^ |

i tried c problem with hash, wasn't much difficult to implement. but i got intituion for d but couldn't implement it. a lot of conditions were there

→ Reply

krishna_08

6 months ago, # ^ |

I also implemented C with hash map by making pair of two elements of a triplet as key and another element of triplet as value,But I overcomplicated to optimise more.

D is very tricky to implement because of the condition that each device must execute at least one instruction.

→ Reply

noob_in_area

6 months ago, # ^ |

yeah in c u can manage 4 maps string key and int value, where first map denotes triplet starts from a[j],a[j+1], second map triplet end a[j+1],a[j+2] third a[j] and a[j+2] and fourth having triplet itself. so at any position we can get total triplets.

for refrence:

unordered_map<string,int> m1;
 unordered_map<string,int> m2;
 unordered_map<string,int> m3;
 long long ans =0;
 for(int i=2;i<n;i++) {

    string s1 = to_string(a[i-2])+","+to_string(a[i-1]);
    string s2 = to_string(a[i-1])+","+to_string(a[i]);
    string s3 = to_string(a[i-2])+","+to_string(a[i]);
    string s4 = to_string(a[i-2])+","+to_string(a[i-1])+","+to_string(a[i]);

    long long a1 = 1ll*m1[s1];
    long long a2 = 1ll*m3[s2];
    long long a3 = 1ll*m2[s3];
    long long a4 = 1ll*m1[s4];
  // finding all triplet
    ans+=(a1-a4)+(a2-a4)+(a3-a4);
    // updating tripletes
    m1[s1]++,m3[s2]++,m2[s3]++,m1[s4]++;

 }

→ Reply

noob_in_area

6 months ago, # ^ |

i got d but after the contest done lol !!!, like we can just manage their states of R and H

→ Reply

mushfiq_nehal

6 months ago, # |

Problems were kinda hard according to div3

→ Reply

WORTH

6 months ago, # |

-13

The time limit and constraints of C could be managed better. Other than that, the problems were nice.

→ Reply

MudaMuda

6 months ago, # |

any hint for E? I tried dp[m][x] using map but obviously I get TLE;

→ Reply

6 months ago, # ^ |

Try dp[h] = max money we can have after buying $$$h$$$

→ Reply

ay012

6 months ago, # ^ |

vstiff can you tell your transitions ? for the dp states and why so reason too please

→ Reply

6 months ago, # ^ |

← Rev. 3 →

Basically just two transitions:

1) buy everything

if dp[k] >= c {
  dp[k + h] = dp[k + h].max(dp[k] - c);
}

2) get salary

dp[k] += x;

→ Reply

ay012

6 months ago, # ^ |

← Rev. 3 →

nvm got it

→ Reply

6 months ago, # ^ |

← Rev. 2 →

I've solved with dp[m][total_happiness]

obviously it passed

→ Reply

Insanity_123

6 months ago, # ^ |

Hi daud04, I see you have done recursive DP, can you please explain your solution in detail if possible? I couldn't think of a way dot it recursively as money from previously bought happiness can still be leftover and help us in future, I did it iteratively : link , If anyone else know this please feel free to pitch in.

→ Reply

6 months ago, # ^ |

my dp state is [index][required_happiness] and it returns the minimum required money i must have before entering the state to buy required happiness.

(i'm just going forward here)

as a knapsack dp, there is 2 option.

if i buy the happiness of the index , i must have a[index] value now , and must have the to money to buy remaining happiness from next indexes, as i can store this k for next indexes , substituted k from next dp cost.

→ Reply

halfyy

6 months ago, # |

nice problem set! i have seen same ideas like in these problems before, but they are usually in div2 and too hard to solve. thank you for introducing them for me!

→ Reply

Aditya_Metkar

6 months ago, # |

I hoped Brute Force would work on Problem C with 4s Time Limit but NOPE...

→ Reply

Atma_

6 months ago, # |

Really nice contest. Problems were not too difficult, and liked the problem E especially. Problem D was implementation heavy and if not for some mistakes in it and time wasted in debugging it, this would have been my first contest to solve all problems as I solved G just few minutes after contest ended :(

→ Reply

brave-kid

6 months ago, # |

I have a bonus problem (Harder version of problem $$$C$$$) : A pair of triplet is good if elements in any two positions are not equal and equal in one position , count the number of good pairs

→ Reply

Pi-nan

6 months ago, # ^ |

wouldn't it be equal to the total number of pairs — number of pairs with exactly 2 matches (current problem) — number of pairs with all 3 matches?

→ Reply

brave-kid

6 months ago, # ^ |

you also have to subtract number of pairs with 0 matches

→ Reply

cwz2024

6 months ago, # |

Tough C, I come up with the the solution pretty quickly but spent many times to implement it 261860863

And D also a terrible implementation(at least for my code) I neerly smashed my laptop when I realize what I am coding 261856874

And can someone help with my E? At first I thought it was a signed int overflow (because it did't WA until test case 10) but it seems to be more than that... 261884565

→ Reply

Kevalllll

6 months ago, # ^ |

Not getting what is wrong with my memoization solution of E: 261908791

Appreciate the help if anyone could.

→ Reply

Pinaki_20001

6 months ago, # ^ |

D 261878026 seemed easier to implement than C 261849652. My C almost took 1.2 secs. I think it might get hacked lol

→ Reply

shviv1

6 months ago, # ^ |

My solution for C uses four maps and an idea of inclusion and exclusion. But I couldn't solve D in +1 hour.

261867166

→ Reply

jose_5056

6 months ago, # ^ |

I tried submitting your code 261934590 and got it accepted. The idea was that a particular state can be visited many times, you assumed that it can be only once.

Code

If it is visited more than once, we minimise the value of dph[i][j + a[i].ss] for every such visit.

 if (dp[i - 1][j])
            {
                if (money >= a[i].ff + dph[i - 1][j])
                {
                    if (dp[i][j + a[i].ss] != 1)
                        dph[i][j + a[i].ss] = dph[i - 1][j] + a[i].ff;
 
                    else
                    {
                        dph[i][j + a[i].ss] = min(dph[i][j + a[i].ss], dph[i - 1][j] + a[i].ff);
                    }
 
                    dp[i][j + a[i].ss] = 1;
                }
            }

→ Reply

cwz2024

6 months ago, # ^ |

← Rev. 2 →

Oh my god, I actually have realized it but my brain didn't go right and made huge amount of small mistakes when I tried to modify it :(

And It should have been Accepted if simply to add a more ! in my last minute submitted code rather than failed in test case 1 (:_;)

Anyway, thank U very much orz

→ Reply

andrewtt

6 months ago, # |

Are all submissions tested against the test cases from successful hacks at the end of the hacking phase?

→ Reply

Pevo

6 months ago, # |

Hardest div3 I've ever taken, C is harder than an average C in div2.

→ Reply

6 months ago, # ^ |

A: Really easy problem, as it should be (800)

B: Already semi-difficult, similar to 2B in some ways (1000).

C: Extremely difficult to implement and solve for its position, analgous to easy-mid Div2C/Div3D (1300)

D: Easy to solve, ananoying to implement(1300).

E: Elegant but hard. DNS (1700).

F: Got me stuck in debugging hell for an hour (1900).

G: DNS (2000)

→ Reply

Anongoat

6 months ago, # ^ |

dns is short for what?

→ Reply

6 months ago, # ^ |

Did Not Solve.

→ Reply

1e3bonzakura

6 months ago, # ^ |

???

I'm a noob and it was very easy IMO. Done it in 12 minutes.

→ Reply

nxsang1611

6 months ago, # |

← Rev. 2 →

-24

*Deleted

→ Reply

tickbird

6 months ago, # |

got AC on D after contest simply by removing pre-check, but simulate answer then checking correctness.

→ Reply

garlic_bread_0204

6 months ago, # ^ |

I don't see that in your submissions...

→ Reply

Astroflexx

6 months ago, # ^ |

Bruh your last contest was on March 1, and you haven't participated since then and complain??

→ Reply

tb_ro

6 months ago, # |

I had the right idea on C with the three maps but I couldn't think of the way to sum them up correctly :(. Problem D was really nice, the concept and everything. E was also cool but I didn't really have time to solve it. First time I solve D and don't solve C on a contest which I didn't expect to be fair but I'll take it.

→ Reply

Ladamalina

6 months ago, # ^ |

Try this way for C

// pair -> 3rd num -> frequency
std::unordered_map<ii, std::map<int, int>, HashPair> set12, set23, set13;
// pair -> count
std::unordered_map<ii, int, HashPair> cnt12, cnt23, cnt13;

AC in 999ms for me https://codeforces.net/contest/1974/submission/261840334

→ Reply

dragospvp1

6 months ago, # |

Any idea how to do this faster? https://codeforces.net/contest/1974/submission/261915177

→ Reply

VitaliiV

6 months ago, # ^ |

don't copy the string every time you find a duplicate character

→ Reply

dragospvp1

6 months ago, # ^ |

done thank you :)

→ Reply

lizzahazza

6 months ago, # |

In F, what if k is fixed in input and instead of moves being given, both players play optimally to maximize their score?

→ Reply

Here is the almost correct solution

6 months ago, # ^ |

n^4 dp !!

→ Reply

kareem_Bizreh

6 months ago, # |

i wish that problems next time be less implementation T_T

→ Reply

marc2825

6 months ago, # |

← Rev. 2 →

I am surprised that ChatGPT was able to solve problem G in this round. To be more specific, I was stuck on G, so I put the problem statement into ChatGPT, which is a hot topic right now, to try to get some clues. Initially, it presented me with an incorrect greedy code (a simple greedy method of looking from the front and buying if possible). Then, I provided an example that would fail with this solution (Test Case 3: 6 4, 4 10 3 8 6 10). To my surprise, it then gave me the correct greedy algorithm using priority_queue! (This might have been a lucky punch, though)

I am unrated so I am not particularly affected, but for contests like div-3/4 with many typical problems, ChatGPT might be able to solve quite a lot of them...... (I haven't tried it yet, but I think it can also solve problems like F, which have straightforward and typical approaches but may be a hassle to implement.)

(My prompt: https://chatgpt.com/share/05ad0c4b-33a1-4480-8f46-c7a87a60f019 we need to fix some details (input and the timing of adding X), so we can't just copy and submit, but the main idea is totally correct. I think if the prompts were further elaborated, the code will follow those instructions too.)

→ Reply

ab_malek

6 months ago, # ^ |

← Rev. 2 →

Problem G was a pretty standard priority queue problem. After taking current happiness if the cost becomes higher than the money we have. We have to remove some happiness we prevously take. Which one should we remove ? Of course the most cost happinesses.

→ Reply

Xor_again

6 months ago, # ^ |

I gave problem E to GPT-4, and after 2-3 attempts it come up with an almost correct answer, and then i provided some hints and i got the correct answer.

and here is the correct solution

But don't get the wrong idea, I didn't use CHATGPT during Contest, nor do i want to suggest using it. I just wanted to check the capability of GPT-4 for dynamic programming problems.

→ Reply

arceus31

6 months ago, # |

Any insights into why this submission is giving an incorrect result for test case 5: 261917349

→ Reply

treasuryonly

6 months ago, # ^ |

You can use long long instead of int.

→ Reply

arceus31

6 months ago, # ^ |

Just realized and got ac, 'integer overflow' destroyed this contest :(. Didn't even spent time on D which was very much implementation only.

→ Reply

treasuryonly

6 months ago, # |

Problem C is nice, I was so intense solving it, switched to C++ after getting MLE with Haskell, couldn't make it in time but still made my day.

Screenshot

Thank you guys for a nice contest!

→ Reply

_Lactosi

6 months ago, # |

Thanks for such a great contest. I loved it

→ Reply

cseshamim47

6 months ago, # |

How to solve C?

Can anybody please tell me why I'm getting WA on test 4? Submission

→ Reply

treasuryonly

6 months ago, # ^ |

With 1 <= a[i] <= 1e6 then these may not work:

int abc = (v[i]*100)+(v[i+1]*10)+v[i+2];

int _ab = (v[i]*10)+v[i+1];

int _bc = (v[i+1]*10)+v[i+2];

int _ac = (v[i]*10)+v[i+2];

I think you can use pair instead of combining into a single int value.

→ Reply

cseshamim47

6 months ago, # ^ |

ohh shit. I misread the constraint :(

→ Reply

peti1234

6 months ago, # |

+43

G was pretty similar to this problem: 1526C2 - Potions (Hard Version)

→ Reply

Sreedhar3210

6 months ago, # ^ |

I had a strong feeling that i have seen G like problem before, seems to be this.

→ Reply

nxsang1611

6 months ago, # ^ |

Orz it's really the same

→ Reply

whiitex

6 months ago, # |

Great contest, but I think that problem A could have been written in a better way: there are too many people who did it after 10 mins, meaning that the statemenet was not clear at all. Something like "an app can only be placed on a single screen" would have been enough. I was (wrongly) thinking of application on multiple screens, so that, e.g. 4 screens could contain 15 y app. Hope next time I'll be sharper in statement comprehension

→ Reply

ayushanshul07

6 months ago, # |

I am unable to figure out why my C is failing

https://codeforces.net/contest/1974/submission/261920538

It fails on 1110 testcase on Unit Test 2.

→ Reply

chipi_chipi

6 months ago, # ^ |

mine fails on 1108 in the same testcase

https://codeforces.net/contest/1974/submission/261872195

i spent so much time on this problem :(

→ Reply

olegator2007

6 months ago, # |

← Rev. 2 →

Please explain why D is failing on test 4 261864972.

→ Reply

iLLuSiOnZ

6 months ago, # |

Can someone explain why my solution 261888809 with $$$N=10^5$$$ failed, but the same solution 261919448 with $$$N=$$$$$$\sum\limits_{i = 1}^mh_{i}$$$ passed in 1974E - Money Buys Happiness where $$$N$$$ is the maximum number of elements in $$$dp$$$ array. I guess my time complexity is $$$O(N*M)$$$ which should pass. And what does this statement It is guaranteed that the sum of $$$\sum_{i}h_{i}$$$ over all test cases does not exceed $$$10^5$$$ means?

→ Reply

Dell_Know

6 months ago, # ^ |

I got the same TL as you because I initially did dp with $$$5 \cdot 10^4$$$.

The problem is $$$t <= 1000$$$, so taking in your case dp till $$$10^5$$$ will make the worst case of $$$10^5 \cdot 10^3 \cdot 50 = 5 \cdot 10^9$$$, which is too much. (in my case it was twice less, but still too much).

But taking $$$N = \sum_{i = 1}^m h_i$$$ resolves this, cuz then the worst case will be $$$m \cdot \sum_{i = 1}^t N_i$$$, but we know that sum of all $$$N_i$$$ over $$$t$$$ cases is not greater than $$$10^5$$$, then the worst case will be $$$50 \cdot 10^5 = 5 \cdot 10^6$$$ which is good enough.

→ Reply

iLLuSiOnZ

6 months ago, # ^ |

Oh yeah, now I realised when you mentioned it, basically overall time complexity is $$$O(T*M*$$$$$$\sum_{i}h_{i})$$$ and they have mentioned that $$$(T*$$$$$$\sum_{i}h_{i})$$$$$$\leq10^5$$$ so worst case will be $$$5*10^6$$$ which is fast enough whereas in my case, it will be $$$5*10^9$$$ which is TLE. Thnx mate.

→ Reply

Astroflexx

6 months ago, # |

Problem C and D sucked the living soul out of me. Took whole 2hr to solve them. Really hard for a Div3.

→ Reply

accord

6 months ago, # |

C was unusually hard for Div3. E was nice.

Hopefully back to blue after this one.

→ Reply

Jagnath_Reddy

6 months ago, # |

I got the correct intuition for C but then I thought HashMap<Integer,HashMap<Integer,HashMap<Integer,Integer>>> must not be the intended solution, should have continued

→ Reply

arajeev210

6 months ago, # ^ |

You can also do it using 1 TreeMap<Triple, Integer>. (TreeMap cus ez to write a comparator for triple). Use -1 to represent a "hole"

→ Reply

Jagnath_Reddy

6 months ago, # ^ |

Your solution is amazing

→ Reply

arajeev210

6 months ago, # ^ |

Thank you :)

→ Reply

pcumamahesh

6 months ago, # ^ |

Yeah, even I did something similar to that. 261823516

→ Reply

Saptak3315

6 months ago, # |

Is E solvable using recursive dp?

→ Reply

amoad

6 months ago, # ^ |

i implement recursive dp but it gives a wrong output my dp state is dp[index][buy or do not buy]

code

vector < int > cost ; 
vector < int > h ; 
vector < vector < int >>  dp ; 

int rec ( int index , int bought , int current , int salary , int m ) {

      if ( index == m ) return 0 ; 

      if ( dp[index][bought] != -1 ) return dp[index][bought] ; 

      int first = 0 ; 
      int second = rec ( index + 1 , 0 , current + salary , salary , m ) ; 

      if ( cost[index] <= current ) 
         first = h[index] + rec ( index + 1 , 1 , current + salary - cost[index] , salary , m ) ; 


      return dp[index][bought] = max ( first , second ) ; 
}

void solve(){ 
  

     int m , x ; 
     cin >> m >> x ; 

     dp.resize ( m + 1 , vector < int > ( 2 , -1 ) ) ; 
     cost.resize ( m + 1 ) ; 
     h.resize ( m + 1 ) ; 


     for ( int i = 0 ; i < m ; i++ ) {
       cin >> cost[i] >> h[i] ; 
     }
     

     int bought = rec ( 0 , 1 , 0 , x , m ) ; 
     int not_bought = rec ( 0 , 0 , 0 , x , m ) ;
     
     cout << max ( bought , not_bought ) ; 

  
    dp.clear() ; 
    cost.clear() ; 
    h.clear() ; 


}

output

output :
0
10
200
15
1
10 -> should be 9
11 -> should be 9

let me know if you were able to solve it using recursion or any other dp state

→ Reply

Ladamalina

6 months ago, # ^ |

I've solved it using iterative DP https://codeforces.net/contest/1974/submission/261897619

→ Reply

manikiran949

6 months ago, # ^ |

I found this submission which uses recursive dp : https://codeforces.net/contest/1974/submission/261868908

→ Reply

formidablechief27

6 months ago, # |

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

→ Reply

RakibHossain

6 months ago, # |

Problem B is getting too many successful hacks. Can someone tell me what seems to be the problem with the solution approach of those who are getting hacked.

→ Reply

ruthvik16

6 months ago, # ^ |

How does an O(n) solution lead to a TLE hack in particular?

→ Reply

eshaansodhi

6 months ago, # ^ |

+14

what they did wrong was they declared the answer as an empty string and instead of pushing m[s[I]] back , all of them added it to the current string and replaced the current string. This made each operation having a cost of i(current) length , giving the end time complexity of O(n^2)

Wrong approach => ans = ans + map[s[i]]

Correct approach => ans.push_back(map[s[i]])

→ Reply

RakibHossain

6 months ago, # ^ |

-12

That is completely misstatements. ans = ans + mp[s[i]]; doesn't lead to O(n^2) complexity.

→ Reply

Vladosiya

6 months ago, # ^ |

Actually, I tried to change one of hacked submission this way and it worked. Sad that it wasn't caught by our max test.

→ Reply

aqua4

6 months ago, # ^ |

unordered_map is easily hackable. Don't know what's wrong about default map solutions.

→ Reply

spisded

6 months ago, # |

Can someone explain the second last given test case of problem E?

→ Reply

shviv1

6 months ago, # ^ |

you can buy 2,3, and 5th tokens to get maximum happiness.

→ Reply

spisded

6 months ago, # ^ |

Okay now i see, i understood the question completely wrong. Thanks

→ Reply

AHMADUL

6 months ago, # |

'C' is quite tricky implementation!!!

→ Reply

rmz

6 months ago, # |

can we solve E with recursive dp ?

→ Reply

OgataShumaHiroyuki

6 months ago, # |

I would appreciate your kindness if any of you could just debug my code for E, Thanks. https://codeforces.net/contest/1974/submission/261937456

→ Reply

Dell_Know

6 months ago, # ^ |

TL can occur because you loop through $$$10^5$$$ values in dp on each test (look at this https://codeforces.net/blog/entry/129611?#comment-1150814). Change to the sum of $$$h_i$$$.

→ Reply

OgataShumaHiroyuki

6 months ago, # ^ |

I still get TLE, please have a look, sir. Submission link after changes

→ Reply

Little_Sheep_Yawn

6 months ago, # ^ |

← Rev. 2 →

It seems that you use memset(dp,-1,sizeof(dp)), the complexity of which is the size of dp, thus $$$5\times 10^6$$$ approximately.

If you do this whenever you process a test case, as the total number of test cases can be $$$1000$$$ , you reach a total complexity of $$$1000\times 5\times 10^6=5\times 10^9$$$ , which is clearly wrong.

→ Reply

parvaraval27

6 months ago, # |

Thank you for the contest codeforces! Newbie here...Felt C was bit harder compared to D , anyone else?

→ Reply

theRealChainman

6 months ago, # |

good round, especially like F and G this round.

→ Reply

saelcc03

6 months ago, # |

20 lines of code for problem D

link

who less?

→ Reply

6 months ago, # ^ |

Little suggestion to turn 20 lines of yours to 15. Check this part:

  for(char c: ss){
    if(c == 'W') pm['W']++;
    if(c == 'E') pm['E']++;
    if(c == 'N') pm['N']++;
    if(c == 'S') pm['S']++;
  }

Simplify it to for(char c: ss) pm[c]++;. Easier debug this way too.

→ Reply

saelcc03

6 months ago, # ^ |

XD You are right. I missed that. Thanks

→ Reply

NULLgorithm

6 months ago, # |

Only if I wouldn't have spent so much time on C :(

→ Reply

AdityaTakkar

6 months ago, # |

for Problem E, is it the right approach to find the minimum number of money required to obtain x amount of happiness given i months using dp?. And then check what is the maximum possible happiness for which he can pay the money.

→ Reply

6 months ago, # ^ |

Yeah. it's right. I did the same way.

→ Reply

AdityaTakkar

6 months ago, # ^ |

← Rev. 2 →

Thats great.Can you please explain what were transition eqn. you wrote, I am not able to find bug in my code

→ Reply

aqua4

6 months ago, # ^ |

knapsack

→ Reply

6 months ago, # ^ |

as a knapsack dp, there is 2 option.1. if i buy the happiness of the index , i must have a[index] value now , and must have the to money to buy remaining happiness from next indexes, as i can store this k for next indexes , substituted k from next dp cost.

→ Reply

My ugly solution for D, but it works.

6 months ago, # |

← Rev. 2 →

C and D are much tougher than regular Div3. Btw, a tip for the likes of D is jotting down all possible negative cases first, then either deal with the correct one or a much more trivial yes-or-no decision making.

~~Btw, anyone having a hint for G? I have a few ideas but I'm afraid I was overthinking at contest...~~ (Nvm, I read a comment above and realized I was way too stupidly overthinking... T.T)

→ Reply

Ulissao

6 months ago, # |

It was the coolest Div. 3 that I have ever done. However I did it well, I solved A-D tasks.

In my point of view, C was way harder than D. I did a ugly implementation with a giant code.

I expect to get green.

Thanks for the contest !!!!

→ Reply

pcumamahesh

6 months ago, # |

Thanks for the contest! The problems were of pretty good quality as compared to recent div3 rounds. Hoping to reach Expert by the end of main tests!

→ Reply

lizzahazza

6 months ago, # |

implementation forces with too easy G. E and F were better imo.

→ Reply

udta_kouwa

6 months ago, # |

My solution for problem-D assign first N-S to Robot and E-W to Helicopter and track the positions.
My Solution

→ Reply

charan..

6 months ago, # |

i got a problem with the submission i submitted the code but till now it is showing as it is in queue can u check it once

→ Reply

fisher199

6 months ago, # |

What are some approaches that can be used to solve F? I was thinking either some sort of dp or something with geometry. That is to say, we somehow determine the number of points in a bounding box, and each cut makes this bounding box smaller. Then, by keeping a record, we can determine the numbers of points obtained for each cut. Or are these ideas a bit to "direct"?

→ Reply

6 months ago, # ^ |

It's direct, but it's kinda the motive of it. When moving the bounding box, you'll figure the points that would be left out of the box.

Maintaining those points would require a sorted data structure with add/find/delete operation — as this data structure should add the points initially, find the points that are before/after a certain threshold, and delete those points. Still the number of points in the original box is quite large, so these operations should be fast enough instead of a naive linear one in array. For my most convenience, AVL/RBtree-based data structures (i.e. set at C++ and TreeSet at Java) should work well enough.

→ Reply

tanishgoyal16

6 months ago, # ^ |

Can you explain your idea of how you deleted elements from the opposite dimension. I mean, if the move is U or D, how did you deleted those coordinates from the data structure where the coordinates are stored optimally for L/R operations (if you even are using a 2nd DS for that matter) ?

→ Reply