Codeforces Round #817 (Div. 4) Editorial

Thanks for participating!

1722A - Spell Check

Idea: mesanu, MikeMirzayanov

1722B - Colourblindness

Idea: flamestorm

1722C - Word Game

Idea: flamestorm

1722D - Line

Idea: flamestorm

1722E - Counting Rectangles

Idea: mesanu

1722F - L-shapes

Idea: MikeMirzayanov

1722G - Even-Odd XOR

Idea: mesanu

• • 20 hours ago, # ^ | It should be Timru

  • 19 hours ago, # ^ | ← Rev. 2 →   +21 i... totally knew that, good reading comprehension, well done, you passed the test

    • 11 hours ago, # ^ | there should be "Timru" instead of "Timur" in the editorial solution

      • 7 hours ago, # ^ | it is sorted afterwards , so eventually it is Timru only

        • 112 minutes ago, # ^ | Timru

• 20 hours ago, # ^ | exactly

• 19 hours ago, # ^ | Can you give your solution here it would help

  • 19 hours ago, # ^ | here if you need explanation feel free to ask

    • 18 hours ago, # ^ | Hello, I saw your solution but I didn't understand this line . What is it for > for (k;k<=n;k++) ans[k]=s;

      • 12 hours ago, # ^ | let's suppose that it was already optimal like RRLL so in the line you mentioned it just sets the remaining indexes (which could not be covered in while loop cuz of being optimal) they will just get the previous value as we will not be changing them...

        • 6 hours ago, # ^ | Thank you.

      • 10 hours ago, # ^ | Let's say the number of characters I needes to change was 8 and n is 10. I need go give an answer for all k such that 1<=k<=n so I just output for the remaining k

        • 6 hours ago, # ^ | I got it. Thank you so much.

          • 6 hours ago, # ^ | You're welcome

      • 10 hours ago, # ^ | ← Rev. 2 →   0 Check out my submission for problem D it might help you understand you the two pointer approach bettetb

• 19 hours ago, # ^ | I solved it in O(n) aswell, but using prefix array 170271299

• 13 hours ago, # ^ | Yes, I solved it in the same way. here

• 7 hours ago, # ^ | What is two pointer approach... Can you share some resources from where I should learn... It would be a great help

  • 6 hours ago, # ^ | Check Codeforces edu section. You can also read about it on USACO Guide

  • 3 hours ago, # ^ | ← Rev. 2 →   0 Two pointer is basically using two indices to traverse through an array on the basis of some condition that you can apply on both the pointers(pointing to a particular index), like in the D part of the question we take one pointer at very start and one pointer at very end of the array and then we can check if we got a left viewer with first pointer then changing it to R will give a better score till n/2-1 and checking the same thing for the right pointer for the right side viewer till n-n/2, we can do this till left pointer is less than right pointer. To understand two pointers you should try solving problems for it instead reading about it, this link will work for basic problems Two pointers and problems on it

• 6 hours ago, # ^ | i do it with queue :)

  • 6 hours ago, # ^ | It can be done too, because there indices that must be changed before others right?

• 19 hours ago, # ^ | ← Rev. 3 →   0 I think that's true. Change it, flamestorm.

  • 15 hours ago, # ^ | You check if "T" is in the string, that can be done in O(1)O(1) (since it only has 5 elements). Then you check if "i", also O(1)O(1) And so forth. In total 5⋅O(1)=O(1)5⋅O(1)=O(1)

• 14 hours ago, # ^ | master piece. i tried to construct a solution similar to topic 3, but unfortunately fell into tons of case work. however, instead we can take advantage of samples, XD

• 9 hours ago, # ^ | ← Rev. 2 →   0 thanks a lot!!

• 3 hours ago, # ^ | Thanks alot. Can you share the proof of topic 3 ?

  • 3 hours ago, # ^ | proof with an example

    • 2 hours ago, # ^ | That's great! Thanks alot.

• 18 hours ago, # ^ | should give a TLE or difficult to pass since for every query you will traverse all 1000 (x) and BS for (y) which will give "1e5 * 1000* log(1000)"

• 16 hours ago, # ^ | I did it this way because I didn't know about 2d sum prefixes. You need to keep a sorted 2d array, and then another 2d array of sum prefixes for 1..1000. Then you do two binary searches on the ranges to get your start and end. It was slow but I passed using Go at 3500ms.

  • 10 hours ago, # ^ | May be that will fail system testing.

    • 5 hours ago, # ^ | It did TLE. I also solved with same approach and it TLEd.

    • 62 minutes ago, # ^ | Yup you were right.

      • 30 minutes ago, # ^ | Mine Problem C was also hacked due to TLE I used a very dumb method to solve that initially.

• 2 hours ago, # ^ | I got TLEd for that

