Educational Codeforces Round 165 [Rated for Div. 2]

2 weeks ago, # ^ |

If the contest has an interactive problem they should say in the announcement.

→ Reply

Your_Hands_Clean

2 weeks ago, # ^ |

I would like to give you a downvote but because we are in the same community take an upvote.

→ Reply

Rushdi

2 weeks ago, # |

← Rev. 3 →

Edu time I hope A-E is data structures problems , or 2 of them at least

→ Reply

Sandeep_Yadavji

2 weeks ago, # |

All the best guys :) ;

→ Reply

2 weeks ago, # |

The penalty for each incorrect submission until the submission with a full solution is 10 minutes. what this line means, how penalties are given in this case. I know only -50 for wrong submission is a type of penalty.

→ Reply

Rushdi

2 weeks ago, # ^ |

in Edu rounds the leaderboard is sorted Depending on how many problems you solve there is no score
but what if there is 2 people have the same number of problems solve they will sum the times of them and sort it by the person who have less time
but if person got 2WA on a problem then AC the sum of time will increase by 20 which will give him bad leaderboard place

→ Reply

lokas7755

2 weeks ago, # |

Hope able to solve ABC

→ Reply

Mehdi_Ba

2 weeks ago, # |

I hope I don't get negative delta...

→ Reply

hasanovr

2 weeks ago, # |

I wish high rating to participants

→ Reply

2 weeks ago, # ^ |

I done a and b , have you done c ?

→ Reply

2 weeks ago, # ^ |

is it possible in the A,that the min number of invitation can be other than 2 or 3

→ Reply

mzv

2 weeks ago, # ^ |

→ Reply

2 weeks ago, # ^ |

then why my code is failing at test case 2, i can't understand ,is it allowed to share the solution or code

→ Reply

2 weeks ago, # ^ |

You can share the submission id, anyway all submissions are available for all to see. But not during the contest.

→ Reply

13 days ago, # ^ |

can you help to improve my cp skill ?

→ Reply

13 days ago, # ^ |

Yes

→ Reply

https://mirror.codeforces.com/contest/1969/submission/258816464

13 days ago, # ^ |

is it the submission id,actually i don't know

→ Reply

13 days ago, # ^ |

258816464 the number at the end is submission id

→ Reply

13 days ago, # ^ |

→ Reply

rahi088

2 weeks ago, # |

Good luck everyone

→ Reply

xiojoy

2 weeks ago, # |

1800 plz!

→ Reply

avighnakc

2 weeks ago, # ^ |

Doma Umaru?!

→ Reply

xiojoy

2 weeks ago, # ^ |

→ Reply

iamshihab100

2 weeks ago, # |

← Rev. 2 →

-24

Best of luck everyone.

→ Reply

2 weeks ago, # ^ |

+21

Spoiler

→ Reply

nflight11

2 weeks ago, # |

Very long time no see, Educational Codeforces. I wish this contest teach me a lot.

→ Reply

Loganwick

2 weeks ago, # |

BledDest Orz

→ Reply

Sweet

2 weeks ago, # |

+17

pls no guessforces

→ Reply

2 weeks ago, # |

My first Educational round. Hop to get positive delta for everybody.

→ Reply

beyond1991

2 weeks ago, # |

GLHF

→ Reply

Sohib_Avgonov

2 weeks ago, # |

+39

"I wonder how you folks (BledDest, adedalic, Neon, Roms, awoo) come up with so many tasks. It's like you've been holding Educational Rounds since the invention of sliced bread=)

→ Reply

DSP-friendly

2 weeks ago, # |

Will the 12-hour hacking part give any additional score? Will it be possible to hack the solutions of your room during the contest?

→ Reply

DGME

2 weeks ago, # |

+12

Hope everyone will not get stuck in A, B and C.

→ Reply

Astroflexx

2 weeks ago, # |

← Rev. 2 →

-15

Please no stupid constructive/guesswork/made sense only to the author type problems like the last two contests.

→ Reply

senak

2 weeks ago, # |

Please,I want to pupil

→ Reply

yuanzihan

2 weeks ago, # |

Good luck && have fun!!!

→ Reply

yuaksoinocenow

2 weeks ago, # |

-28

It was kinda shitty contest tbh

→ Reply

ibrahimwq

2 weeks ago, # ^ |

because you couldn't solve C?

→ Reply

pb_messi

2 weeks ago, # |

C>>>D. 10 minutes for D and 1hr+(multiple WA) for C.

→ Reply

nichke

2 weeks ago, # ^ |

Isn't C just a standard dp?

→ Reply

2 weeks ago, # ^ |

ah yes because 2D is standard DP. Someone who actually solved C & D

→ Reply

2 weeks ago, # ^ |

what logic you apply while solve d ?

I can not solve c and d !!

→ Reply

2 weeks ago, # ^ |

C : 2D DP with n and k. Where DP[i][j] is maximum subtracted from sum in first i elements with j operations. DP[i][j] = max ( DP [i-q-1][j-q] for all q between 0 and j).

