As the author of rejected problems the date of this round, I hope you will enjoy it.

As a tester I must say problems are really interesting and well written and please notice unusual solving time. Good luck to all...

(1500 + 1500) means that there are subtasks?? Since every time when subtasks are there, then author mentions it...but this time they haven't mentioned

At first, I got excited about subtasks because of the $$$+$$$ sign, but then I realized that they won't change my score, it will still be $$$500-(750+750)-1500-2250-4000=-8750$$$

What a special weekend! Codeforces Round 700 and Topcoder SRM 800! :D Kudos to both Codeforces & Topcoder.

EDIT — It's SRM 799.

As a tester, I hope you will participate in and enjoy the interesting round!

Codeforces Round # 700, this is a special milestone.

What a Sweet AdHoc/MathForces round!

GoraGoraGOra

I am 1990 now, and I hope that tomorrow I can take a master. Can you give me some advice on how I should solve problems: solve B2 or solve B1 first and then think about B2?

woow, score distribution is announced so early! I appreciate it!

Wow colourful testers!!!

I see there is a pupil tester as well. Can anyone tell how to contribute to Codeforces as a tester?

No one

Literally No one

First few comments downvoted as usual

If you saw your comment downvoted recently, that was me :)

Can anyone tell me how to get upvotes without telling me how to get upvotes?

there are three expected rating in this round for me.....ratng<1535 or (rating>=1535 and rating<1600) or rating>=1600....Pray for me

