Codeforces Round #946 (Div. 3)

13 days ago, # |

+17

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

→ Reply

tbquan08hanoi

13 days ago, # |

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

→ Reply

archiemahajan

13 days ago, # |

Hope to reach cyan this contest : >

→ Reply

saelcc03

13 days ago, # |

Mewing cat ready for the contest

bye bye

→ Reply

mraron

13 days ago, # ^ |

Spoiler

→ Reply

__NO__NAME__

13 days ago, # |

time for green

→ Reply

JigSaW__

13 days ago, # |

good luck for everyone:)

→ Reply

mushfiq_nehal

13 days ago, # |

Hope for a good contest.

Best wishes everyone <3

→ Reply

LiLRoSe

13 days ago, # |

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

→ Reply

0.01

13 days 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

13 days ago, # |

+16

Thanks for nice tasks.

Funny that I solved G by accident couple months ago.

→ Reply

123gjweq2

13 days ago, # |

E was tough

→ Reply

13 days ago, # ^ |

Teach me your ways big bro you’re so strong

→ Reply

123gjweq2

13 days 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.com/contest/1974/submission/261935786

13 days 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

13 days ago, # ^ |

Try seeing this...

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

→ Reply

13 days ago, # ^ |

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

→ Reply

PG_Mazen

13 days 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

13 days ago, # |

← Rev. 2 →

fail to solve D

hardest Div3 I've ever taken

byebye cyan hello green

→ Reply

teateart

13 days 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

13 days ago, # ^ |

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

there are too much corner cases, loc easily beyond 100

→ Reply

13 days ago, # ^ |

75, 3-4 ifs: 261907165

→ Reply

Emil_Aliyevv

13 days ago, # |

← Rev. 2 →

Div. 3 like Div. 2.5

→ Reply

13 days ago, # ^ |

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

→ Reply

13 days ago, # ^ |

I agree first 4 were all implementation based.

→ Reply

M1ngXu

13 days 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

13 days 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

13 days ago, # ^ |

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

→ Reply

AvaraKedavra

13 days ago, # ^ |

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

→ Reply

akashtadwai

13 days ago, # ^ |

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

→ Reply

darkknight98

13 days 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

13 days 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_

13 days ago, # ^ |

More or less.

→ Reply

Tanjiro_Nezuko

13 days ago, # ^ |

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

→ Reply

slabi

13 days ago, # |

humiliating

→ Reply

VitaliiV

13 days ago, # |

The hardest div 3 I've ever seen.

→ Reply

amoad

13 days ago, # |

(corner_case)Forces

→ Reply

Silvally

13 days 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

13 days ago, # ^ |

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

→ Reply

MJavad

13 days 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

13 days ago, # |

good tasks

→ Reply

MikeMirzayanov

13 days ago, # |

+36

In this round, there were three problems based on my ideas: 1974B - Симметричное кодирование, 1974C - Красивые пары троек, 1974F - Игра с отрезанием.

→ Reply

Noluck_167

13 days ago, # ^ |

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

→ Reply

13 days 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

13 days ago, # ^ |

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

→ Reply

neo_programmer

13 days ago, # ^ |

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

→ Reply

krishnagopalagarwal7

13 days ago, # |

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

→ Reply

Itachi_Uchiha13

13 days 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

13 days ago, # ^ |

Thanks

→ Reply

krishnagopalagarwal7

13 days 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

13 days ago, # |

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

→ Reply

iij

13 days 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

13 days ago, # ^ |

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

→ Reply

iij

13 days ago, # ^ |

← Rev. 2 →

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

→ Reply

13 days ago, # ^ |

Ah , got it .. Thanks

→ Reply

Timosh

12 days 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__

13 days ago, # |

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

→ Reply

MudaMuda

13 days ago, # ^ |

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

→ Reply

Shruti_07

13 days 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

13 days 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

12 days 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

13 days ago, # |

I took more than one hour to solve D

→ Reply

m_df

13 days 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

13 days ago, # ^ |

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

→ Reply

m_df

13 days ago, # ^ |

Thanks!

→ Reply

SuperMo

13 days 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

13 days 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_

13 days ago, # ^ |

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

→ Reply

Filipe9

13 days 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

13 days ago, # ^ |

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

→ Reply

MJavad

13 days ago, # ^ |

There is a picture in the problem statement that explains it

→ Reply

Shruti_07

13 days ago, # |

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

→ Reply

kakasuarez

13 days 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

13 days ago, # |

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

→ Reply

13 days 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

13 days ago, # ^ |

I got tle in D couldn't optimize

→ Reply

noob_in_area

13 days 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

13 days 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

13 days 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

13 days ago, # ^ |

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

→ Reply

mushfiq_nehal

13 days ago, # |

Problems were kinda hard according to div3

→ Reply

WORTH

13 days ago, # |

-13

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

→ Reply

MudaMuda

13 days ago, # |

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

→ Reply

13 days ago, # ^ |

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

→ Reply

ay012

13 days ago, # ^ |

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

→ Reply

13 days 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

13 days ago, # ^ |

← Rev. 3 →

nvm got it

→ Reply

13 days ago, # ^ |

← Rev. 2 →

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

