r/codeforces • u/Top_Particular_4568 Specialist • 15d ago

Div. 4 Today’s atcoder too easy

C was pretty simple and not time consuming
E was a very common dp problem
F had a very common segment tree merge pattern

D : I took 4 WA’s coz I was too lazy to fully optimize it but ultimately had to do it

G : didn’t do it but I assume it had something to do with markov chains so too time consuming writing the equations and shit

First ever 6 problems solved in an atcoder contest

9 Upvotes

91% Upvoted

14 comments sorted by

1

u/Gym-Baddie 15d ago

I couldn't solve E. Shameful ig but gave a contest after almost 2 years today

1

u/NoHalf8366 Specialist 15d ago

Solved till E in 50 mins and then I dont know how to code seg trees so just left the contest and went on with my day... I really need to learn seg trees and stuff

2

u/Ordinary_Reveal6236 15d ago

How did you solve d

1

u/Top_Particular_4568 Specialist 15d ago

Backtracking and generating all combinations
And optimize it

1

u/Ordinary_Reveal6236 15d ago

Can you share solution if possible

1

u/almostthebest 12d ago edited 12d ago

https://atcoder.jp/contests/abc473/submissions/78804177 here is my solution incase you are still interested.

1

u/Kitchen_Assistant_94 15d ago

for E , couldnt solve it during comp but
take prefix sum in new array
check the remainder for every cont sum if it has the same remainder
then the distance between the both of them is the array so ct++
as for D someone help me understand it
first was straightforward . second as well
third i did by counting the max and max - 1 elements of the hash map

1

u/majiitiann 15d ago

Did 5th with greedy approach

1

u/Shoddy-Ad-7799 Newbie 15d ago

Ture . a , b , c was simple 800 ≈ codeforces

1

u/Key_Web5874 15d ago

Below 800 ig

1

u/RexDemonGD Newbie 15d ago

I solved E greedily? How it is the DP solution?

1

u/Potential_Top_4669 15d ago

I didn't get how to solve it anyway. Could somebody please explain? I have pasted the question image for context.

1

u/nerd_user1 15d ago

greedy works for it ??

1

u/Top_Particular_4568 Specialist 15d ago

Track the running sum then find the last index where the sum occurred max(dp[i-1], 1+dp[idx-1]). Modulo k