Wrong answer on pretest 6. :(

You suck Great Hero

long queue again? :(

i literally fucked up in the today's contest who else also fucked up his contest today !! stucked on B ; C --> Interactive don't know how to solve Interactive problems D--> Wrong answer on pretest 6 !!

I have a one question..if i get wrong submission in one question ..then will it decrease 50 point from total point or from particular question.?

I'm sorry, but we're heading for no pretests at all? Why is C (div 1) only 5 pretests, taking into account that there are 2 samples? The round is still going on, and I don't know if my solve will fall, but it's still unpleasant...

what are the chances that div2 b has weak pretests.

.

this is the 100th time I WA for writing the wrong variable XD why do I keep doing this mistake?

Contest is anti-traditional because WA on pretest 6 not 2

For those who want test cases of Div 2 B -

(order of monsters matters)

here is(just like TC3 but in descending order) —

1
1000 1000 4
500 400 300 200
1000 1000 1000 1000

answer should be "YES"

basically we have to sort the monsters in ascending order (first attacking power and if attacking power same them by their health )....so that hero kill small monsters first and then kill the large monster and himself dies(if possible).

Video solution to problem C: https://youtu.be/AgJrby-pShU

How to solve C?

Beacause of the long queue I didn't get to finish E in time :(.

Here is my solution to E:

Put an edge 1->2 with cost 1

For every node put edges such that the lengths of the paths ending with him are in the interval [1, 2 ^ (n — 2)]. By that I mean:

1->n cost 1

2->n cost 1

3->n cost 2

i->n cost 2 ^ (i — 2)

Now simply use as many of these power of 2 intervals to build the interval [L, R]. I wa'd because of the long queue and a dumb error :(

Those who are getting WA on pretest-6 for DIV2D. Try this

8
2 2 0 2 0 1 2 2

Ans = 8

Two possible segments are

2 0 2 0 2
2 1 2

I wonder if anyone got more WA than me:)

https://www.geeksforgeeks.org/find-local-minima-array/

What is pretest 4 in Div1 C?

"Wrong ans on pretest #6" I guess I saw/read this line max number of times :|

One of the best contests I have seen in a while and I am saying this because this is one of the few contests where I was stuck to my laptop for solving D1, D2 until the very end. And, they didn't seem unsolvable which they usually do.

Thanks for these brilliant problems, authors

Much kudos to you liouzhou_101

How about setting E to be $$$4 \cdot 10^8$$$ points?

The problem with B pretest 2 is that you have to sort the monsters based on their attack power increasingly so that you fight monsters with low attack power first.

Was $$$N log^2 N$$$ with persistent trees supposed to fail on D (I know it can also be done with parallel binary, but I'm curious for the persistent tree solution)?

It's so sad when you find a $$$\mathcal{O}(n\ \text{polylog}\ n)$$$ solution to a problem and it's too slow QAQ

Is there a $$$\mathcal{O}(n \log^2 n)$$$ algorithm to D or are you supposed to make $$$\mathcal{O}(n \log^3 n)$$$ fit TL?

proublm D1 try this 13 2 2 2 2 2 2 4 5 3 2 2 2 2 answer is 7

My code for div1D: almost 300 lines! Short explanation:

• First off, let's denote $$$B_{v,a}$$$ — number of values $$$a$$$ on the path from $$$0$$$ to $$$v$$$ inclusive.
• Look at the value $$$a_l$$$ in LCM(u, v); if it's inside $$$[l, r]$$$, we want to check if $$$B_{v,a_l} = B_{u,a_l}$$$, and otherwise, we want to check if $$$B_{v,i} = B_{u,i}$$$ for some $$$i \in [l, r]$$$ different from $$$a_l$$$.
• We can turn that into uniform queries: check if the claim "$$$B_{v,i} \neq B_{u,i}$$$ for some $$$i \in [l, r]$$$" is true/false. They can be used to solve the problem through binary search. How do we answer a set of such queries?
• We can't remember $$$B$$$, but we can traverse the tree using DFS and update a common array to get rows of $$$B$$$.
• Let's hash subarrays of $$$B$$$. We need to support 2 operations: update a value to get the current row of $$$B$$$ and get the hash of some subarray of this row. It can be done with a Fenwick tree.

If you are still figuring test cases that break your solution for div2D1

7
2 2 1 2 1 2 2

7
2 2 1 3 1 2 2

8
2 2 1 3 2 1 2 2

8
2 2 1 2 3 1 2 2

9
2 2 1 2 3 2 1 2 2

How do you solve D2D? Asking both for first and second version. Thanks.

fuck you son of the bitches!!!!!

In the last 3 minutes I got AC on div2 D1.

I edited it to convert for D2. Submitted when 2 seconds were left but cf didn't accept it saying the contest is over. If my D2 passes now Imma gonna cry !

EDIT: The div2 D2 I couldn't submit was correct. Also my C failed system tests coz I binary searched on both halves and therefore exceeded the number of queries. Life can make you happy and sad at the same time.

Could someone from the testing team please tell me why the verdict for this dataset in Div2 problem B is "YES". 1 1 1000000000 10 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 I used it for hacking. But apparently the accepted verdict is "YES.

Very nice problems !!!

I wonder why was pure bruteforce solution containing 10^9 operations was not getting challenged in Div2 B. Unnecessarily I got two unsuccessful hacking attempts. liouzhou_101 & MikeMirzayanov please check this as many such solutions will wrongly get accepted.

Here is the java based input generator I used for hacking that solution:

public class InputGenerator {
    public static void main(String[] args) throws Exception {
        System.out.println(1);
        System.out.println("1 1000000000 100000");
        int n=100000;
        for(int i=1;i<n;i++)System.out.print("1 ");
        System.out.println(1);
        for(int i=1;i<n;i++)System.out.print("1000000000 ");
        System.out.println(1000000000);
    }
}

The target solutions I unsuccessfully tried to hack:

• https://codeforces.com/contest/1480/submission/106805271

• https://codeforces.com/contest/1480/submission/106806952

I got something unexpected for this hack: I believe it generates a valid test, but I got

Validator 'validator.exe' returns exit code 3 [FAIL Expected integer, but "/**" found (stdin, line 1)]
close

Could you check what's going on?

Whats the hack case you guys using for div1A/div2C?

I registered for the contest but I couldn't attend because of a sudden meeting :(

Does my ranking go down?

liouzhou_101 I request you to reduce the full score of Div2C. There are almost 4 times more submissions on this Problem compared to Div2D1 which also has the same score. This is unfair for the people who solved Div2D1 and not Div2C (and i believe they deserve more credit). Moreover Div2C was easily found with a simple google search as well here

g

Div2 D2 pretest 6?

Why is this solution in problem Div2.D1 incorrect? https://codeforces.com/contest/1480/submission/106825810

Why brute force is passing the pretests for DIV 2 C?

I think problem Div1A/Div2C has appeared in leetcode or in some FAANG interview, because I saw and solved the absolutely same problem before

D1 pretest 6 ? Div 1.