Codeforces Round #784 (Div. 4) Editorial

Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/Typewriter/Regular/Main.js

Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

flamestorm's blog

Codeforces Round #784 (Div. 4) Editorial

By flamestorm, 11 days ago, In English

Tutorial of Codeforces Round #784 (Div. 4)

11 days ago, # |

Thanks for the round, I loved it!

11 days ago, # |

props on hosting a div 4 round

11 days ago, # |

I was too slow to finish H

11 days ago, # |

Thanks for the awesome round and light fast editorial!

11 days ago, # |

My first full solved round! Let's goooo!

10 days ago, # ^ |

same to me

11 days ago, # |

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

10 days ago, # ^ |

same hahahaha

10 days ago, # ^ |

hahah，，same

11 days ago, # |

The problems were so easy. In my personal opinion it should have been Div. 5. next time, try to do smth more difficult. ez top 1 <1400

11 days ago, # ^ |

Yeah I definitely agree that this contest was too easy. Pretty much everyone I know, including several newbies, solved every problem.

I'm all for easier contests for less experienced coders, but 3383 people AK-ing the round makes the first 3k spots separated by penalty only, which just shouldn't happen.

I think Div. 4 rounds are a really good addition to Codeforces, and I believe that today's problemset was really fun, even though I liked the difficulty curve from round 640 better.

11 days ago, # |

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!

11 days ago, # |

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.

11 days ago, # |

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

11 days ago, # ^ |

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

11 days ago, # ^ |

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

11 days ago, # ^ |

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

...
        for(auto x : al){
            ll temp;
            if(b.find(x.first)!=b.end()){
...

10 days ago, # ^ |

← Rev. 2 →

使用双指针试试 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); } } }

11 days ago, # |

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

11 days ago, # |

The comment is hidden because of too negative feedback, click here to view it

10 days ago, # ^ |

← Rev. 2 →

Buddy, "upvote me please", never works

11 days ago, # |

← Rev. 2 →

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

154427318

11 days ago, # ^ |

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

11 days ago, # |

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

11 days ago, # ^ |

← Rev. 2 →

-11

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

11 days ago, # |

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

11 days ago, # ^ |

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)

11 days ago, # ^ |

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]

11 days ago, # |

← Rev. 2 →

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

11 days ago, # |

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.

11 days ago, # ^ |

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

10 days ago, # ^ |

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.

10 days ago, # ^ |

TLE with Python 3.8.3 154483619 Accepted with PyPy 3.7.10 (7.3.5 64-bit) 154483785

11 days ago, # |

← Rev. 3 →

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

10 days ago, # |

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

10 days ago, # ^ |

Thanks. P/s: I have upvote your comment.

10 days ago, # |

← Rev. 2 →

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

10 days ago, # ^ |

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

10 days ago, # ^ |

Orz, what iş means?

10 days ago, # ^ |

orz looks like a man is on his knees.it means i admire him very much

10 days ago, # |

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

10 days ago, # ^ |

You should wait, then give your points

10 days ago, # ^ |

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

10 days ago, # |

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

10 days ago, # |

10 days ago, # ^ |

← Rev. 2 →

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.

10 days ago, # ^ |

Thanks a lot! Will always keep that in mind.

10 days ago, # |

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 ^^'

10 days ago, # ^ |

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

10 days ago, # ^ |

← Rev. 2 →

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.

10 days ago, # ^ |

← Rev. 2 →

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.

10 days ago, # ^ |

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

10 days ago, # |

Where can I find a video tutorial

10 days ago, # |

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

10 days ago, # |

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

10 days ago, # |

what is the meaning of ORZ?

10 days ago, # ^ |

You can think of it as a gesture

10 days ago, # ^ |

gesture, what type of?

10 days ago, # ^ |

A man fell to his knees

10 days ago, # ^ |

is it like: 'take a bow'?

10 days ago, # ^ |

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

10 days ago, # ^ |

Forgive me for my poor English...

10 days ago, # ^ |

Thanks, sorry for my poor knowledge about these terms!

10 days ago, # |

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

9 days ago, # |

← Rev. 2 →

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

9 days ago, # |

Thanks for awesome round

9 days ago, # |

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

9 days ago, # |

how to use c++ to finish question D?

8 days ago, # |

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

1
4
RBWW

It should output "YES"

3 days ago, # |

← Rev. 2 →

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

Codeforces Round #784 (Div. 4) Editorial

flamestorm's blog

Where can I find a video tutorial

Recommend

Seata AT 模式

邢山虎：指责加班是特定时期的悖论，历史将予以澄清

五一无堂食，预制菜走俏，盒马：烤串组合销量翻倍

饿了么联合餐饮及零售商户，在京紧急加大预制品菜供应

10+ ways to visualize your martech stack

【VSCode】VSCode入门介绍及使用技巧

【Nginx】记一次Nginx生产环境的Trouble Shooting过程

【Redis】用Docker-Compose搭建Redis主从复制

【Redis】用Docker-Compose搭建Redis Sentinel

JavaScript之函数(二) 函数内部三个不常见的属性

About Joyk