awoo's blog

By awoo, history, 4 weeks ago, translation, In English

Neapolis University Pafos

Hello Codeforces!

The series of Educational Rounds continues thanks to the support of the Neapolis University Pafos.

On May/30/2024 17:35 (Moscow time) Educational Codeforces Round 166 (Rated for Div. 2) will start.

This round will be rated for the participants with rating lower than 2100. It will be held on extended ICPC rules. The penalty for each incorrect submission until the submission with a full solution is 10 minutes. After the end of the contest, you will have 12 hours to hack any solution you want. You will have access to copy any solution and test it locally.

You will be given 6 or 7 problems and 2 hours to solve them.

The problems were invented and prepared by Adilbek adedalic Dalabaev, Ivan BledDest Androsov, Maksim Neon Mescheryakov, Roman Roms Glazov and me. Also, huge thanks to Mike MikeMirzayanov Mirzayanov for great systems Polygon and Codeforces.

Good luck to all the participants!

UPD: Editorial is out

  • Vote: I like it
  • +203
  • Vote: I do not like it

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

another BledDest round. Sheesh!!!

»
4 weeks ago, # |
Rev. 7   Vote: I like it 0 Vote: I do not like it

I got it.

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Orz

»
4 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

Let's run this shit down boys

»
4 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

mewing cat ready 4 the contest

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope the competition topic is more interesting!

»
4 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hope ABC!

»
4 weeks ago, # |
  Vote: I like it -12 Vote: I do not like it

Hmm Educational round "Mathforces" for a reason!

»
4 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Mathforces round are the best

»
4 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

hope ABC

»
3 weeks ago, # |
  Vote: I like it +11 Vote: I do not like it

let's hope for delta > 0

»
3 weeks ago, # |
  Vote: I like it +23 Vote: I do not like it

Best wishes for everyone's A, B, C and D.

»
3 weeks ago, # |
  Vote: I like it +16 Vote: I do not like it

need +1

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

Hope everything goes well !!

»
3 weeks ago, # |
  Vote: I like it +48 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    yes I am also the handful one

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

today first 10 min my codeforces didnt run well

»
3 weeks ago, # |
Rev. 2   Vote: I like it +35 Vote: I do not like it

Bad network

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

I opened a B! :)

»
3 weeks ago, # |
  Vote: I like it -31 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

what is the idea for D?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +12 Vote: I do not like it

    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$$$.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    1. Keep one counter. Initial value of the counter = 0;

    2. Travel the string from left to right. When you encounter '(' , counter++, else counter--, Store above values into some array.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +10 Vote: I do not like it

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

    1. $$$ 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.
    2. 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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Here is my solution.

    1. diff_cnt -- counter the different between the number of '(' and the number of ')'
    2. 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.
    3. 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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Excellent mental exercise... Loved the problems.

»
3 weeks ago, # |
  Vote: I like it +36 Vote: I do not like it

thank you for the contest. :)

I really enjoyed solving C today.

Said no one ever!

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        maybe a mistake

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

i solved D one minute after contest ended :(

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

»
3 weeks ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

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

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

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

»
3 weeks ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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.net/contest/1976/submission/263360996

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +1 Vote: I do not like it

    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.

»
3 weeks ago, # |
Rev. 9   Vote: I like it +4 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve C?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

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

    But of course there much more clever solutions

»
3 weeks ago, # |
  Vote: I like it +15 Vote: I do not like it

is carrot working for anyone?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

damn seems everyone made the same mistake in E

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +153 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +17 Vote: I do not like it

    i don't want comments like this get normalized

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +18 Vote: I do not like it

    Why? I enjoyed it.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +5 Vote: I do not like it

        I don't have many if statements

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it +13 Vote: I do not like it

        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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    You are damn right

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
  • »
    »
    3 weeks ago, # ^ |
    Rev. 3   Vote: I like it +1 Vote: I do not like it

    For example:

    1

    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).

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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

https://codeforces.net/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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone provide a testcase where this submission fails. 263337520

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

baler contest !!!

»
3 weeks ago, # |
  Vote: I like it -11 Vote: I do not like it

Today educational codeforces round is the best contest ever seen.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Any hint for 'C'?

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    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)$$$?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hello Master DuongForeverAlone! hru? do u remember me?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +2 Vote: I do not like it

The A was really bad

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it +2 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

how to solver B

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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)

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      _ the minimum number of operations (possibly zero)_

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Dp, If don't understand then ask.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    263354202

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

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! :)

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

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

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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

'C' was really mysterious!!!