D: Sort all for minimizing Alice's cost. Then, look at all items where Alice pays less than what Bob could pay. Store all of Bob's costs in a min heap priority queue. Bob gets k minimal costs for free. answer = max(sum(Bob) excluding top k elements — sum(Alice)).

→ Reply

13 days ago, # ^ |

Thank you bro, I make you my friend! I star on your profile in order to add in my friend list. To be honest, I am not good in heap priority queue and dp. if you have good material to study then please share it with me. my mail id is : smitrpatel19@gnu.ac.in my linkedin is : https://www.linkedin.com/in/jayambe

→ Reply

jonnnnnsinaga

2 weeks ago, # ^ |

How could you solve greedy problem more easily than the DP problem ?

→ Reply

daanish_shaikh

13 days ago, # ^ |

do you know how to find the testcase which went wrong? as if there are many testcases it is not shown in the submission

→ Reply

BadlyBadCoder

2 weeks ago, # |

can C be treated like the stack of plates problem where you need to take the top plate before taking any plate under it , and you can only take k plates in total ?

→ Reply

2 weeks ago, # |

+28

D <<< C

→ Reply

2 weeks ago, # ^ |

← Rev. 3 →

If you don't mind me asking, what was the solution for D?

→ Reply

2 weeks ago, # ^ |

← Rev. 2 →

Well, firstly sort things by Bobs cost, if equal sort it in decreasing order by Alice cost. Let's say we want to buy first $$$t$$$ things. For all of them we will get max(0, $$$b_i-a_i$$$), if we will additionally buy any $$$k$$$ things (so Bob will choose them). We just need to maintain sum of $$$k$$$ smallest numbers of $$$a_i$$$ to the right of $$$t$$$ and brute-force $$$t$$$ from left to right.

Maybe it's a little bit messy, but this is what i have...

→ Reply

2 weeks ago, # ^ |

thanks brosef I understand now

→ Reply

dimastrakhal

2 weeks ago, # ^ |

C was easy DP, maybe a little tricky to implement.

→ Reply

2 weeks ago, # ^ |

DP itself was not intuitive for me, as we are able to replace $$$a_i$$$ not only with $$$a_{i-1}$$$, but also with $$$a_{i+1}$$$.

→ Reply

AntonioElCamborio

2 weeks ago, # ^ |

Maybe it's easier if you think about the operation as "choose a subarray [l,r] and replace all elements with the subarray minimum".

Then dp[i][j] = minimum sum of subarray [0,j] after applying i operations, and you can iterate over the size of the subarray including the element j (can be 1, 2... k).

→ Reply

2 weeks ago, # ^ |

yeah, that is the observation I needed to solve this.

→ Reply

My solution discussion stream

2 weeks ago, # ^ |

← Rev. 2 →

It's a dime in dozen occasion, lol. I usually manage to solve more complicated problems, rather than easier ones. IDK why rly...

→ Reply

britishcat

2 weeks ago, # |

orz

→ Reply

dp_16

2 weeks ago, # |

Aaaaaaa, I couldn't debug C in time.

→ Reply

aryanc403

2 weeks ago, # |

+11

→ Reply

amoad

2 weeks ago, # |

why my solution is failing for C ?

→ Reply

DuongForeverAlone

2 weeks ago, # ^ |

← Rev. 2 →

It's hard to use greedy for C, or even impossible (I actually think about a lot of ways to use greedy but I found lots of counter examples either, so just use DP is a better approach).

→ Reply

vivek_coder_9

2 weeks ago, # ^ |

Hello DuongForeverAlone sensei, how are you? and plz Can you tell me what is the best way to start DP, so that i can cover all the standard problems of it? and from where? Answer my question Greedily sensei ;)

→ Reply

DuongForeverAlone

13 days ago, # ^ |

Just do it LOL. I have no idea what is the best way to start. Until now there are much topics in DP I haven't covered yet (some DP optimization techniques for example). Heading to codeforces, leetcode, cses, spoj, ... or any other online judges you know and sort to do DP.

→ Reply

dreaM107

13 days ago, # ^ |

I tried difference (Greedy) too, in quite different ways, making array of differences, modifying original array and difference array on each iteration, counting max difference and keep on deleting from the sum. But there is one thing greedy doesn't account for ie repetition in similar differences. Example --> n = 4 k = 2, a = [4, 8, 5, 1] the differences are 4, 3, 4. You chose the first 4 to change, new array is [4, 4, 5, 1] next you choose last 4. final array --> [4, 4, 1, 1], sum = 10 Now in case you choose last 4 to change --> [4, 8, 1, 1] now you choose the difference 7 which gives --> [4, 1, 1, 1], sum = 7.

I haven't practiced DP but as far as I can see from solutions, people tend to be doing similar thing using DP ie a 2D array to keep track of all changes. (I might be wrong on the DP logic since idk how to use DP). But the problem in greedy you faced is same as mine and I presume many more got stuck here.

