Educational Codeforces Round 166 [Rated for Div. 2]

3 weeks ago, # |

+16

need +1

→ Reply

_dexterDynamo_

3 weeks ago, # |

Hope everything goes well !!

→ Reply

piaolianggg

3 weeks ago, # |

+48

Am I the only one for who the contest page is broken? I can't read problem statements or watch standings or submit.

→ Reply

3 weeks ago, # ^ |

Probably among a handful at best. Pretty sure the blog would be lambasted otherwise.

→ Reply

CallmeSourav

3 weeks ago, # ^ |

yes I am also the handful one

→ Reply

vstiff

3 weeks ago, # |

Nice problems, but solved only ABC. Sure D is simple counting with stack, but couldn't quite figure out till the end.

→ Reply

CallmeSourav

3 weeks ago, # |

today first 10 min my codeforces didnt run well

→ Reply

MrPython

3 weeks ago, # |

← Rev. 2 →

+35

Bad network

I've wasted about 30 minutes because of 502 and cloudflare

→ Reply

kryptx

3 weeks ago, # ^ |

+10

It was constantly showing an error on Brave browser. The issue was resolved when I switched to chrome for some reason.

→ Reply

I_Love_Diar_Narumov

3 weeks ago, # |

← Rev. 2 →

I opened a B! :)

→ Reply

tickbird

3 weeks ago, # |

-31

had 11 WA2 and took 1.5 hours on problem B until get AC

couldn't solve C

worst nightmare for me, expecting -150 delta

→ Reply

pokeland157

3 weeks ago, # ^ |

+20

but.. you didn't even give the contest?

→ Reply

sweet_samosa

3 weeks ago, # ^ |

alt probably

→ Reply

1.618034

2 weeks ago, # ^ |

← Rev. 2 →

+13

Yes, it seem, this tickbird is made for leaving comments only. Here is his alt jinsu

→ Reply

red_one_fine_day

3 weeks ago, # |

what is the idea for D?

→ Reply

3 weeks ago, # ^ |

+12

Let $$$b$$$ be array of string balance. Then, if you do operation on $$$(l,r)$$$ you change all $$$b_i$$$ $$$(l \le i \le r)$$$ to $$$2 \cdot b_{l-1} - b_i$$$.

→ Reply

papa-ka-para

3 weeks ago, # ^ |

Hint — 0

We can only reverse EVEN length segments. We can only reverse segments, where number of '(' is equal to number of ')'.

Hint — 1.

Lets take one sample string -> (((( )))) . Figure out, how many possible reversals are there.

Hint — 2.

We are allowed to reverse till last two '('. We can not reverse last three '(' . Why ?

To get an answer to above question, try this on pen-paper...

Keep one counter. Initial value of the counter = 0;
Travel the string from left to right. When you encounter '(' , counter++, else counter--, Store above values into some array.

→ Reply

rtckyw_

3 weeks ago, # ^ |

← Rev. 3 →

+10

For each segment start l we want to count number of correct segments' ends r, such that sequence remains balanced, and that means:

$$$ count_{opened-to-l} - count_{closed-to-l} == count_{opened-to-r} - count_{closed-to-r}$$$, otherwise we will change the balance of whole sequence and it will become irregular.
Suppose balance of l-th place is $$$k$$$. Then between l and r there can't be a position with balance $$$\geq 2*k + 1$$$, otherwise there will be a position, where we open (after operation we close) more than k brackets, meaning our balance goes below zero, then sequence is also incorrect.

Counting suitable ends can be done with grouping positions by balance and binary search

→ Reply

DogAndCat

3 weeks ago, # ^ |

Here is my solution.

diff_cnt -- counter the different between the number of '(' and the number of ')'
Since the diff_cnt will decrease later, we just do diff_map[(diff_cnt[i]-1)/2] = 0; The different from 0 to diff_cnt[i]-1)/2 is invalid. But other value will be set later.
For each position the answer will be all position of current diff_cnt. ( ans += diff_map[diff_cnt[i]]; ) Because the difference between these position is 0.
map<int, int> diff_map; for(int i=1;i<=s.size();i++) { ans += diff_map[diff_cnt[i]]; diff_map[diff_cnt[i]]++; diff_map[(diff_cnt[i]-1)/2] = 0; // cout << "diff cnt: " << diff_cnt[i] << " map: " << diff_map[diff_cnt[i]] << endl; } cout << ans << endl;

263353060

→ Reply

papa-ka-para

3 weeks ago, # |

Excellent mental exercise... Loved the problems.

→ Reply

the_last_smilodon

3 weeks ago, # |

+36

thank you for the contest. :)

I really enjoyed solving C today.

Said no one ever!

→ Reply

OMgL

3 weeks ago, # |

I don't really understand C

For the last test case 3 1 4 3 3 4 1 5 5 4 5 2 and for the 3rd candidate (programming skill, and testing skills) would be (4, 5) (3, 5) (4, 5) (1, 2) we need 3 programmers and 1 tester so for the 1 tester we take the 2nd candidate (3, 5) and for the 3 programmers we take (4, 5) (4, 5) (1, 2) Doesn't that mean the result is 5 + 4 + 4 + 1 = 14? why is it 13?

→ Reply

Sudip809

3 weeks ago, # ^ |

since first candidate is having higher testing skil, he must be consider as the tester.

→ Reply

_Tawsif_

3 weeks ago, # ^ |

When you're skipping 3rd one,the tester shouldn't be the 2nd one rather 1st one because according to the statement until programmer or tester slot is not filled, you should always take the one with greater skill value.As the first one's testing skill is more than programming skill and tester slot is not filled yet(initially 0),you should take the first one as tester and rest as programmers.

→ Reply

ngmh

3 weeks ago, # ^ |

you have to assign in order, so the first candidate will be assigned as a tester since his bi (5) > ai (4), then the second candidate will be assigned as programmer

→ Reply

OMgL

3 weeks ago, # ^ |

ah I just thought since it was most suitable position, I thought I had to get the max possible value. Dam I actually did so much extra stuff when I could have solved it

→ Reply

3 weeks ago, # |

I could not figure it out a case where the output is zero for Problem B , I guess this is where I got WA, could anyone provide one please? Thanks in advance!

→ Reply

3 weeks ago, # ^ |

you always need to do the copy operation once so the answer can never be zero

→ Reply

3 weeks ago, # ^ |

Exactly, however in the problem statement it mentions that the number of operations made can be possibly zero, this is the part I am not getting, how can it be zero if we need to do copy operation?

→ Reply

3 weeks ago, # ^ |

maybe a mistake

→ Reply

Aniket_719

3 weeks ago, # ^ |

I just check the meaning of "aforementioned" that means change in value by increasing or decreasing so that possible that we wont change

So it's correct statement

→ Reply

3 weeks ago, # ^ |

It's not correct because copying counts as an aforementioned operation

→ Reply

Aniket_719

3 weeks ago, # ^ |

The minimum answer for this problem is one because when we move any element of A to last it will cost us 1, So we won't get 0 as output

→ Reply

3 weeks ago, # ^ |

← Rev. 2 →

your code is wrong because if lastIncluded is false at the end of the iteration you just add one but more than that many operations might be needed

→ Reply

3 weeks ago, # ^ |

Thank you for your feedback, so I added lastIncluded to check if the last value of array b is included or not when transforming the other elements of the array a, if it is included then it means I do not have to perform an extra operation to convert it; as at some point it could be appended to array a and match last element of b. In the case is not included then I need to add an extra change to match last element of b.

→ Reply

https://codeforces.com/contest/1976/submission/263361104

3 weeks ago, # ^ |

Your point was right, just got it accepted, needed to check for more operations instead of adding just one; I thought during the contest that it had to be with possibility of zero, thanks for your help

→ Reply

Ovetsar_ilish

3 weeks ago, # |

Aah i missed updating the condition in A!! Cost me wayy to much

→ Reply

Saivishwas

3 weeks ago, # ^ |

simple solution for A, if string is sorted YES else NO

→ Reply

Raks_splunk

3 weeks ago, # ^ |

Couldn't think of this in the contest so just brute forced it but damn, how did i miss this observation.

→ Reply

ngmh

3 weeks ago, # |

← Rev. 2 →

i solved D one minute after contest ended :(

May/31/2024 00:36UTC+8 263359883

→ Reply

JoeDelaney2012

3 weeks ago, # |

← Rev. 3 →

If someone could explain why I have a Runtime error on this PyPy submission (problem C) I would really appreciate it.

Nevermind, after the contest ends you can see the error messages, it's a stack overflow.

→ Reply

DeludedMaster

3 weeks ago, # |

← Rev. 4 →

Can Someone spot the mistake in my code or tell the test case ? I know the logic is correct but i am unable to find the error.

https://codeforces.com/contest/1976/submission/263360996

if someone does it, he will be blessed with high ratings :)

→ Reply

3 weeks ago, # |

3 wa's for problem 1...i think its time to leave :(

→ Reply

Blank_404

3 weeks ago, # ^ |

← Rev. 2 →

Don't leave. Keep trying you will do better. I saw, you solved both A and B which is great! You shouldn't be demotivated by few WAs.

→ Reply

3 weeks ago, # ^ |

thanks :))

→ Reply

lv.zheng

3 weeks ago, # |

← Rev. 9 →

Solution for D with step-by-step optimizations:

263354202

First preprocess this thing to arr:

()((())())
1012321210

For every starting position pos, the valid number of ranges is "count of idx such that arr[idx]==arr[pos]", where idx must be between pos+1 and last, where last is "the first position after pos such that arr[last] > 2*arr[pos]" (because positive is subtraction after inverse, we need 2*arr[pos] to clear it to zero, and one more to make it invalid)

Now we need two lookups:

find_first_gt_from finds the position of the first value greater than x starting from pos.
count_equal_in_range counts the number of items equal to x in range [first, last).

find_first_gt_from is optimized with map<value, vector<pos>> and lower_bound. While count_equal_in_range is optimized with binary search plus range_max, which can be optimized with a sparse table.

→ Reply

Arthis

3 weeks ago, # |

How to solve C?

→ Reply

arajeev210

3 weeks ago, # ^ |

Calculate the answer for answer[n+m+1], call it sum. Store the job given to each indices in this arrangement(You can use a set for example). Also, store the first instance where someone's job flipped(i.e. they were more skilled in testing but only programming is left, or vice versa). Notice that after that, there are no more flips of the opposite manner, since after a flip, every job is the same. Finally, just run through from 1 to n+m, and pretend to remove this persons job. It would go to either a) the first person flipped infront of this index(in which case their job goes to the last person) or to the last person. For a more formal look, you can checkout my sol here 263338267

→ Reply

teejorob

3 weeks ago, # ^ |

263401471 thanks for the logic bro

→ Reply

vstiff

3 weeks ago, # ^ |

Simplest is bruteforce with memoization, because taking/skipping 1 element will affect very few elements.

But of course there much more clever solutions

→ Reply

_Gawd_

3 weeks ago, # |

+15

is carrot working for anyone?

→ Reply

3 weeks ago, # ^ |

+20

→ Reply

shorya1835

3 weeks ago, # |

damn seems everyone made the same mistake in E

→ Reply

18o3

3 weeks ago, # ^ |

What mistake?

→ Reply

samyasar2002

3 weeks ago, # |

Can the 3rd test case of problem B Increase/Decrease/Copy be done in 7 operations?

→ Reply

pokeland157

3 weeks ago, # ^ |

how

→ Reply

andrej246

3 weeks ago, # |

Great problem D, the solution is quite simple but still not completely trivial. E is also nice, sad I couldn't implement it in time...

→ Reply

3 weeks ago, # |

+153

I don't want problems like today's C to get normalized

→ Reply

div3_enjoyer

3 weeks ago, # ^ |

+17

i don't want comments like this get normalized

→ Reply

3 weeks ago, # ^ |

nowadays not many people have sense of humour :(

→ Reply

andrewtt

3 weeks ago, # ^ |

+18

Why? I enjoyed it.

→ Reply

-proof-by-ac-

3 weeks ago, # ^ |

← Rev. 2 →

good for you!

→ Reply

tickbird

3 weeks ago, # ^ |

Why? Because it forces you to think in a different way?

→ Reply

https://codeforces.com/contest/1976/submission/263362135

3 weeks ago, # ^ |

+28

it forces you to "if else if else if else if else if else if else..."

→ Reply

linkret

3 weeks ago, # ^ |

I don't have many if statements

→ Reply

Aspergillus

3 weeks ago, # ^ |

← Rev. 2 →

+13

Well there is an implementation which doesnt have such complications. One thing to notice is that there are only two types of distribution of workers. n + 1 programmers and m testers and n programmers m + 1 testers. For each i, if a[i] > b[i] remove it from the net sum of the n + 1 configuration, otherwise remove it from the net sum of the m + 1 configuration.

→ Reply

kalDima

3 weeks ago, # ^ |

You are damn right

→ Reply

rafael2005

3 weeks ago, # |

C — any idea why I get WA for this?

→ Reply

tb_ro

3 weeks ago, # ^ |

← Rev. 3 →

For example:

2 2

1 2 3 4 2

3 4 5 6 1

Your code outputs 14 13 13 12 14

For the second person, the answer should be: 3+5+4+2=14 (he would've been a tester, so the third guy becomes a tester instead of him, and the last guy becomes a programmer).

→ Reply

andrewtt

3 weeks ago, # |

← Rev. 3 →

Came up with the following solution during contest for F but didn't implement it in time:

https://codeforces.com/contest/1976/submission/263362159

TLDR, always remove the two deepest branches, and make them into a cycle. How to prove that:

a) this is optimal

b) this runs fast enough

Edit: fixed spacing of comment

Edit 2: solution was hacked

→ Reply

deadnecro18

3 weeks ago, # |

Can anyone provide a testcase where this submission fails. 263337520

→ Reply

lotusblume

3 weeks ago, # ^ |

Spoiler

Correct answer: 3 Your answer: 4

→ Reply

deadnecro18

3 weeks ago, # ^ |

Thanks

→ Reply

Caraxes.

3 weeks ago, # |

baler contest !!!

→ Reply

BlAcKBeArD2

3 weeks ago, # |

-11

Today educational codeforces round is the best contest ever seen.

→ Reply

3 weeks ago, # |

Any hint for 'C'?

→ Reply

3 weeks ago, # ^ |

← Rev. 2 →

Remove last one and choose everyone to progers or testers by naive. What will happen if you remove $$$i$$$-th person? $$$(1 \le i \textbf{<} n+m+1)$$$?

