flamestorm's blog

Codeforces Round #784 (Div. 4) Editorial
By flamestorm, 2 months ago, In English

Thanks for participating!

1669A - Division?

Idea: SlavicG

Tutorial
Solution

1669B - Triple

Idea: Errichto

Tutorial
Solution

1669C - Odd/Even Increments

Idea: mesanu

Tutorial
Solution

1669D - Colorful Stamp

Idea: flamestorm

Tutorial
Solution

1669E - 2-Letter Strings

Idea: SlavicG

Tutorial
Solution

1669F - Eating Candies

Idea: MikeMirzayanov

Tutorial
Solution

1669G - Fall Down

Idea: MikeMirzayanov

Tutorial
Solution

1669H - Maximal AND

Idea: SlavicG

Tutorial
Solution
 
 
 
 
  • Vote: I like it
  • +67
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it +39 Vote: I do not like it

flamestorm orz

→ Reply
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Thanks for the round, I loved it!

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

props on hosting a div 4 round

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was too slow to finish H

→ Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the awesome round and light fast editorial!

→ Reply
»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

My first full solved round! Let's goooo!

→ Reply
»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Looking forward to more div.4 rounds, so I can have flawless solves like this <3.

→ Reply
»
2 months ago, # |
  Vote: I like it +14 Vote: I do not like it

Also, there are video solutions here for people who prefer those.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I was too slow. Feels so bad knowing I could've done tons better if only I was faster. :( I'll try harder next time. Thanks for the contest guys!

→ Reply
»
2 months ago, # |
  Vote: I like it +31 Vote: I do not like it

This may come off as an unpopular opinion but I feel the round should have at least consisted of 1 ~ 2 1600 rated greedy or ad-hoc style problems.

Lately, most CF div 2 rounds had very annoying C or B problems and it would have been nice to have a problem of those nature in this round. (Today's D was the closest to what I am trying to say)

The div 3 rounds's most difficult problems are at least of 1900 rating (non inflated) even though it is meant to be for < 1600 rated people.

I think it is as fair to have at least 1 ~ 2 1600 problems in div 4 rounds too following the div 3 standards.

Just some suggestions from my end.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, can someone point out why i am getting wrong answer here for Question F. If i am running that test case on my system then i am getting the correct output but here it shows a different output. Can someone point it out why. Thanks in advance.

Code : https://codeforces.com/contest/1669/submission/154423744

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think you miss the case where the amount of candies the two eat overlapped

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No NO, actually for this test case

      6 1127 5715 4917 682 1721 4439

      Judge is telling my output is 6, but on my system its coming 5 which is the correct answer

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        You do not initialize variable temp, so its value is unpredictable:

        ...
        for(auto x : al){
            ll temp;
            if(b.find(x.first)!=b.end()){
...
        → Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    使用双指针试试 use double poiters， and move both while left and right have same amount，move only left when left has less，otherwise move the right import java.util.*; import java.io.*; public class Main { public static void main(String args[]) throws IOException{ BufferedReader bf=new BufferedReader(new InputStreamReader(System.in)); PrintWriter pw=new PrintWriter(System.out); Scanner sc=new Scanner(System.in); int n=sc.nextInt(); for(int i=0;i<n;i++){ int k=sc.nextInt(); int arr[]=new int[k]; for(int j=0;j<k;j++){ arr[j]=sc.nextInt(); } int ans=0; int l=0,r=k-1; int a=arr[0],b=arr[k-1]; while(l<r){; if(a==b){ ans=l+1+k-r; l++; if(l<k){ a+=arr[l]; } r--; if(r>=0){ b+=arr[r]; } } else if(a<b){ l++; if(l<k){ a+=arr[l]; } } else{ r--; if(r>=0){ b+=arr[r]; } } } System.out.println(ans); } } }

    → Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

I waste all the time debugging the split string in D. Look like I should learn some python :D

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

i am getting TLE in test case 3 for problem E. 2-Letter Strings . Can anyone explain why is that? Thank you

154427318

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The solution needs to be of O(n) time and your algorithm works in O(n^2) time.

    → Reply
»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

Problems F and G were (in my opinion) the coolest ones in the round. Not surprised to realise that was Mike who proposed them.

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it -11 Vote: I do not like it

    Meaning you would have been surprised if it were to be proposed by Errichto / SlavicG /Mesanu /Flamestorm ?

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem H why we not initialize ans=A[1]&A[2]&...A[N-1]&A[N] because why not that also contribute to final answer?? please reply

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    If some bit from A[1]&...&A[N] contributes to the answer, it means that every number has it, so in that case, n−count_i will be 0. In that case, that bit is catched by the answer anyways (since always k >= 0)

    → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can do that after setting all the bits that will get you the maximum & in all the numbers and this solution did that [submission:https://codeforces.com/contest/1669/submission/154391862]

    → Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Starting questions were easy but last ones were little bit optimising...

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Very good contest for beginners. It would be better if the H problem has a Python solution. The same solution like in tutorial gets TLE.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Unfortunately, it's pretty rare to see a contest with vanilla cpython fully supported all the way up through its hardest problems.

    The main way around this has been for platforms to add pypy support (for which 64-bit has been a vast improvement), combined with substituting in faster input functions... and it's pretty workable (not without quirks/caveats though).

    For reference: 154321651 154359653

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks. It is a striking difference of input() between PyPy 3 64-bit and Python 3.8. I get 297 ms on PyPy 3 64 instead of 2000 ms on Python 3.8 with absolutely the same solution. PyPy performs input() faster almost 7 times.

      → Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    154457903

    154457994

    → Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

For some reason, my code for D didn't work even though the algo is the exact same lol Edit: small bug cost me badly :( but I had to leave the contest early

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

In problem E, why does multiset get TLE and map get AC 154413991 154415571.

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

第一次参加codeforces，打卡 first time to participate contest on codeforces

→ Reply
»
2 months ago, # |
  Vote: I like it +5 Vote: I do not like it

Problem G is 1861. Rotating the Box.

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    This one is even simpler though. There's no rotation involved.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi! This was my first contest. I solved three problems but did not get any rating points. Can someone explain why so?

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    You should wait, then give your points

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How long should we wait and is there a way to solve the problems after the contest? This was my first contest so I had some issues with the submission xD

      → Reply
»
2 months ago, # |
  Vote: I like it -20 Vote: I do not like it

Solutions were leaked. MikeMirzayanov

Problem D — https://ide.geeksforgeeks.org/cRVhmz9gbI

Problem E — https://ide.geeksforgeeks.org/V5RoKGRyPs

Problem F — https://ide.geeksforgeeks.org/r0DMzbirqS

Problem G — https://ide.geeksforgeeks.org/deNrTlJG0p

Problem H — https://ide.geeksforgeeks.org/804K8WBJ9C

→ Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Me with 1300 others after solving all problems! .... Le-m-gendary Greend_mister. (><)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://www.youtube.com/watch?v=8SHACLzAUEI

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

https://codeforces.com/contest/1669/submission/154468622 why is it giving tle and https://codeforces.com/contest/1669/submission/154468664 is not? there is only a difference of break statement. Please clarify

→ Reply
  • »
    »
    2 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, there is a big difference! In the first code where you got TLE, you have not completed taking inputs! you have T test cases, for each test case you are given a value of N and N elements,

    Now in the first code, in the same loop where you are taking input, you are BREAKing that loop just because you have found out your answer! It means if you have found your solution after taking the Y number of Inputs, the remaining N-Y inputs are not taken. So those N-Y inputs will be taken for the next test case, resulting in an Error/WA (Not necessarily TLE)

    You have to take input of all the N elements in each test case.

    Solution: ALWAYS TAKE INPUTS SEPARATELY and do perform Operations on the input you have taken to avoid this type of mistake.

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I might be misunderstanding 1669E - 2-Letter Strings. I thought one could just read the strings and always use the last read string (e.g., s_j) to compare all the j — 1 strings before. I've read the editorial and it makes sense to me. My reasoning tells me that my logic should be the same, so I came up with this code, but it seems to be wrong:

long long res = 0;
vector<string> v(n);
for (long long j = 0; j < n; ++j) {
    string a;
    cin >> a;
    v.push_back(move(a));

    for (long long i = 0; i < v.size() - 1; ++i) {
        res += (v[i][0] != v[v.size() - 1][0]) ^ (v[i][1] != v[v.size() - 1][1]);
    }
}

cout << res << "\n";

I'd appreciate any help! I'm probably missing something silly here ^^'

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You don't have a correct algorithm. You add 0 or 1 to res instead of the quantity of pairs. Please, read tutorial.

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Are you sure about that? :o Can you give a counterexample? If I add 1 whenever a pair (i, j) with i < j satisfies the given condition, I don't have to add the whole quantity of pairs at once. In fact, when changing the vector to a plain array instead, it passes the first 4 tests (but times out at some point because it's O(n^2)). If you'd like me to, I can make an example to clarify the idea of the algorithm.

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Excuse me, your idea is correct. Every new string can add to result as many pairs as many previous strings have exactly one different letter with new one. It is not a good idea to use v.size(). You make a vector v with n empty elements, don't use these elements and append additional elements for every new string. It would be better to input directly cin >> v[j] and use j rather than v.size() — 1. It will be 4 times faster. Of course, O(n^2) is very slow. Only 121 different strings are possible. You can count the quantity of every possible string and calculate the total quantity of pairs after that.

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Agreed! Thanks for the info about vectors, nice to know ^^

          → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Where can I find a video tutorial

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I wrote E so complicated that I was dizzy!!! My stupid code

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Orz

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I could have increase my rating, but I forgot it :)

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is the meaning of ORZ?

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    You can think of it as a gesture

    → Reply
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      gesture, what type of?

      → Reply
      • »
        »
        »
        »
        2 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        A man fell to his knees

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          is it like: 'take a bow'?

          → Reply
          • »
            »
            »
            »
            »
            »
            2 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            I think he's more like kneeling down and support the ground with both hands

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              Forgive me for my poor English...

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                2 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks, sorry for my poor knowledge about these terms!

                → Reply
»
2 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Screencast + video editorial

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Amazing tutorial. I upsolved all the problems using this tutorial and also improve my logic in solved problems. Thanks.

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

why d problem solution is giving error?

anyone please help

for i in range(int(input())):

n = int(input())

l = input().split('W')

bad = False
for s in l:
    b1 = 'R' in s
    b2 = 'B' in s
    if (b1 ^ b2):
       bad = True
print("NO" if bad else "YES")

12 5 BRBBW 1 B 2 WB 2 RW 3 BRB 3 RBB 7 WWWWWWW 9 RBWBWRRBW 10 BRBRBRBRRB 12 BBBRWWRRRWBR 10 BRBRBRBRBW 5 RBWBW Traceback (most recent call last): File "main.py", line 1, in for i in range(int(input())): ValueError: invalid literal for int() with base 10: '12 5 BRBBW 1 B 2 WB 2 RW 3 BRB 3 RBB 7 WWWWWWW 9 RBWBWRRBW 10 BRBRBRBRRB 12 BBBRWWRRRWBR 10 BRBRBRBRBW 5 RBWBW'

** Process exited — Return Code: 1 **

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks for awesome round

→ Reply
»
2 months ago, # |
  Vote: I like it -8 Vote: I do not like it

Hello I think my points are deducted because something related to ideone I got a mail that my solution significantly coincides with other solutions I use Ideone most probably in public mode I didn't know that anyone can copy my code in ideone and I received an email that I broke some rule.

Please if my points are deducted due to this issue I will not use ideone again I will search how to change the public mode in ideone to private.

thank you

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

how to use c++ to finish question D?

→ Reply
  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    We can use an array to save the positions of every character 'W'. Then, they'll devide the string into several parts. For each part, if it only contains 'B' or 'R', cout<<"NO"; otherwise, cout<<"YES".

    → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For 1669D — Colorful Stamp, if you did it slightly differently than the editorial, try this input

1
4
RBWW

It should output "YES"

→ Reply
»
2 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

MikeMirzayanov solutions are always very intuitive and easy to understand. Despite the difficulty of the problem. Great teacher, thanks every one!

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

orz

→ Reply
»
2 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

o__rz____

→ Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

good

→ Reply
»
7 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

According to me, using python in editorial is better than any other language( even tho i myself use Java)...its just more understandable.

→ Reply
»
5 weeks ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Can anyone explain problem E(https://codeforces.com/problemset/problem/1669/E) logic(O(nlogn) or O(n)) in some detail by taking an example? I COULDNT UNDERSTAND EDITORIAL

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

ans += (1 << i); can anyone explain me why are we doing this in problem H ?

EDIT — i got it we are doing pow(2,i) .

→ Reply