→ Reply

MADE_IN_HEAVEN

2 weeks ago, # |

Good contest, I liked the problems.

→ Reply

silenttkillerr

2 weeks ago, # |

Idea for D?

→ Reply

nichke

2 weeks ago, # ^ |

Hint: Think in reverse operation order. Suppose you include N elements and want to remove one, what's the optimal strategy for Alice?

→ Reply

BledDest

2 weeks ago, # ^ |

← Rev. 2 →

+33

The model approach is the following one:

Spoiler

→ Reply

2 weeks ago, # ^ |

ah nice explanation, thanks broski

→ Reply

vstiff

2 weeks ago, # ^ |

← Rev. 2 →

Why Bob will take for free most expensive for him, if his goal is to minimize Alice profit? I sorted by $$$b_i-a_i$$$ and got different answer on pretests.

Upd: Think I got it, Alice already paid for entire subset, so it makes sense to sort by $$$b_i$$$

→ Reply

raidencode

13 days ago, # ^ |

Thank you for explanation

→ Reply

SNX03

13 days ago, # ^ |

I sorted the lists based on the decreasing differences in values and it WA on test 3. Basically sorted a list of pairs $$$(b[i]-a[i], i)$$$. Why does this idea fail?

→ Reply

nichke

13 days ago, # ^ |

I believe I have a more "elegant" greedy solution which utilizes different observations so I'd like to share it.

First observe that if Alice selects fixed $$$M$$$ elements, Bob will take the $$$K$$$ with the largest sum of $$$b_i$$$.

Next, observe that Alice never wants to take an element if $$$a_i>b_i$$$. Just consider both cases (Bob takes this element and Bob does not take it) and the answer never becomes worse if Alice excludes it.

Now that we know this, suppose that Alice chooses all elements such that $$$a_i<=b_i$$$, let the count of such elements be $$$l$$$. Let's denote the elements selected by Bob by $$$(a_1,b_1),(a_2,b_2),...,(a_k,b_k)$$$ and the remaining ones by $$$(a_{k+1},b_{k+1}),(a_{k+2},b_{k+2}),...,(a_l,b_l)$$$. We know the total sum for this choice, because Bob chooses greedily the $$$K$$$ largest $$$b_i$$$'s.

Now what happens if Alice wants to choose $$$l-1$$$ elements?

We never want to remove an element that is not already chosen by Bob, because it will just reduce the total sum. If we remove an element $$$(a_p,b_p)$$$ that is chosen by Bob, the total sum increases by $$$a_p$$$ and it can trivially be proved that we can never add $$$b_p$$$ to our total sum in the future by performing removals. So it's always optimal to remove the element with the largest $$$a_p$$$ and instead of it insert the one with the largest $$$b_q$$$ such that $$$(a_q,b_q)$$$ is not present in Bob's set.

We can easily simulate this process using two multisets.

I didn't write the proof in a formal way here, because it would be lengthy, but one can derive it if they want.

Here's my submission 258749293

→ Reply

shleep

2 weeks ago, # ^ |

If Alice chooses some subset of elements, then Bob will pick the $$$K$$$ elements with the highest values of $$$B_i$$$. If we sort the items by $$$B_i$$$, then this just means Bob will always pick the rightmost $$$K$$$ elements in any subset. Therefore, our array will become split into 2 partitions: the left partition's elements go to Alice, and $$$K$$$ of the elements in the right partition go to Bob (we can choose the ones with lowest $$$B_i$$$).

We can do the following: Iterate over the size of the right partition from size $$$K$$$ to size $$$N$$$, and maintain the sum of the smallest $$$K$$$ values of $$$B_i$$$ using a multiset. We then calculate Alice's profit as $$$\max(0, B_i-A_i)$$$ for all elements $$$i$$$ in the left partition, which we maintain with a prefix sum array.

→ Reply

fernandezpalomojosue

13 days ago, # ^ |

← Rev. 2 →

I skip the problem because I thoug the profit can be negative and that's why I never understood the 3 example, that should be specified in the statement. Upd: now i see you can buy an empty set :(.

→ Reply

SNX03

13 days ago, # ^ |

Was buying empty set not mentioned during contest?

→ Reply

JakobZ

2 weeks ago, # |

Best contest ever!!! I very much enjoyed it :)

→ Reply

mzv

2 weeks ago, # |

great contest, even tho idk how greedy works in D

→ Reply

AkiLotus

2 weeks ago, # |

I bruteforced sorting criteria for D and resulted in a +7 AC... what a way to live... XD

