Hope the pretests are stronger in this one.

As it is written by link

Well, the "Remember" hasn't been written by link yet :)

UPD: Thanks, it is updated.

Hoping that everyone does great and everyone gets a positive delta in this contest. All the best everyone!!!!!!

Hope I reach candidate master after this round!****

Excited for my 2nd contest

never give any contest for increasing your rating. Just give it to learn something new, and rating will definitely increase sometime!

Hoping to reach Pupil!

Marinush

I have a question, before the contest div 3 before rated, i had been a specialist, and i register at this contest, so they said that i will be rated, but after the contest div 3 before rated, i am a expert, and they( codeforces) said that i was trusted participant in contest (dont have asterisk before name in register in this contest ), so I will be rated or unrated? Thank you.

I hope the contest be good like the latest one yesterday

Good luck and have fun guys!

Pray for downvote

Wish to become pupil!

As a tester, I wish all the beginners good luck!

Hope I reach Radiant this round

Hello MikeMirzayanov,BledDest,vovuh,adedalic.System

I find out some plagiarism activity in Codeforces Round 786 (Div. 3).

Please check out submissions of problem 1674B - Dictionary,submissions are 155621247 and 155678427 They both have same function with same variable but just comment down it and wrote it again with some variable change. Please look out at it.

Proofs given below and also you can check submissions...

I am excited about this round to be easy as the last Div 3 round. ♥

Hope everyone gets a good rank.

Excited to enjoy this round on my birthday! :)

That was an amazing contest! Thanks for the nice problems!

That was an amazing contest! Thanks for the awesome problems!

good problems. Confused in E for half an hour. F and G are good educational problems.