»
3 weeks ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

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 =(

»
3 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    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
    
    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it -14 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    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 ¯_(ツ)_/¯

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +11 Vote: I do not like it

      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.

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

    I didn't find the implementation that lengthy, 263365416

»
3 weeks ago, # |
  Vote: I like it +14 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

whats wrong in my first solution to B ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

E is no easy, I can't AC T_T

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    The mirror was fine the whole time for me.

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    I wasted about 30min because of 502 and cloudflare.

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

this is recursive function

two states only person prog or tester

i think it's most easy solution to this problem

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you provide an AC link ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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 ?

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 3   Vote: I like it 0 Vote: I do not like it

      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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i also kinda solved it with DP(Non Recursive)

    263356128

»
3 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can try m1.codeforces.com?

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      didn't work well.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    never mind I thought we need to maximize our sum

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the idea for C?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      calculate in reverse order means?

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 ?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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.
  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

Results,when.. ??

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    It will take some time but soon will get updated.

»
3 weeks ago, # |
  Vote: I like it +18 Vote: I do not like it

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

»
3 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

want a tutorial for C PLZ!!!

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      thanks!!!

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          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?

          • »
            »
            »
            »
            »
            »
            3 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      • »
        »
        »
        »
        3 weeks ago, # ^ |
        Rev. 3   Vote: I like it +6 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

when will the ratings be updated?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    “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.

»
3 weeks ago, # |
  Vote: I like it +20 Vote: I do not like it

when will the rating be updated ?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    • »
      »
      »
      3 weeks ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    If it==s.begin(), then when you do auto it1(it); it1--; you are stepping off the start of the set s, and anything can happen.

    If *it1 happens to give the same value as *s.begin(), or some unpredictable number greater than *s.begin(), then you get the right answer.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Was it rated or unrated?

»
3 weeks ago, # |
  Vote: I like it +6 Vote: I do not like it

system testing got tle

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

awoo can you write a tutorial

»
3 weeks ago, # |
  Vote: I like it +8 Vote: I do not like it

why the rating updation is getting this much delayed unusually??

»
3 weeks ago, # |
  Vote: I like it +9 Vote: I do not like it

awoo , BledDest , MikeMirzayanov

Even hours after final standings, neither of today,yesterday's contest rating changes are published yet ?

is there any reason or just ratings TLE....

»
3 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

How much time will it take to display rating??? i cant see myself in 700s anymore. This is torture to a newbie.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Will the rating even be updated or not?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

had my refresh button right now, been the submit button in contest yesterday

PUPIL confirmed :)

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Great contest! Does the rating update usually take this long, lol?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    They say sometimes it does. I've only been on a handful of rounds so far, but one took 12+ hours to update. There was no open hacking that round, so add that time to this round. And dunno about R949. Hope to see the updates by tomorrow morning.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When rating will be updated?

»
3 weeks ago, # |
  Vote: I like it +5 Vote: I do not like it

Why I'm still unrated?

»
3 weeks ago, # |
  Vote: I like it +21 Vote: I do not like it

Why i am still blue even my max rating has been changed to candidate master?

  • »
    »
    3 weeks ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    It seems that all the people participating in this round but not the next round and getting level upgrade have encountered this problem.

    • »
      »
      »
      3 weeks ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      can't even understand how this could happen...

      • »
        »
        »
        »
        3 weeks ago, # ^ |
          Vote: I like it +16 Vote: I do not like it

        It's quite fun seeing I am blue with the rating of 2007 :)

        but I believe it will update soon.

        • »
          »
          »
          »
          »
          3 weeks ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          I think they don't know about this bug As this bus is in that div only The least round has no bug

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You have the best programmers in the world but takes you 2 days to update the rating of 2*10^4 users

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Something went wrong with the new rank

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

give me my rating pls dawg

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Rating not updated I have not gotten plag either

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why am I still Newbie with a rating of 1200+ :(

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the rating change?

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Gave the contest even had 1 correct submission but still not showing any change in rating and not being shown in my given contests section as well

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Why isn't the rating updated yet??It has been so long...

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Just got this e-mail that plague has been detected in my code and I am genuinely so confused. My solution for D problem is only slightly similar to one random guy's solution!? This contest was a huge rating boost for me. Please review this 263359271 This is my submission and the following is the other guy's submission: 263354669 MikeMirzayanov

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hey Mike Mirzayanov , I got a plagiarism check notification for this contest with another random guy . Here's my logic:- For each test case, it calculates two sums, edison and ethan. For edison, it iterates through the arrays, selecting the larger values from a or b based on limits n and m, and records these choices. Then, it recalculates for ethan using a similar method but with a different selection order. Finally, it computes and prints values reflecting the contributions to the sums from the chosen elements. The process ensures that the sums are maximized according to the constraints. I am sure that this check is purely coincidental and I don't even know the guy who. I got the check with...the points were extremely important for me so please remove the check if possible

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I tried running my code on ideone in default settings and i was not aware about that. It won't be repeated next time.

»
3 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello Mike Mirzayanov, I have got a plagiarism check for problem C in this contest.

The provided solution of mine aims to maximize two different sums by selecting elements under constraints. For each test case, the solution initializes the arrays and two sums, hiper_ed and hiper_et. It then employs two selection strategies: the first strategy prioritizes elements from the first array if they are greater and within a limit n, and otherwise selects from the second array if within limit m. The second strategy inverts this logic, prioritizing elements from the second array if they are greater and within m. Both strategies ensure that the constraints on the number of selections are met. Finally, the solution calculates and outputs a value for each index based on the differences in sums, reflecting the contribution of each element to the overall sum. This approach uses standard problem-solving techniques for array manipulation and constrained selections, making any resemblance to other solutions a coincidence.

The provided solution is an original work derived from applying well-known techniques to solve the given problem effectively. Any similarities with other solutions are due to the nature of the problem and the methods used to solve it, which are widely accepted and practiced in the programming community.

The approach used in this solution is a common strategy for problems involving array comparisons and constrained selections. The specific logic of iterating through arrays, comparing elements, and maintaining counters is a typical method used by many programmers to tackle such problems. Any resemblance to other solutions is purely coincidental and a result of applying standard problem-solving techniques.

This plagiarism will affect adversely to my graph in this placement season. Can you please look at this. Thank you for consideration

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Students are welcome