Anyway, anyone can prove the validity of D? My (greedy) approach is to sort everything, first on Alice's buying cost in increasing order, then Alice's theoretical profit (assuming Bob doesn't take anything for free) in decreasing order.

→ Reply

Abito

2 weeks ago, # ^ |

+11

Let's think of a strategy for Bob. If I take s elements (s>k) then he will choose s-k elements with the minimum b. That's obviously true because sum of a is fixed and to minimize the profit Bob will choose the smallest bs. Now, I'm Alice and I know that. Then I wiill check each b. If I fix some b[i], then for all b[j] such that j>i I will choose minimum k as from them. I know that since they are k and Bob will choose minimum bs, he will not choose from them. So now remains the elements in the prefix of i. Any element I will choose in this prefix, Bob will choose it too. So I want all positive profits in this prefix. I'm not sure if this is kind of a proof, but this was my though process.

→ Reply

alpha1215

2 weeks ago, # |

can someone please tell why is this giving WA on 3 is there any logic error or bug

code

#include<bits/stdc++.h>
using namespace std; 
char nl = '\n';
using i64 = long long;

void solve(int t) {
    // cout << "test #" << t << << nl;
    int n, k; cin >> n >> k;
    vector<pair<i64, i64>> A(n);
    for(auto& a : A) cin >> a.first;
    for(auto& a : A) cin >> a.second;
    sort(A.begin(), A.end(), [&](pair<i64, i64>& a, pair<i64, i64>& b) -> bool {
        return a.second - a.first > b.second - b.first; 
    });
    // for(auto& a : A) cout << a.first << " " << a.second << nl;
    i64 cur = 0;
    i64 ans = 0;
    multiset<i64> st;
    for(int i = 0; i < n; i++) {
        cur -= A[i].first;
        st.insert(A[i].second);
        if(st.size() > k) {
            i64 x = *st.begin();
            st.erase(st.begin());
            cur += x;
            ans = max(ans, cur);
        }
    }
    cout << ans << nl;
} 

int main() {
    int tt = 1;
    cin >> tt;
    for(int t = 1; t <= tt; t++) solve(t);
}

→ Reply

alagorithmet

2 weeks ago, # ^ |

I also had WA on 3, does someone have a counter example which I may have overlooked?

"wrong answer 14th numbers differ — expected: '14', found: '13'"

→ Reply

smit_384

13 days ago, # ^ |

← Rev. 2 →

did you find counter case? ( I am getting wrong answer on same tc) My Code

→ Reply

alagorithmet

13 days ago, # ^ |

nope, but I will write here if I manage to find.

→ Reply

polsage

2 weeks ago, # ^ |

← Rev. 2 →

try for this test case:

4 1

1 1 3 9

3 4 5 15

here you will get 0 but answer is 2

→ Reply

warks

2 weeks ago, # |

TFW you get a WA a couple minutes before the contest ends and out of supreme luck, you unknowingly click "Mobile Version" on Codeforces and instead of debugging your code, you end up debugging what just happened 🙃

Icing on the cake

// All you had to "un"-debug :')
ImplicitSegmentTree st = new ImplicitSegmentTree(0, 5);
// ImplicitSegmentTree st = new ImplicitSegmentTree(0, 1_000_000_001);

→ Reply

warks

2 weeks ago, # ^ |

Tip (to self, others):
Whenever changing limits like this for debugging purposes — it's probably best to add print statements alongside (so that you remember to fix this as well)
Alternatively, in languages where there is support for compiler-warnings, add those :)

→ Reply

parag776

2 weeks ago, # ^ |

i needed this tip too!

→ Reply

The-Winner

2 weeks ago, # |

I got AC on problem E one minute after the contest ended. The problems were really nice, thanks

→ Reply

2 weeks ago, # ^ |

Sigma

→ Reply

Bosscoder

2 weeks ago, # |

← Rev. 2 →

https://mirror.codeforces.com/contest/1969/submission/258748770 How to memoize this recursive approach to C ? Or any other recursive solution ?

→ Reply

alpha_6124

2 weeks ago, # ^ |

simple recursive 258735237

→ Reply

nectarl

2 weeks ago, # |

what's the idea for c? I couldn't debug my dp solution in time, with mp[j][val] standing for j operations used and the last value being val. since val could be huge, i used unordered_map to store the status. and to avoid space overflow, status with the values that aren't possible to be at the end for current moment need to be erased. or is there a much easier solution?

→ Reply

2 weeks ago, # ^ |

k is less than 10 so you can solve with 2D DP.

→ Reply

alagorithmet

2 weeks ago, # ^ |

bruh I thought $$$k \leq n$$$ and couldn't come up with anything. can't believe I have misread that

→ Reply

prashant51102

2 weeks ago, # ^ |

I can't believe that I missed it. regretting a lot now.

knowing the constraint k <= 10 makes the problem way easier.

→ Reply

Astroflexx

2 weeks ago, # ^ |

I did the same but got WA 5 times

→ Reply

SeeleVollerei_

2 weeks ago, # |

It seems like the time limit of E is too tight. Submission https://mirror.codeforces.com/contest/1969/submission/258765134 got TLE on test 25 by using BTreeSet, however, submission https://mirror.codeforces.com/contest/1969/submission/258766945 got AC by using HashSet (it was simply replaced BTreeSet as HashSet)

→ Reply

TakakuraAnri

2 weeks ago, # ^ |

← Rev. 2 →

+17

E can solve by Monotonic Stack in O(n),so the timelimit is enough. Code

→ Reply

ANON7MOUS

2 weeks ago, # |

Can anyone please explain me the DP approach to solve problem c?

→ Reply

Steven-_-AbuAlkhair

2 weeks ago, # ^ |

do dp range and the cost is the min element in range * length of range

→ Reply

ANON7MOUS

2 weeks ago, # ^ |

okey let me try then

→ Reply

shleep

2 weeks ago, # ^ |

$$$dp[i][j]$$$ = the minimum sum when we only consider the first $$$i$$$ elements, and perform $$$j$$$ operations. We can do $$$dp[i][j] = dp[i-1][j] + A_i$$$ to do nothing. Suppose we perform $$$x$$$ moves: we convert elements $$$A_{i-x}, ..., A_{i}$$$ to the minimum element in this range (call it $$$min$$$), and the new sum of this range is $$$(x+1)*min$$$. The minimum sum for the remaining elements can be obtained with $$$dp[i-1-x][y]$$$, where $$$y$$$ is the # of moves performed beforehand. Therefore, we do $$$dp[i][x+y] = (x+1)*min + dp[i-1-x][y]$$$ for all pairs $$$(x,y)$$$ where $$$x+y \le K$$$.

→ Reply

ANON7MOUS

2 weeks ago, # ^ |

thanx for explaining the states and transitions

→ Reply

AvaraKedavra

2 weeks ago, # ^ |

← Rev. 2 →

If I define dp[i][j], the maximum sum of elements I am able to delete, if I am at index i and perform j operations. Then I subtract the maximum value of dp[i][j] from the total original sum of the array, why am I getting wrong answer ?

Edit — Resolved. Should have used long long.

Code

ll n,k;
    cin>>n>>k;
    int dp[n+2][k+1];
    memset(dp,0,sizeof(dp));
    vector<ll>arr(n+1);
    ll totSum = 0;
    vector<ll>pref(n+1);
    vector<ll>vect;
    for(ll i=1;i<=n;++i){
        cin>>arr[i];
        totSum+=arr[i];
        pref[i]+=pref[i-1]+arr[i];
    }
    ll maxSumDeleted = 0;
    for(ll i=n;i>=1;--i){
        for(ll j=0;j<=k;++j){
            ll start = i;
            ll end = i+j;
            if(end>n){
                continue;
            }
            ll sum = pref[end]-pref[i-1];
            ll elemsReduced = j+1;
            // ll minElement = query(1,0,n-1,start-1,end-1);
            ll minElement = LONG_LONG_MAX;
            for(ll helper=start;helper<=end;++helper){
                minElement = min(minElement,arr[helper]);
            }
            ll totalGain = max(0,sum-elemsReduced*minElement);
            // if(j==0){
            //     totalGain = 0;
            // }
            for(ll l=0;l<=k;++l){
                if(j+l>k){
                    break;
                }
                dp[i][j+l]=max(dp[i][j+l],totalGain+dp[end+1][l]);
                maxSumDeleted = max(maxSumDeleted,dp[i][j+l]);
            }
        }
    }
    cout<<totSum-maxSumDeleted<<endl;

→ Reply

2 weeks ago, # |

My second educational round, and again not solve C. So educational round means high difficulty??? Both two my edu round solve only AB and rank 3600+ (:_;)

I'm going to be specialist and hope to get my rate back in div3 round a few days later X(

→ Reply

DuongForeverAlone

2 weeks ago, # ^ |

C is not too hard, but not too easy in this round. If you take a look at previous Edu round, it is something really different, so it doesn't mean high difficulty

→ Reply

2 weeks ago, # ^ |

-7

Maybe I just to weak in 2D or 3D dp (:_;).

And I determined to try to come up with a greedy solution, till the end of round. Although I've imagined this is probably a dp, I refused to go ahead because I thought I have little chance to solve a 2D dp problem (x_x;)

→ Reply

Red0

2 weeks ago, # ^ |

Or you could do tmrw's Div. 2 and somehow solve A-D :)

→ Reply

Enmendurana

13 days ago, # ^ |

why u lying?? ur 1. edu u solved ABC

→ Reply

13 days ago, # ^ |

Oops, it was two rounds that were really close and I mistakenly remember this, sorry. It was actually the round right after that edu round:(

→ Reply

Astroflexx

2 weeks ago, # |

+21

Fantastic Edu round as always. Thanks a lot BledDest awoo adedalic Neon Roms and all testers!

→ Reply

Bob_Wang

2 weeks ago, # |

+16

I posted my code of problem D in the last 10 seconds, but the evaluator didn't receive it.

After the contest finished, I reposted my code, and then it was accepted.

Now I wanna die right now.

→ Reply

2 weeks ago, # ^ |

sorry man

→ Reply

RahulS2003

2 weeks ago, # |

← Rev. 2 →

Can anyone please check the error in this code for C?

Solution

→ Reply

amoad

2 weeks ago, # ^ |

we pretty much used the same approach , but the problem meant to be solved using DP and not greedy

→ Reply

mzv

2 weeks ago, # ^ |

← Rev. 2 →

are you using greedy? well, this case doesn't work for greedy

5 4
999 999 2 3 1

→ Reply

tickbird

2 weeks ago, # |

C was bit hard for its position.

→ Reply

md_nihal

2 weeks ago, # ^ |

I believe it's my skill issue:) it was a good problem actually

→ Reply

2 weeks ago, # ^ |

hard to implement. Not hard to solve.

→ Reply

silenttkillerr

2 weeks ago, # |

Any counter Test for this https://mirror.codeforces.com/contest/1969/submission/258771109

→ Reply

alpha1215

2 weeks ago, # |

C was obvious dp don't why some people found D easier than C is it because there is some standard idea / technique if so please tell me. Thanks!

→ Reply

34z12000

2 weeks ago, # ^ |

I'd say both are pretty obvious. Personally, I just found them hard to implement

→ Reply

alpha1215

2 weeks ago, # ^ |

can you please tell me what's wrong with this

→ Reply

34z12000

2 weeks ago, # ^ |

can't say, sorry

→ Reply

Tsovak

2 weeks ago, # |

← Rev. 2 →

+22

Many solutions to problem A, including mine, are hacked, because of set.

How is it possible? The time complexity is $$$O(t∗n∗(n−1)/2∗4∗log(4))=O(5∗10^7)$$$ which should not work longer, than 2 seconds.

I have solved ABCDE, and would become a master, if my solution to A wasn't hacked :(

→ Reply

DrunkTourist

2 weeks ago, # ^ |

We'll stay forever this way You are safe in my heart And my heart will go on and on

→ Reply

shohagfaraji

2 weeks ago, # ^ |

Pardon me if I'm mistaken, The time complexity of your code is O(t∗n∗n∗O(n)) = O(6∗10⁹). As inner clr(set) takes O(n) in every iteration.

→ Reply

BiNARyBeastt

2 weeks ago, # ^ |

He always just pushes 4 elements to the set and clears it, so clearing the set doesn't take o(n). It takes o(4).

→ Reply

returnAC

2 weeks ago, # ^ |

+24

o(4)

→ Reply

el_tunel

2 weeks ago, # ^ |

+30

std::set has a lot of overhead as it uses a tree structure, so you end up using a lot of time allocating and deallocating memory, rebalancing the tree, etc.

→ Reply

Abito

2 weeks ago, # ^ |

My solution is the same, but the only difference is that you clear the set, I define a new one each time. I think this is the reason why you take more time on the original tests and got hacked.

→ Reply

13 days ago, # ^ |

i'm surprised that your solution din't get hacked. this one did get hacked tho. He also created a new set.

→ Reply

Abito

13 days ago, # ^ |

maybe because he's declaring vectors and calling a solve function? I think the smallest differences can make my 1968ms get tle

→ Reply

13 days ago, # ^ |

i found the place or the hole in the code which gives allows the hack to give TLE. Its the fact that the code does n^2 iteration, still no proof how tho. you code does $$$ \frac{n(n-1)}{2} $$$ iterations. I think that can make a proof. I tried both. Your approach just passes with 1999ms. The others don't. and that too if we don't use function call and stuff. A normal while(t--) loop passes barely but doing anything other that will not work. even if you do $$$ j = i+1$$$ it still gives TLE on test 4. creating a vector also doesn't make any different if we do $$$\frac{n(n-1)}{2}$$$ iterations.

I tried finding the issue but I couldn't and this is the information i was able to discover. any details would be really appreciated by some experienced coder.

→ Reply

EduardoBrito

13 days ago, # ^ |

I think it is because of the chosen compiler. I was reading this blog and I think the reason is that GNU C++17(64) and GNU C++20(64) is better than GNU C++17

→ Reply

13 days ago, # ^ |

i use c++ 20. you can refer to my submissions.

→ Reply

EduardoBrito

13 days ago, # ^ |

Don't use endl

→ Reply

13 days ago, # ^ |

i don't think that particularly causes the issue. A master friend of mine told that its because of high constant factor of stl::set()

→ Reply

coder0687

2 weeks ago, # |

-8

why my solution for problem C 258776010 getting Runtime Error

→ Reply

aryanc403

2 weeks ago, # |

For problem E 258747661 should be hackable. I have no proof on the bound of the no of iterations.

→ Reply

thesuaveguy

2 weeks ago, # |

Hi! can someone please point where I'm going wrong in task D. Any help is appreciated :)

258782796

→ Reply

Middlemist

2 weeks ago, # |

← Rev. 4 →

Can anyone tell me where this approach for q3 is going wrong? I'm maintaining a last variable which is what was the last element in vector I'm iterating 258774405 aryanc403 can you help me with this ?

→ Reply

copyPasteCoder

2 weeks ago, # |

-9

Can anyone explain what does it mean "Generator is not determinate [the verification run produces different output, cmd =7 4956565656565656564512121], [1100006 bytes, '1000 300 6 151 55 114 76 65 24 12 86 135 38 98 2...290 266 282 34 73 297 245 5 118 261 79 200 35 ', sha1=f0a1c17d87899a11c1db8f805df18da45b1251d5] vs. [1100006 bytes, '1000 300 2 151 55 114 76 65 24 12 86 135 38 98 2...290 266 282 34 73 297 245 5 118 261 79 200 35 ', sha1=a2117fdfb95eb249f578f57f01f328e2a91fc766]."

→ Reply

Middlemist

2 weeks ago, # ^ |

It's a RTE

→ Reply

_Kee

2 weeks ago, # ^ |

A generator must be deterministic, that is, it must produce the same output every time it's run. If you use RNG, you must set a random seed.

→ Reply

mehtasanchit3

2 weeks ago, # |

-8

I solved only one question A will I get rating

→ Reply

haaki

2 weeks ago, # |

Could someone help me understand how my reasoning for C is wrong? I'm failing cases but I can't understand why 258783884

My thought process was to: keep indexes grouped and sorted by max(a[i]-a[i-1], a[i], a[i+1]) (max diff between its neighbours). Then for each K get the current maximum difference, update the element at i with min(a[i-1], a[i+1]), and keep track of how much the sum is being reduced by. Finally, update diff for (i-1) and (i+1) since arr[i] has been modified.

→ Reply

Aniket_719

2 weeks ago, # ^ |

Just think about test case 1 3 2 1 2 6

U will get your answer

→ Reply

Aniket_719

2 weeks ago, # ^ |

T= 1 N= 3 K =2 Arr: [1 2 6]

→ Reply

haaki

2 weeks ago, # ^ |

ah, I see I can't be greedy. Thanks!

→ Reply

defnotmee

2 weeks ago, # |

+13

I really liked problems D and E!

→ Reply

tickbird

2 weeks ago, # |

-8

Solution on C using DSU

#include <bits/stdc++.h>
using namespace std;

struct DSU {
    std::vector<int> f, siz;
    
    DSU() {}
    DSU(int n) {
        init(n);
    }
    
    void init(int n) {
        f.resize(n);
        std::iota(f.begin(), f.end(), 0);
        siz.assign(n, 1);
    }
    
    int find(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    
    bool merge(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        }
        siz[x] += siz[y];
        f[y] = x;
        return true;
    }
    
    int size(int x) {
        return siz[find(x)];
    }
};

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T; cin >> T; nxt: while(T--)
    {
    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (auto &x: a) cin >> x;

    DSU dsu(n);

    while (k--) {
        long long best = -1;
        int id = -1, dir = 0;
        for (int i = 0; i < n - 1; i++) {
            int cur = dsu.find(i), nxt = dsu.find(i + 1);
            if (cur == nxt) continue;
            long long cmp = 0;
            long long diff = 0;
            if (a[cur] < a[nxt]) {
                diff = a[nxt] - a[cur];
                cmp = diff * dsu.size(nxt);
                if (best < cmp) {
                    best = cmp;
                    id = i, dir = 1;
                }
            } else {
                diff = a[cur] - a[nxt];
                cmp = diff * dsu.size(cur);
                if (best < cmp) {
                    best = cmp;
                    id = i, dir = 0;
                }
            }
        }
        if (best != -1) {
            if (dir) {
                dsu.merge(id, id + 1);
            } else {
                dsu.merge(id + 1, id);
            }
        }
    }

    long long ans = 0;
    for (int i = 0; i < n; i++) {
        ans += a[dsu.find(i)];
    }
    cout << ans << "\n";
    }
}

can anyone provide counter example? I don't see any reason why this not working.

→ Reply

lhardt

2 weeks ago, # ^ |

You are applying a greedy algorithm, i.e. merging the immediate best, rather than doing a deeper search.

For example,

1 5 2 20 10 19 28

Your algorithm will see the largest difference (20-10) and merge them, and then merge 19 together, totaling 10+10+10+28 = 58. but the optimal solution would be 20+10+10+10 = 50

→ Reply

Quasicoherent

2 weeks ago, # |

← Rev. 2 →

I just spent quite a while debugging my solution to C, which I was confident was correct but failed on test 5 due to a runtime error. It turns out that it was a stack overflow error, and after I increased the stack size, my solution passed (original, with increased stack size). I feel that I should have gotten credit for my original solution during the contest since it would have passed within the given time and memory constraints and only failed due to a restriction in the judging environment.

→ Reply

2 weeks ago, # ^ |

reject memoization, embrace tabulation

→ Reply

TakakuraAnri

2 weeks ago, # |

← Rev. 2 →

+20

I have solve the problem E by Monotonic Stack in O(n).

The submission

→ Reply

Tom66

2 weeks ago, # ^ |

It's a stack.

→ Reply

anucode

2 weeks ago, # |

Idea for c ?

→ Reply

moonshy

2 weeks ago, # |

looking forward to the tutorial

→ Reply

pb_messi

2 weeks ago, # |

How to solve E?

→ Reply

black_big_cock

2 weeks ago, # ^ |

← Rev. 3 →

let st[i] be the largest j so that j < i and the subarray [j, i] is not unique (if j doesnt exist, st[i] = inf).

Now, if st[i] < i (for i = 1 -> n), we have a segment [st[i], i], now the problem becomes: calculate the minimum number of black points so that each segment contains at least 1 black point. It's easy to solve using deque and dp.

→ Reply

harsh_bamane17

2 weeks ago, # |

do we have penalty for wrong hacking attempt?

→ Reply

Zaoldyeck

2 weeks ago, # |

-6

Could someone explain why this solution was hacked in problem A? Here's the link to the submission: link. It's supposed to be ( n^2 ) and should pass. Can someone verify if the test validator is working correctly?

awoo adedalic BledDest Neon Roms

→ Reply

Bungmint

2 weeks ago, # ^ |

← Rev. 2 →

made a mistake, but set has a high overhead for each operation.

→ Reply

nxsang1611

2 weeks ago, # |

Good edu round :)

→ Reply

OneMoreWA

2 weeks ago, # |

Can someone please suggest problems that are similiar to Yesterday's 2C

→ Reply

2 weeks ago, # |

specialist in this contest, only able to solve A and B but in 10 mins so i got descent rank.

→ Reply

hacaravaca

2 weeks ago, # |

Could someone please tell me why this contest didn't count towards my rating? I did the registration as usual

→ Reply

DSP-friendly

2 weeks ago, # ^ |

We just need to wait for the update of the ratings. It usually takes a few hours after the contest end.

→ Reply

2 weeks ago, # ^ |

is the system testing over?

→ Reply

DSP-friendly

2 weeks ago, # ^ |

In the standings title it is said they are final. Except, probably, for the cheaters.

→ Reply

2 weeks ago, # ^ |

How cf finds cheaters?

→ Reply

nxsang1611

13 days ago, # |

where's the contest?

→ Reply

The-Winner

13 days ago, # |

Until the editorial gets published, can anyone provide some help regarding problem F? I've been thinking of some DP, where $$$dp_i$$$ = number of coins you can get if you start with a full unique deck and have the last $$$i$$$ cards in the stack. I tried to come up with the transitions but I am missing something. Thank you in advance!

→ Reply

Geothermal

13 days ago, # ^ |

Assuming “full unique deck” means one card of each number, you’re on the right track. In terms of transitions, here are some questions to think about:

Suppose you want to transition from turn i to turn j. How can you determine which cards to discard on turn i in order to end up with cards 1..k on turn j? (Try writing out a few small cases.)
How does discarding cards affect the number of pairs you can make? (It helped me to think about your DP state as minimizing the number of pairs you eliminate from the deck. How does discarding a card with an odd number of occurrences differ from discarding a card with an even number of occurrences?)

→ Reply

The-Winner

13 days ago, # ^ |

+18

Thank you very much, the confirmation that I am on the right track motivated me to keep going. I just got AC on it

→ Reply

dougalves

13 days ago, # |

-11

Congrats to OliviaRodrigo who did very well on the contest! Big fan of your songs here!!

→ Reply

OliviaRodrigo

13 days ago, # ^ |

Can't Catch Me Now

→ Reply

udta_kouwa

13 days ago, # |

← Rev. 2 →

For problem B pre-test did'nt include overflow cases. :cry

→ Reply

13 days ago, # ^ |

you using long long for ans i dont think its overflow

→ Reply

udta_kouwa

13 days ago, # ^ |

its overflow check my new submission.

→ Reply

13 days ago, # ^ |

yeh i see now , next time make sure use long long everywhere. thats the same thing happened to me one time now i use long long mostly.

→ Reply

Xing_ke

13 days ago, # |

Why are these two codes the same, but one Ce and one Ac？ When the hack ended, it was still Ac, but now it looks like it has changed to Ce. 258710579 and 258844106. I need some help.

→ Reply

Go8

13 days ago, # |

+27

Will the rating changes before 942??

→ Reply

_Lactosi

13 days ago, # |

← Rev. 2 →

Could someone explain me why this https://mirror.codeforces.com/contest/1969/submission/258724763 code for B got AC on pretests and now is getting WA on test 1? I understand why it fails but why didnt it got WA on the same test during the contest?

→ Reply

13 days ago, # ^ |

-8

i think they know there is some problem thats why rating still not updated

→ Reply

13 days ago, # ^ |

It's probably cause by ub(undefined behavior). You tried to get the front of an empty deque in int first=v.front();. And maybe in the pretest, this behavior somehow get a value that can pass test 1.

→ Reply

_Lactosi

13 days ago, # ^ |

How does undefined behavior work? Because it had to give a correct answer for every case formed only by '0's, and if it was so, why not after pretest?

→ Reply