→ Reply

3 weeks ago, # |

D was nice, C was too much case work (for me) but anyways nice problem
can we do better than n * log(n) * log(n) in D.

→ Reply

3 weeks ago, # ^ |

yes, my submission is n log n

→ Reply

3 weeks ago, # ^ |

You can do binary search + sparse table or segment tree to solve in $$$O(n \log{n})$$$

→ Reply

3 weeks ago, # ^ |

i use bs over range maximum using segment tree it's
it's $$$ n\ log^2(n) $$$ can you please tell me how to reduce it to $$$n \ log(n)$$$

→ Reply

3 weeks ago, # ^ |

You are using segment tree to find maximum in $$$O(\log{n})$$$, but you can use data structure sparse table to find maximum on segment in $$$O(1)$$$.

→ Reply

3 weeks ago, # ^ |

Thanks!

→ Reply

3 weeks ago, # ^ |

In general, you don't really need to do binary search separately on the segment tree. CP Algorithm's blog on SegmentTrees is pretty good; I'd suggest going over the blog as a whole, but even the following section should give you an idea: Typical UseCase — $$$O(log^2(n)$$$ -> $$$O(log(n))$$$

→ Reply

3 weeks ago, # ^ |

Thanks! i learnt a new technique.

→ Reply

3 weeks ago, # ^ |

← Rev. 2 →

We don't really need dedicated RMQ data structures such as SparseTable/SegmentTree. Set/Map worked for me.
Reference Submission (C++ : Jiangly)
Reference Submission (Java : Me)
Complexity remains the same though, i.e., $$$O(n*log(n))$$$

*Edit: Added C++ reference submission (Jiangly's)

→ Reply

Soultaker

3 weeks ago, # ^ |

+71

D can be solved in O(n): 263368704

→ Reply

3 weeks ago, # ^ |

Thanks! interesting soln.

→ Reply

camc

3 weeks ago, # ^ |

Dang that's actually so clean

→ Reply

im_vengeance011

3 weeks ago, # ^ |

max(a[i..j]) ≤ 2×a[i] can u please explain this

→ Reply

vstiff

3 weeks ago, # ^ |

After inversion all +1 will become -1 and after subtraction will become < 0, invalid brackets

→ Reply

im_vengeance011

3 weeks ago, # ^ |

got it

→ Reply

3 weeks ago, # ^ |

Cool simplification!

→ Reply

DuongForeverAlone

3 weeks ago, # |

Got accepted C and D after upsolving. Feeling pretty bad today for corner case (or maybe some stupid handling in my implementation) :(( .

→ Reply

AdityaTakkar

3 weeks ago, # ^ |

I too was not able to find why I got WA for 30 minutes. I am Too slow at implementation and debugging.

→ Reply

3 weeks ago, # ^ |

Hello Master DuongForeverAlone! hru? do u remember me?

→ Reply

2 weeks ago, # ^ |

Yes Master DuongForeverAlone! You had a bad day, but you made a comeback just another day, and also today you did really well. Congrats! and yes i'll be focussing on >=1600 it just took a lot of work to figure out 1600 level problems (as of now) so i can't do more than 2, i have university exams for the whole month as well. Can you give me a tip on something? that how much time should i spend on problems >=1600 on my own without seeing the editorials? Thanx in advance

→ Reply

DuongForeverAlone

2 weeks ago, # ^ |

Try to direct message me instead of comment, as this is a personal problem.

→ Reply

2 weeks ago, # ^ |

I cant see you last reply LOL so i just replied myself XD

→ Reply

Arthas

3 weeks ago, # |

The A was really bad

→ Reply

AdityaTakkar

3 weeks ago, # ^ |

← Rev. 2 →

I too thought the same. But the shortest way to solve the problem A is to just check whether given is sorted or not. it is so elegant.

→ Reply

Arthas

3 weeks ago, # ^ |

Oh wow, didn't notice that. But still, i'm pretty sure that most participants brute forced the solution which was really annoying to code.

→ Reply

tb_ro

3 weeks ago, # |

First time I solve C in a Div. 2 contest! A and B were pretty easy and C was such a nice problem, I took a bit too much time for it but I liked it.

→ Reply

zhaoyang666

3 weeks ago, # |

how to solver B

→ Reply

3 weeks ago, # ^ |

consider each element as potential candidate which can be use to perform 3'rd operation
if you choose a_i for 3'rd operation
think about how you can minimize cost for i'th element because for all other j (j != i) cost is fixed that is abs(a_i — b_i)

→ Reply

mash97

3 weeks ago, # ^ |

Hi! Do you have any idea whey (possibly zero)?

_ the minimum number of operations (possibly zero)_

→ Reply

3 weeks ago, # ^ |

no. of ops will always be > 0

→ Reply

Swayam78

3 weeks ago, # ^ |

Dp, If don't understand then ask.

→ Reply

eklavya_k

3 weeks ago, # |

problem D the time limit is very strict. O (n * logn * logn) solution using Recursive segment tree gives TL, although I know nlogn solution exists.

→ Reply

lv.zheng

3 weeks ago, # ^ |

I use sparse table + binary search to find "the index of the first item after pos that is greater than x"

263354202

→ Reply

codack_mayank

3 weeks ago, # ^ |

I used map<int,vector>

→ Reply

synthborne

3 weeks ago, # ^ |

My solution is the same and runs in O(n * logn * logn). But I just copied segtree's code from GFG and it runs in less than 1000ms.

→ Reply

cwz2024

3 weeks ago, # |

It seems that my purple name want to stay with me for a longer time :)

Somehow I come up with an solution to D using segtree, and it worked! :)

→ Reply

ONEHUNDREDPUSHUPS

3 weeks ago, # |

compare my first submission in the contest and after contest in the D and cry with me T^T

→ Reply

AdityaTakkar

3 weeks ago, # |

How to solve Problem C using Binary Search? I solved without using it.

→ Reply

https://codeforces.com/contest/1976/hacks/1028125

3 weeks ago, # ^ |

263329045

→ Reply

aryan1313131

3 weeks ago, # |

+21

Is this hack not weird? Why would they randomly hardcode wrong answers. Seems like a trick by the hacker to gain points by hacking solutions like this.

→ Reply

Lakshay_2021059

3 weeks ago, # ^ |

damn

→ Reply

atd

3 weeks ago, # |

← Rev. 2 →

+15

I couldn't submit B for a long time cause cf wanted to verify if I am a human.

→ Reply

AHMADUL

3 weeks ago, # |

'C' was really mysterious!!!

→ Reply

DonSilvio

3 weeks ago, # |

← Rev. 3 →

God, I read B incorrectly and was thinking that the third option was to copy the number to the initially empty array b...

Spent 30 extra minutes do to that =(

→ Reply

jmyszka

3 weeks ago, # |

+12

Another amazing performance for JinnyW For what i know he is only 8 years old Could he be the next big chinese competetitor?

→ Reply

daveshub

3 weeks ago, # ^ |

Where did you get such information? I still find it hard to comprehend an 8yr old CM :(.

→ Reply

namanbhardwaj1454

3 weeks ago, # |

Could someone please help me by finding a test case where I am wrong for today's C https://codeforces.com/contest/1976/submission/263348497

→ Reply

rakhimova

3 weeks ago, # ^ |

input:

1
16 16
41 30 6 18 12 7 38 7 28 27 16 41 31 15 1 34 46 11 5 41 47 16 11 16 14 11 29 14 27 37 25 14 8 
32 6 40 47 33 30 11 41 1 20 1 1 1 29 9 13 45 43 46 19 20 20 43 12 36 20 40 5 30 49 34 17 37

correct output:

1012 1023 1022 1015 1029 1032 1015 1021 1025 1026 1037 1012 1022 1033 1053 1019 1007 1019 1016 1012 1006 1042 1019 1037 1026 1042 1022 1039 1032 1013 1028 1039 1045

→ Reply

namanbhardwaj1454

3 weeks ago, # ^ |

Thanks. Could you also tell what strategy did you use to find this test? I tried to debug it for an hour but was unable to find a counter case.

→ Reply

rakhimova

3 weeks ago, # ^ |

i failed test 2 in the contest, so i wrote a test generator and brute force code to check my solution for task C, and it got accepted. here is my code

test generator

void solution()
{
    srand(time(0));
    int t;
    t=100;
    cout << t << '\n';
    while(t--){
        int n=rand()%20;
        int m=rand()%20;
        cout << n << ' ' << m << '\n';
        vector<int> a(n+m+1), b(n+m+1);
        for(int i=0; i<n+m+1; i++){
            a[i]=rand()%50+1;
        }
        for(int i=0; i<n+m+1; i++){
            b[i]=rand()%50+1;
        }
        for(int i=0; i<n+m+1; i++){
            if(a[i]==b[i]) a[i]++;
        }
        for(auto x: a) cout << x << ' ';
        cout << '\n';
        for(auto x: b) cout << x << ' ';
        cout << '\n';
    }
        
}

→ Reply

rakhimova

3 weeks ago, # ^ |

i used the same strategy to find a counter case for your code

→ Reply

namanbhardwaj1454

3 weeks ago, # ^ |

Thanks

→ Reply

ritwij_kr

3 weeks ago, # ^ |

Try to write cleaner code! it helps while debugging your solution.

→ Reply

Devvikram34

3 weeks ago, # |

-14

C is really a bad problem. Just lengthy implementation. I just got scared and could not implemenet it properly

→ Reply

al-ghoul

3 weeks ago, # ^ |

-6

How is a problem bad just because it is lengthy? Most real-life problems are way longer than this tbh I enjoyed C it had so many factors to consider before arriving at the solution instead of one single crazy trick ¯_(ツ)_/¯

→ Reply

CaveNightingale

3 weeks ago, # ^ |

+11

A lengthy problem in 2-hour contest is a bad problem.If it's in a 5-hour or 14-day contest, it's not really bad.

→ Reply

al-ghoul

3 weeks ago, # ^ |

Personally I don't think it was that bad, it took me almost all the time to solve it but that's coz I'm still a noob, I can see a pretty significant amount solved C in sub 40 mins

→ Reply

ScarletS

3 weeks ago, # ^ |

+10

I didn't find the implementation that lengthy, 263365416

→ Reply

shivamxd

3 weeks ago, # |

+14

The solution to problem D involves identifying a pair (i, j) that satisfies the following conditions: A[i-1] == A[j], A[j] != 0, and for every k in the range i <= k <= j, A[k] <= 2A[j]. Here, the array A is a prefix sum array derived by considering '(' as +1 and ')' as -1. To illustrate, consider the sequence "((((()))))".

Interestingly, while many have approached this problem with a time complexity ofO(n * log(n) * log(n)), there exists a more efficient solution. This problem can actually be solved inO(n) time 263375129

→ Reply

santi3223

3 weeks ago, # |

Any idea how could I improve my code for C, giving TLE in test 4

https://codeforces.com/contest/1976/submission/263348500

→ Reply

3 weeks ago, # ^ |

Assume all the candidates come to interview. Solve the problem twice, once for N+1 coders and M testers, and once for N coders and M+1 testers. In both solutions track whether each candidate is appointed as a coder or as a tester. This takes O(N+M+1) steps.

If the candidate i does not come to interview, then check whether i is appointed a coder or tester in the two solutions. If a coder in the first solution, then answer is (first solution score — candidate i score as a coder). If a tester in the second solution, then answer is (second solution score — candidate i score as a tester).

You will never have candidate i appointed as tester in first solution and as coder in second solution.

→ Reply

santi3223

3 weeks ago, # ^ |

Oooh right, thanks for pointing that out!

→ Reply

Priyanshu_1510

3 weeks ago, # |

Can anyone tell why this submission fails for C? https://codeforces.com/contest/1976/submission/263357375

→ Reply

this is recursive function

3 weeks ago, # ^ |

line 124: cout<<ans1-t[i]; There is no space before the next output.

→ Reply

Priyanshu_1510

3 weeks ago, # ^ |

Dammit!That was the only mistake.Thanks for pointing out.

→ Reply

marshtomp

3 weeks ago, # |

← Rev. 2 →

I would really appreciate it if anyone can point out why my submission for C is wrong: https://codeforces.com/contest/1976/submission/263355148

→ Reply

marshtomp

3 weeks ago, # ^ |

Nevermind, resolved.

→ Reply

Focus07

3 weeks ago, # |

whats wrong in my first solution to B ?

→ Reply

matislu

3 weeks ago, # ^ |

You need to check if $$$b[n]$$$ is between $$$min(a[i], b[i])$$$ and $$$max(a[i], b[i])$$$ for any $$$i$$$ in loop instead of just at the end using bottom and top variables. If this condition holds, just add 1, otherwise handle the case as you're doing it right now.

→ Reply

Kustizus168

3 weeks ago, # |

E is no easy, I can't AC T_T

→ Reply

CaveNightingale

3 weeks ago, # |

codeforces.com is down in some time interval during the contest, and around 15 minutes later the mirror.codeforces.com recovered but the root domain didn't and wasn't accessible even at the end of contest. I don't see why this round should be rated even the terrible server issue occurs. By the way, C is really a bad problem.

→ Reply

cleanser

3 weeks ago, # ^ |

The mirror was fine the whole time for me.

→ Reply

MrPython

3 weeks ago, # ^ |

← Rev. 2 →

I wasted about 30min because of 502 and cloudflare.

m1,m2 and m3 didn't work well, too.

→ Reply

CaveNightingale

3 weeks ago, # ^ |

It seems that m1, m2, m3 haven't been working well for a few months. I don't know why Mike didn't fix it.

→ Reply

Devvikram34

3 weeks ago, # ^ |

A lengthy problem in 2-hour contest is a bad problem.If it's in a 5-hour or 14-day contest, it's not really bad.

→ Reply

Eslam_Ahmed

3 weeks ago, # |

← Rev. 2 →

I solve problem C Using Recursive DP

DP[n][2]

this person take place as prog 0 else 1

and send remaining places of prog and test

two states only person prog or tester

i think it's most easy solution to this problem

→ Reply

3 weeks ago, # ^ |

can you provide an AC link ?

→ Reply

3 weeks ago, # ^ |

can you please explain it a little bit? like in my mind I need at lease 3 states index,n,m
which is 1e15 I looked at your code but I couldn't get it because I'm not used to java can you explain the logic ?

→ Reply

Eslam_Ahmed

3 weeks ago, # ^ |

← Rev. 3 →

if we solve it for first n people for example if we stand at index 7 and remaining programmers 4 and testers 3 if we remove index 3 this is programmer we go to index 7 with 3 prog and 3 testers yes? if we remove index 4 this is tester we go to index 7 with 4 prog and 2 testers yes?

if we remove index 5 this is programmer we go to index 7 with 3 prog and 3 testers yes?

which meaning we always go to any index with prog-1 or testers -1

so I don't care about n and m in first case I don't remove any one

→ Reply

2 weeks ago, # ^ |

← Rev. 2 →

thanks I think I got it dp[i][s] means that we are here at index I and we are missing person of type s right ? I will try to implement it to make sure that I got it

→ Reply

kinitic013

3 weeks ago, # ^ |

i also kinda solved it with DP(Non Recursive)

263356128

→ Reply

pian_zhu

3 weeks ago, # |

Please take care of chinese,We can't even get into codeforce.com

→ Reply

Kevin_juruo_awa

3 weeks ago, # ^ |

can try m1.codeforces.com?

→ Reply

MrPython

3 weeks ago, # ^ |

didn't work well.

→ Reply

pian_zhu

3 weeks ago, # ^ |

m1.codeforce.com is not work well,and a great number of times it can't load problems

→ Reply

Kevin_juruo_awa

3 weeks ago, # ^ |

exactly it is the case. or try use some vpns or build it via employ a server located not in china(shadowsocks). or you can ask the content of the problem to friends(in this contest only C is not loaded with m1.)

→ Reply

3 weeks ago, # |

can someone give a hint on problem c first I sorted, but how to handle the case when you have to choose whether this person should be coder or debugger ?

→ Reply

3 weeks ago, # ^ |

never mind I thought we need to maximize our sum

→ Reply

chunzDing

3 weeks ago, # |

what is the idea for C?

→ Reply

smit_384

3 weeks ago, # ^ |

Hint : only 2 will change, first forced employee and last index one and calculate in reverse order

→ Reply

chunzDing

3 weeks ago, # ^ |

Thank you for the great idea. I get ac. 263424028

→ Reply

Pirated_Codes

3 weeks ago, # ^ |

calculate in reverse order means?

→ Reply

smit_384

3 weeks ago, # ^ |

← Rev. 2 →

mean first we will calculate n+m th doest come on interview then n+m-1,n+m-2....so on till 1,0th index dont come at work. or maybe forward can work but i have written in backwards manner

→ Reply

ayush_t007

3 weeks ago, # |

I have this test case for problem B 1 3 2 4 6 1 5 2 13

shouldn't the ans be 21 for this. ans=(2-1)+(5-4)+(13-6)+1+(13-2)=21. for making the copy of 13 we first have to go from 6 to 13 which is 13-6=7 operation and then after appending the copy(+1 operation) we have to come back to 2 (13-2=11 operations. And for the remaining numbers in a ans+=(2-1)+(5-4). what is the flaw in this logic ?

→ Reply

3 weeks ago, # ^ |

First operation is to copy the 6 to the end, giving 2 4 6 6. Then using +-1 operations convert to 1 5 2 13, taking (2-1) + (5-4) + (6-2) + (13-6) steps. Total 14.

→ Reply

nithinraj04

3 weeks ago, # ^ |

You have to append 6 to the back of a and then make it 13. So the answer will be ans = (2-1)+(5-4)+1+(6-2)+(13-6)=14

→ Reply

dzhi

3 weeks ago, # |

I am puzzled at the statement of problem F for an hour and couldn't explain the sample output, until I realized that lower vertex in condition below is by depth instead of vertex id! Somehow I couldn't realize it earlier despite noticed the input is a rooted tree.

for every bridge, all tree edges in the subtree of the lower vertex of that bridge should also be bridges;
the number of bridges is as small as possible.

→ Reply

working_cell

3 weeks ago, # ^ |

My friend had also misunderstood at this place before,though he solved the problem at last.When he was reading this part,he was confused why the problem repeats "root has only one son" again and again.So he asked questions and specifically said this to the organizers at question part.However,the response isn't satisfying and there are still a lot of people who neither realized the contradiction nor got the correct meaning.

→ Reply

3 weeks ago, # |

I thought that I have to maximize the sum in problem C I just noticed that I don't have to

→ Reply

srijannn17

3 weeks ago, # |

Results,when.. ??

→ Reply

Whitedevil08

3 weeks ago, # |

When will the ratings change?? I am checking my ratings from yesterday Night!!!

→ Reply

Harman001

3 weeks ago, # ^ |

It will take some time but soon will get updated.

→ Reply

Erinyes

3 weeks ago, # |

+18

The problems are quite suitable for Educational Round,I like this style.

→ Reply

arihant_j

3 weeks ago, # |

← Rev. 2 →

can someone tell where is my code failing for problem c,i calculated skill if candidate n=m+1 th didnt come and then using it found if candidate i th didnt come(i>=1 and i<=n+m) 263427040

→ Reply

moyegege

3 weeks ago, # |

want a tutorial for C PLZ!!!

→ Reply

granadierfc

3 weeks ago, # ^ |

Forget that you have to pick n and m guys. Imagine that you want to pick n + 1 programmers and m testers.You can do it simply by checking a[i] > b[i]. Let us say the sum of a[i] (for prorgrammers and respectively b[i] for testers) is S. Now for all guys selected as programmer , the answer , when they are excluded is simply S — a[i] , as you can discard i_th guy from the chosen set. Similarly do it other way i.e. solve the problem for n programmers and m + 1 testers.

→ Reply

moyegege

3 weeks ago, # ^ |

thanks!!!

→ Reply

Pirated_Codes

3 weeks ago, # ^ |

how will i get to know if the i_th person which is absent now was contributing as a programmer or tester?

→ Reply

granadierfc

3 weeks ago, # ^ |

You can maintain that using some array. What I did was whenever a particular i was a programmer , I did was ans[i] = -a[i]. After getting the final sum S , I had to check if ans[i] < 0 and then do ans[i] += S.

→ Reply

Pirated_Codes

3 weeks ago, # ^ |

← Rev. 3 →

but there will be 1 person that will contribute as both programmer and tester when we will take (n+1 programmer and m tester) and (n programmer and m+1 tester) right?

→ Reply

granadierfc

3 weeks ago, # ^ |

Yes , you are correct , and both gives same answer , so there is no issue.

→ Reply

Mah.D

3 weeks ago, # |

Div-1 participants(rating > 2100) are rated for this round?

→ Reply

Erinyes

3 weeks ago, # ^ |

no. This round will be rated for the participants with rating lower than 2100.

→ Reply

clubpenguinfan

3 weeks ago, # ^ |

Why are people above 2,100 given a rank in the common standings?

→ Reply

Mah.D

3 weeks ago, # ^ |

but rating more than 2100 are showing in official standing :)

→ Reply

djm03178

3 weeks ago, # ^ |

← Rev. 3 →

Educational rounds has always been 'official' for all participants. However, 'official' != 'rated'. It is 'rated' only for participants with rating lower than 2100.

→ Reply

Mah.D

3 weeks ago, # ^ |

oh, thanks

→ Reply

Ashvil

3 weeks ago, # |

I am new here. My rating is 1210 will this contest be considered rated for me or unrated.

→ Reply

StephaneZ

3 weeks ago, # ^ |

You will be rated, if you made at least one submission during the contest.

→ Reply

bugmaker3243

3 weeks ago, # |

Everytime there is a contest, the codeforces.com always asks me to prove I'm a real person. why?

→ Reply

Euphoria_07

3 weeks ago, # ^ |

This actually happen when there is lots of traffic at the codeforces. Just to avoid the denial of service attack during the contest this is done by the cloud-flare.

→ Reply

AHMADUL

3 weeks ago, # |

Will we get the rating updation before 949 Div-2 starts?

→ Reply

Giga_Cronos

3 weeks ago, # ^ |

This is a nice question, if you became master in the EDU, I believe both contest will be rated for you.

→ Reply

Ronak1808

3 weeks ago, # |

Can anyone look at my C and help me in figure out what I'm missing? 263424813

→ Reply

0sigma101

3 weeks ago, # |

Is this wierd if my all submissions got removed and my rating did not. It shows i did not attempt :/

→ Reply

GermanGuy

3 weeks ago, # |

when will the ratings be updated?

→ Reply

divyanshji

3 weeks ago, # |

what is system testing? and why a 2 hour-long contest is taking more than 12 hours to conclude. I am new to cf.

→ Reply

StephaneZ

3 weeks ago, # ^ |

“System testing” is a procedure that retests all the submitted code with successful hacks during the open-hacking phase, as well as extra tests (if available) provided by the contest managers. Edu rounds and Div.3 rounds may include a 12-hour open-hacking phase, during which everyone can try to hack every submitted code in the contest.

→ Reply

divyanshji

3 weeks ago, # ^ |

Okay. Thanks stephanez.

→ Reply

Coding103856

3 weeks ago, # |

+20

when will the rating be updated ?

→ Reply

Rakshit_1

3 weeks ago, # |

Can someone explain why this code is getting accepted on C++17 but not on C++20..... 263515419

→ Reply

lv.zheng

3 weeks ago, # ^ |

← Rev. 2 →

I have helped debugged your code.

In this section:

    else{
        auto it1=it;
        it1--;
        sum++;
        sum+=min(abs(b[n]-*it),abs(b[n]-*it1));
    }

it1-- crashes. Looks like you are missing some boundary checks.

input:

1
1
1000000000
999999999 1

Debugging environment: MacOS ARM64 clang++ -Wall -std=c++20 -Wextra -Og -g3 with slightly modified include section of your code.

→ Reply

Rakshit_1

3 weeks ago, # ^ |

← Rev. 2 →

but how did it get accepted while submitting in c++17 it got WA on test 7 in c++20;

→ Reply