• 16 hours ago, # ^ | Your solution is weaker

  • 12 hours ago, # ^ | Agreed and that's a pity that such a solution passed.

• 17 hours ago, # ^ | underStood

• 10 hours ago, # ^ | That’s what I did lmao

• 11 hours ago, # ^ | Can you please tell me where my submission 170342106 for problem E is failing?

  • 11 hours ago, # ^ | I think your code is quite overcomplicated

• 9 hours ago, # ^ | tgp07 Excellent editorial, better than official one! Could you please tell me if there is a way to solve E under the same time constraints for tighter dimensions of the rectangle say 1e5 or 1e9 or even higher?

  • a moment ago, # ^ | That would be a lot tougher. I'm not immediately sure of any way to solve that.

• 8 hours ago, # ^ | your G one is really good Thanks for sharing.

• 6 hours ago, # ^ | Take a look at Ticket 16132 from CF Stress for a counter example.

• 6 hours ago, # ^ | Take a look at Ticket 16131 from CF Stress for a counter example.

• 10 hours ago, # ^ | Some of the corner test cases are not added while you submit the solution. And if you have not handled those cases and someone else break your code for any of those test cases means your solution is hacked .

• 9 hours ago, # ^ | For div2, preliminary ratings are updated in 2-3 hours. For education rounds/Div 3/Div 4, we have an open hacking phase which lasts for 12 hours so yeah, expect waiting for atleast 18 hours.

  • 8 hours ago, # ^ | bro I am new here.Can you tell me what is this open hacking phase?

    • 8 hours ago, # ^ | In div3/4 and Educational round, we have an open hacking phase for 12 hours. This means you can view others' code and find a test case where their code fails. If you hack their solution, the system will use this test case provided by you after these 12 hours during the system test (after which we get our final result, I hope you know the difference between system test and pretests). Hacking others won't give you extra points in the Edu round or Div 3/4. The only purpose of Open hacking phase is to promote hacking others' solutions and to understand others' writing styles. Hacking others will give you extra points in Div 2/1. To know more in detail, please use the codeforces search box. Searching is a good habit when on the path to becoming a competitive programmer. All the best!

      • 8 hours ago, # ^ | @nikhilofindia thanks bro

  • 8 hours ago, # ^ | usually div. 3 gets preliminary rating updates by now right?

    • 8 hours ago, # ^ | ← Rev. 3 →   0 Max to Max 5PM IST (from what I have experienced) This is worst case. Edit: Looks like we have a new worst

• 9 hours ago, # ^ | Check out my solution maybe it’ll help you

  • 7 hours ago, # ^ | Thank you, nice code

• 9 hours ago, # ^ | ← Rev. 2 →   0 1 3 3 .*. *.* .*.

  • 7 hours ago, # ^ | Thanks a lot, how do you come up with such cases, like how do you think of cases where our code might fail, how to develop that? any tips on that would be very helpful.

• 7 hours ago, # ^ | Can anyone please help me??

t = int(input())
for _ in range(t):
    tot_words = int(input()) * 3
    s1 = set(x for x in input().split())
    s2 = set(x for x in input().split())
    s3 = set(x for x in input().split())

    only_in_s1 = len(s1 - s2 - s3)
    only_in_s2 = len(s2 - s1 - s3)
    only_in_s3 = len(s3 - s1 - s2)

    in_s1_s2_s3 = s1 & s2 & s3
    s1_s2 = len((s1 & s2) - in_s1_s2_s3)
    s2_s3 = len((s2 & s3) - in_s1_s2_s3)
    s3_s1 = len((s3 & s1) - in_s1_s2_s3)

    score_of_s1 = (only_in_s1 * 3) + (s1_s2 + s3_s1)
    score_of_s2 = (only_in_s2 * 3) + (s2_s3 + s1_s2)
    score_of_s3 = (only_in_s3 * 3) + (s3_s1 + s2_s3)
    print(score_of_s1, score_of_s2, score_of_s3)

• 8 hours ago, # ^ | Funnily I completed sets chapter only yesterday.

• 5 hours ago, # ^ | Its a comparator which defines how you want it be sorted. You can read more about it here

• 5 hours ago, # ^ | I solved in the same way

• 64 minutes ago, # ^ | suppose you have a data structure which stores 2D-prefix sums, such that sum of rectangles with height <= H and width <= W = pref[H][W] then if you wanna know the sum of areas of rectangles with height < Hb and width < Wb (condition — i) then that would equate to pref[Hb — 1][Wb — 1] now say you want the sum of areas of rectangles which have height <= Hs and width <= Ws(condition-ii) the rectangles which satisfy both condition i and ii is the required answer for learning about 2D-prefix sums I would suggest going through the USACO guide, they have detailed and easy to understand content, https://usaco.guide/silver/more-prefix-sums?lang=cpp#2d-prefix-sums