obviously it passed

→ Reply

Insanity_123

13 days 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

13 days 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

13 days 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

13 days ago, # |

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

→ Reply

Atma_

13 days 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

13 days 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

13 days 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

13 days ago, # ^ |

you also have to subtract number of pairs with 0 matches

→ Reply

cwz2024

13 days 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

13 days ago, # ^ |

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

Appreciate the help if anyone could.

→ Reply

Pinaki_20001

13 days 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

13 days 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

13 days 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

13 days 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

13 days ago, # |

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

→ Reply

Pevo

13 days ago, # |

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

→ Reply

13 days 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

13 days ago, # ^ |

dns is short for what?

→ Reply

13 days ago, # ^ |

Did Not Solve.

→ Reply

1e3bonzakura

13 days ago, # ^ |

???

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

→ Reply

nxsang1611

13 days ago, # |

← Rev. 2 →

-24

*Deleted

→ Reply

tickbird

13 days ago, # |

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

→ Reply

garlic_bread_0204

13 days ago, # ^ |

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

→ Reply

Astroflexx

13 days ago, # ^ |

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

→ Reply

tb_ro

13 days 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

13 days 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.com/contest/1974/submission/261840334

→ Reply

dragospvp1

13 days ago, # |

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

→ Reply

VitaliiV

13 days ago, # ^ |

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

→ Reply

dragospvp1

13 days ago, # ^ |

done thank you :)

→ Reply

lizzahazza

13 days 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

13 days ago, # ^ |

n^4 dp !!

→ Reply

kareem_Bizreh

13 days ago, # |

i wish that problems next time be less implementation T_T

→ Reply

marc2825

13 days 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

13 days 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

12 days 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

13 days ago, # |

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

→ Reply

treasuryonly

13 days ago, # ^ |

You can use long long instead of int.

→ Reply

arceus31

13 days 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

13 days 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

13 days ago, # |

Thanks for such a great contest. I loved it

→ Reply

cseshamim47

13 days ago, # |

How to solve C?

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

→ Reply

treasuryonly

13 days 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

13 days ago, # ^ |

ohh shit. I misread the constraint :(

→ Reply

peti1234

13 days ago, # |

+43

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

→ Reply

Sreedhar3210

13 days ago, # ^ |

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

→ Reply

nxsang1611

13 days ago, # ^ |

Orz it's really the same

→ Reply

whiitex

13 days 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

13 days ago, # |

I am unable to figure out why my C is failing

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

It fails on 1110 testcase on Unit Test 2.

→ Reply

chipi_chipi

13 days ago, # ^ |

mine fails on 1108 in the same testcase

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

i spent so much time on this problem :(

→ Reply

olegator2007

13 days ago, # |

← Rev. 2 →

Please explain why D is failing on test 4 261864972.

→ Reply

iLLuSiOnZ

13 days 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

13 days 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

13 days 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

13 days 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

13 days ago, # |

C was unusually hard for Div3. E was nice.

Hopefully back to blue after this one.

→ Reply

Jagnath_Reddy

13 days 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

13 days 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

13 days ago, # ^ |

Your solution is amazing

→ Reply

arajeev210

13 days ago, # ^ |

Thank you :)

→ Reply

pcumamahesh

13 days ago, # ^ |

Yeah, even I did something similar to that. 261823516

→ Reply

Saptak3315

13 days ago, # |

Is E solvable using recursive dp?

→ Reply

amoad

13 days 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

13 days ago, # ^ |

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

→ Reply

manikiran949

13 days ago, # ^ |

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

→ Reply

formidablechief27

13 days 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

13 days 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

13 days ago, # ^ |

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

→ Reply

eshaansodhi

13 days 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

12 days ago, # ^ |

-12

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

→ Reply

Vladosiya

12 days 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

12 days ago, # ^ |

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

→ Reply

spisded

13 days ago, # |

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

→ Reply

shviv1

13 days ago, # ^ |

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

→ Reply

spisded

13 days ago, # ^ |

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

→ Reply

AHMADUL

13 days ago, # |

'C' is quite tricky implementation!!!

→ Reply

rmz

13 days ago, # |

can we solve E with recursive dp ?

→ Reply

OgataShumaHiroyuki

13 days ago, # |

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

→ Reply

Dell_Know

13 days ago, # ^ |

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

→ Reply

OgataShumaHiroyuki

13 days ago, # ^ |

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

→ Reply

Little_Sheep_Yawn

13 days 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

13 days ago, # |

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

→ Reply

theRealChainman

13 days ago, # |

good round, especially like F and G this round.

→ Reply

saelcc03

13 days ago, # |

20 lines of code for problem D

link

who less?

→ Reply

13 days 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

12 days ago, # ^ |

XD You are right. I missed that. Thanks

→ Reply

NULLgorithm

13 days ago, # |

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

→ Reply

AdityaTakkar

13 days 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

13 days ago, # ^ |

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

→ Reply

AdityaTakkar

13 days 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

12 days ago, # ^ |

knapsack

→ Reply

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

13 days 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

13 days 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

13 days 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

13 days ago, # |

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

→ Reply

udta_kouwa

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

13 days 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

13 days 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

12 days 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

12 days 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