Was thinking on problem B for more than 40 mins and after a bunch of unsuccessful attempts using math it comes to be solvable bruteforcely :) A hilarious thing to make it so and i guess i have to remember sometimes that it is just div3 (even tho i'm 1100 still).

I really enjoyed solving G. Great problems, very educational

i'm trying to understand task c in 1hr still not able to understand what they trying to say (maybe my english is weak)

Did anyone solve F in Python? Keep getting TLE with python and MLE with pypy.

For future reference, here is a solution that is accepted in both python 3 and pypy 3 (surprisingly, about 2x slower in pypy): https://mirror.codeforces.com/contest/1675/submission/156014304

G is O(N*M^3) with very small constant factor?

My approach for F: Vlad and Unfinished Business

We need to travel from $$$src$$$ to $$$target$$$. Root the tree at $$$src$$$. The path from $$$src$$$ to $$$target$$$ is now a vertical path. Call a node infected if we need to compulsorily visit it during our journey. Initially, the only infected nodes are $$$src$$$, $$$target$$$, and the given $$$k$$$ vertices.

Notice that if a node is infected, its parent would also be infected (since we cannot visit it without visiting its parent). Hence, we can propagate infection up the tree via a simple DFS.

To compute the answer, notice that any edge between 2 infected nodes would have to be traveled exactly twice. (One while going from parent to children, and the other while coming back). Hence, the answer is

2*(Count of edges where both endpoints are infected)

However, we do not need to travel back to $$$src$$$ from $$$target$$$. Therefore, we need to subtract the depth of $$$target$$$ from our answer.

Code

There is a bug. My solution to A was accepted, but it's missing in the standings.

UPD: fixed, thanks

how to solve G

Can someone please explain why I am getting TLE in problem B? This is my code- https://replit.com/@StephenV1/TrickyComfortableLanguage#main.cpp

What problem C was all about:

problem c is really hard and it can solved by logic principles only!!

Can someone please explain how to solve E ? Only thing I figured out was in total at most 26 moves every char in string can be converted to 'a'. So, k>26 will always yields aaa...a which is the smallest lexicographical string ( Correct me if I am wrong )

Idk how the heck C has 7000 solves . Believe me D and E are a lot easier than C.

My idea for F — Find the path from x to y. Let the path array be composed of nodes u1, u2, u3 ... ul, where u1 = x and ul = y. Then for every u, do a BFS considering u as the root, and store the distances in a array dis. Then the answer is length of path + 2*(sum of all distances of mentioned k nodes). But it got WA on test 2. Am I missing something?

Submission

F is really a hard problem . I solved it in the last minute , but I even don't know how my code pass the tests. Here is my code : 156006851 . And I consider G a bit standard.

jiangly's code is so concise!

can anyone please explain question E in simple English and explain the third test case? Please don't give any hint about the answer.

Thank you for the contest!

I especially liked problem C for the setting and problem F for key insight.

Can anybody explain why so many RE on test case 7 in problem D with Python? My submission: https://mirror.codeforces.com/contest/1675/submission/155950425

when will be the editorial available?

I see some people cant get the logic of C so probably my approach will be useful: first of all i loop through the whole string and count a total number of occurrences of '0' and '1' in a string (separately for each).

Then i start a second loop and in that loop i also count a number of occurrences of '0' and '1' till i-th element. The first thing we need to see that only the last '1' can be a thief (because for any earlier '1' the will be a '1' later, which confirms that a painting cant be stolen earlier). The same goes for '0', but only the first '0' can be a thief (because for any further '0' there will be a '0' earlier, which says that a painting has already been seen to be stolen before).

Now we move to '?'. Here we had to see that '?' can be a thief only if all '0' are on the right side from '?' and all '1' are on the left side of '?'. The logic is pretty straight-forward: if there is a '0' on the left then the painting was already confirmed to be stolen (which cant happen because its being stolen on '?' only). The same we can see for '1': if there is a one '1' on the right then a painting will be confirmed to be seen (which cant happen because the painting has already been stolen on '?').

You can find my code here: 155985751.

I hope I could help somebody out by doing this, have a great one and see you all tomorrow!

Screencast + Explanations

Here are video solutions (for D-F)

In Problem C , if before 0 any ? occurs why he/she won't be considered as Theif ??

The statement of Problem C is a masterpiece.

It was the best text I've read this year.

Problem C, after you simplify the problem, it is only:

Set counter = 0

3 Cases:

1. It is a '?' increment counter

2. it is a 0, return counter + 1

3. it is a 1, reset the counter to 1.

A B C D E F

Problem C becomes simple if you think it like this: Suppose the ith person is a thief, then from [i+1 to N], there would be no painting present in room, and from [1,i-1], there would be painting present, also every person apart from ith one must be telling the truth, so prefix[i-1] can only have 1's or ? and suffix[i+1] can only have ? and 0's.

well, i'm stuck with E again.

how can i find some problems like this and make some improvement, seems like something between greedy and dp.

want to become blue

Twice in a row that Geothermal FST in div3 contest.

So i am dealing with a problem regarding problem B-Make it increasing.

In first two try I applied the logic that a[n-i]/pow(2, n) <a[i] and so I solved it by taking log in both sides and thus finding value of n and adding it to the answer for all i from n-1 to 1. I used a online ide and in many ide my answer for the 6th test case was coming 11 but in codeforces it is giving 10. Please guide me coz i couldnt find where my logic breaks.Though i later solved it using two loops but I suppose using log will save a lot of time in case of larger arrays. I am attaching the code below. Thanking you all.

    bool ans=true;
    int count=0;
    for(int i=n-1; i>0; i--){
        if(arr[i]==0){
            cout<<-1<<"\n";
            ans=false;
            break;
        }
        if(arr[i]>arr[i-1]){
            continue;
        }
        else{

            int p=(log(arr[i-1]/arr[i])/log(2)) + 1;
            count+=p;
            arr[i-1]=arr[i-1]/pow(2, p);
        }
    }
    if(ans) cout<<count<<"\n";

Hey all, I have a question. For problems such as problem E, how to efficiently create an unordered_map of <character, position of character in alphabet>. For example name this unordered_map alphs: alphs['a'] = 1; alphs['b'] =2.. alphs['z'] = 26;

Note: by 'efficiently' i mean without copy pasting 26 lines and assigning each value one by one. i.e. create without typing too much or using few lines of code.

In the constest Codeforces Round #787 (Div. 3) Problem D (1675D) My submition is (Juliano1 / 155992661)

The code framework I submitted comes from "算法笔记 上级训练实战指南"，a algorithm guidebook published in China in 2021 (ISBN 978-7-111-54040-3)

the frame comes from pages 294 ~ 295 // 层序遍历 (traversal) (I will attach pictures at the end of the comments), just replace the "queue" in the framework with "stack" and at the end of the frame The binary tree PUSH operation is replaced with a PUSH operation of the common tree. The frame code is as follows:

void BFS(int root){ queue q; q.push(root); while(!q.empty()){ int now = q.front(); q.pop(); print(now); if(Node[now].lchild !=-1)q.push(Node[now].lchild); if(Node[now].rchild !=-1)q.push(Node[now].rchild); } }

and here is my code:

void dfs(int root, vector p) { stack s; s.push(root); int cnt = 0; int index = 0; while (!s.empty()) { int now = s.top(); s.pop(); cnt++; ans[index].push_back(now); if (p[now].son.empty()) { ans_len.push_back(cnt); cnt = 0; index++; } else for (int i = 0; i < p[now].son.size(); i++) s.push(p[now].son[i]); } }

It can ensure that my code does NOT HAVE CHEATING in the contest. The same part as other contestants is due to the use of similar templates PUBLISHED BEFORE THE CONTEST, so I apply for restoration of my results.

pictures: