F is shit.

19 месяцев назад, # ^ |

+65

when asking for downvotes and asking for upvotes are unsurprisingly in the same SCC

→ Ответить

bycicle

19 месяцев назад, # ^ |

-48

As a participant, I will have participated.

Spoiler for upvotes:

→ Ответить

19 месяцев назад, # ^ |

+12

you've reposted in the wrong connected component

→ Ответить

User_Carrot

19 месяцев назад, # ^ |

For not wasting time, the secret in lots of spoiler is help_me_please. :D.

→ Ответить

Greedious

19 месяцев назад, # ^ |

← Rev. 2 →

+60

posting mind blowing meme to get upvotes :

→ Ответить

shivansh1102

19 месяцев назад, # |

+60

As the leamder

→ Ответить

absolute-mess

19 месяцев назад, # ^ |

+45

Domne

→ Ответить

anubhavdhar

19 месяцев назад, # |

+52

As an author

→ Ответить

Tom66

19 месяцев назад, # |

+30

Div 1+2 and 8 problems! Looking forward to it.

When will scoring distribution come out?

→ Ответить

physics0523

19 месяцев назад, # |

As a tester, I just hope everyone's super-super-supercalifragilisticexpialidocious performance on the contest.

→ Ответить

glebustim

19 месяцев назад, # |

+30

As not a tester, I did not test this round.

→ Ответить

BARBARIANNNNN

19 месяцев назад, # |

-10

I want contribution, I also want rating, I can't have both of them, So I choose rating instead of contribution.

→ Ответить

DitaMirika

19 месяцев назад, # |

← Rev. 2 →

+15

As a participant,I'm hoping for a great round!

→ Ответить

19 месяцев назад, # ^ |

+14

As an author, me too.

→ Ответить

DitaMirika

19 месяцев назад, # ^ |

Looking forward to it :p

→ Ответить

19 месяцев назад, # |

-262

As an author

→ Ответить

19 месяцев назад, # ^ |

-8

omg that thumbs up emoji looks fabulous

→ Ответить

19 месяцев назад, # ^ |

-21

also YOU SHOULDNT BRAINSTORM THE SOLUTIONS WITH OTHERS DURING CONTEST ITS AGAINST THE RULES

(yes, I couldn't believe my eyes after reading that line)

→ Ответить

19 месяцев назад, # ^ |

-22

what's wrong with all this downvote, I'm just stating the facts. are they all cheaters or what

→ Ответить

19 месяцев назад, # ^ |

-251

Come on dude! Isn't it obvious that, by "you guys", I meant everyone, brainstorm the solutions "individually"

→ Ответить

19 месяцев назад, # ^ |

+76

Well, yes, except for the fact that brainstorming, in common sense and as stated on this wikipedia page, is a "group creativity technique". Using a group creativity technique where there isn't a group would be a pain...

→ Ответить

flakes24

19 месяцев назад, # ^ |

got downvoted for being right

→ Ответить

Jynxzi

19 месяцев назад, # ^ |

now this is a comeback

→ Ответить

19 месяцев назад, # ^ |

help me, this comeback has reversed somehow

→ Ответить

19 месяцев назад, # ^ |

after the contest, I realized.

You (plural) might have tried your best to make the problems as interesting as possible, but you (singular) didn't! Shame on you!

→ Ответить

PolarFlea

19 месяцев назад, # ^ |

F*ck you problem stoler.

Let's downvote him to make his contribution lower than zxyoi cuz it's the second time such situation happens

→ Ответить

AntiXoR

19 месяцев назад, # |

← Rev. 2 →

IIT KGP !orz

→ Ответить

cf-coder

19 месяцев назад, # ^ |

What is IIT KGP?

→ Ответить

drakeramoray27

19 месяцев назад, # ^ |

+10

Indian Institute of Technology, Kharagpur. It's India's one of the best engineering institute.

→ Ответить

ZyadFva

19 месяцев назад, # |

As a pupil contestant

→ Ответить

Hamroz_JONN

19 месяцев назад, # ^ |

Lol bro, u r on the edge of pupil-newbie

→ Ответить

Echp0chmak

19 месяцев назад, # ^ |

and what's so wrong with it?

→ Ответить

ZyadFva

19 месяцев назад, # ^ |

-8

i lost 70 points this round. now it's unrated i got my points back (Thanks god)

→ Ответить

whynesspower

19 месяцев назад, # ^ |

why is it unrated?

→ Ответить

ZyadFva

19 месяцев назад, # ^ |

one of problems was copied from another judge.

→ Ответить

allal

19 месяцев назад, # |

I hope I can do at least the first one

→ Ответить

Omar_Hafez

19 месяцев назад, # |

+91

→ Ответить

19 месяцев назад, # ^ |

+38

When the guy who steals your meme gets more upvotes than you.

Reference: https://codeforces.com/blog/entry/102996?#comment-914421

→ Ответить

19 месяцев назад, # ^ |

first time ?

→ Ответить

tiasmondal

19 месяцев назад, # |

+50

Really happy to see IIT KGP finally setting contests in Codeforces. Kudos to the entire team of problemsetters.

→ Ответить

SalmaHatem_

19 месяцев назад, # |

← Rev. 2 →

+10

I love div.1 + div.2 contests
Good luck for everyone!!
Hoping for a nice problems❤️

→ Ответить

nowadays-

19 месяцев назад, # ^ |

Good luck

→ Ответить

islam231

19 месяцев назад, # |

← Rev. 2 →

Is it rated for DIV 2 ?

→ Ответить

19 месяцев назад, # ^ |

+14

Yes, it is rated for all divisions.

→ Ответить

pirate_hunter_zoro

19 месяцев назад, # ^ |

not any more xD

→ Ответить

Noobish_Monk

19 месяцев назад, # |

Hoping to solve 4 problems, would be great

→ Ответить

19 месяцев назад, # ^ |

-259

Wishing you luck, to solve even more

→ Ответить

nowadays-

19 месяцев назад, # ^ |

Hope you can solve more problems too

→ Ответить

Retired_Snow

19 месяцев назад, # |

Hope to become as soon as possible Candidate Master.

→ Ответить

19 месяцев назад, # ^ |

-266

All the best

→ Ответить

cuzperf

19 месяцев назад, # |

As a xxx

Here is: hided content

The above comment is edited as follows:

<div class="spoiler">
  <b class="spoiler-title">As a xxx</b>
  <div class="spoiler-content" style="display: none;">
    <p>Give me xxx</p>
  </div>
</div>

Here is: <span style="color: white;">hided content</span>

→ Ответить

thelastdinner

19 месяцев назад, # ^ |

+32

However, A new comment will be shown in blue background

→ Ответить

Abito

19 месяцев назад, # ^ |

hidden content*

→ Ответить

Allen123

19 месяцев назад, # |

good luck everyone and hope the problems this time is not mathforces qwq

→ Ответить

19 месяцев назад, # ^ |

some moderate amount of math is fine, last time it was kinda excessive but the problems were very interesting

→ Ответить

pigmike

19 месяцев назад, # ^ |

+23

god, you're everywhere

→ Ответить

Silly__coder__

19 месяцев назад, # |

-12

Contest time collides with IND VS AFG cricket match. Very unfortunate.

→ Ответить

hackerbhaiya

19 месяцев назад, # ^ |

+22

It's IND vs SL!

→ Ответить

mr-strange

19 месяцев назад, # |

All the Best EveryOne!

→ Ответить

nowadays-

19 месяцев назад, # |

Good luck to all

→ Ответить

Ahmed_AboRadwan

19 месяцев назад, # |

Sometimes you win, sometimes you learn

→ Ответить

19 месяцев назад, # |

We just got trolled

→ Ответить

19 месяцев назад, # |

How to solve D?

→ Ответить

dulatcodes

19 месяцев назад, # ^ |

← Rev. 2 →

Color everything in blue. Now do a DFS from node 1. Since m is at most n+2, you will get at most 3 back edges. Store those back edges while traversing by dfs.

Now you have obtained some tree rooted in node 1, with some back edges. Now if you have less than 3 back edges, simply color those back edges as red.

If you have 3 back edges, and they form a triangle, in other words have form a-b, b-c, a-c, color a-b and b-c as red. Now look at a-c. Coloring this as red would be a waste, because a, b, c are already connected. So instead leave it as blue. Find out whether a or c has a greater depth in the DFS tree. Let’s say d = deepest(a, c). Color the edge d and parent[d] in red. This way we preserve the tree structure of the blue subgraph and decrement the number of connected components in the red subgraph.

If you have 3 back edges that do not form such a triangle/cycle. Just color them in red.

I highly suggest drawing a tree structure with back edges to understand it better.

→ Ответить

Saucemaster102

19 месяцев назад, # |

+17

C was so good :D

→ Ответить

AlexMari

19 месяцев назад, # |

Very goood problems A, B, C!

→ Ответить

Ayanokouji

19 месяцев назад, # |

How to solve C? Any hints

→ Ответить

BULLMCHOW

19 месяцев назад, # ^ |

Look at number of index i, such that s[i]='(' and s[i+1]!=')'

→ Ответить

19 месяцев назад, # ^ |

or you can just count '))'s in $$$(s)$$$

→ Ответить

19 месяцев назад, # ^ |

I just use DSU.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

How is its time complexity?

→ Ответить

19 месяцев назад, # ^ |

I don't calculate but get only 31 ms.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

+22

oh. that's fast. maybe the time complexity is $$$O(\text{fastenough})$$$.

→ Ответить

Ayanokouji

19 месяцев назад, # ^ |

← Rev. 3 →

DSU here how? If you could explain your thought process it would be helpful

→ Ответить

19 месяцев назад, # ^ |

I use DSU and at the last step count the different number or parent.If make count+1 at '(' and count-1 at ')' you will see that all i for 1 to 2*n where count =1 or count=0 are conected. I use this obserbation to solve. Sorry for my poor English.

→ Ответить

robostac

19 месяцев назад, # ^ |

Link every opening bracket to it's corresponding closing bracket. Whenever there is a ")(" in the string link those two brackets to handle the "()()" case where 1 needs to connect to 4.

→ Ответить

doraty228

19 месяцев назад, # ^ |

the number of positions such that s[i] = s[i+1] = ')'

→ Ответить

hzr

19 месяцев назад, # |

+233

F is shit.

→ Ответить

Lightnessqwq

19 месяцев назад, # ^ |

+73

Can't agree more.

→ Ответить

19 месяцев назад, # |

Problem C was nice.

→ Ответить

19 месяцев назад, # ^ |

Wut it's easier than A, I'm mad because of B not saying it's hard but I'm so stupid and slow

→ Ответить

19 месяцев назад, # ^ |

me here, getting 150 on A :(((((((((((((((

→ Ответить

19 месяцев назад, # ^ |

Good sir, can I know how you made that observation for C?
I have never been so mad at a problem T-T

→ Ответить

19 месяцев назад, # ^ |

I noticed that () () () for example is all connected then I assumed that all of are disconnected and everytime i see () then this one is connected to another sequence

→ Ответить

19 месяцев назад, # ^ |

"I assumed that all of" you mean 'other' instead of 'of', right?
Also, Thanks but I don't know why I couldn't think of this. Would it be lack of practice of 1400-1500 rated problems?

→ Ответить

19 месяцев назад, # ^ |

It needs some luck i may haven't noticed it but if we are trained on graphs it won't be a problem

→ Ответить

19 месяцев назад, # ^ |

I see, thanks once again :D

→ Ответить

19 месяцев назад, # ^ |

I JUST use DSU and at the last step count the different number or parent.If make count+1 at '(' and count-1 at ')' you will see that all i for 1 to 2*n where count =1 or count=0 are conected. I use this obserbation to solve. Sorry for my poor English.

→ Ответить

19 месяцев назад, # ^ |

Thank you! I guess having a bit more knowledge of dsu might have helped ;(

→ Ответить

19 месяцев назад, # ^ |

It doesn't need any of that just a for loop would work

→ Ответить

19 месяцев назад, # ^ |

Yea true, what I actually meant was, maybe knowing dsu well might have given me a different perspective because I couldn't make that observation.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

here's my crude drawing during contest for C, if it might help:

notice how the component count increases for every two decreasing (or increasing, as others pointed out) steps in a row.

→ Ответить

19 месяцев назад, # ^ |

Ohh nice, I will try this idea after few days and see if I can get the approach. Honestly, what I did was to notice the how deep the opening bracket's are going and counted them.
For eg. ( ( ( ) ) ), depth was 2.

And for this ( ( ) ) ( ( ) ), the depth for both first and second balanced sequence is 1. So, it becomes 2 and added 1 for the remaining component. And, it even passed for all given TCs, which made me believe theres something wrong in the code and not in observation.

I get riddled in my own ideas ;-;

→ Ответить

strgglr

19 месяцев назад, # ^ |

What i thought is when the string is ((())) complete then the answer is n but the time you take out a () outside, a component decreases. So calculate no of instant parenthesis. We already have 1 instant parenthesis in the starting case. So answer will be n-(instant-1).

→ Ответить

19 месяцев назад, # ^ |

Ohh wow, this actually makes sense to me. Wish I would have thought a bit in this direction.
Alsoo, Congrats on specialist!!

→ Ответить

mukulrawat_03

19 месяцев назад, # ^ |

i messed up preety badly at c

→ Ответить

19 месяцев назад, # |

+40

Problem F is boring and hard to implement :(

→ Ответить

shauryasinha020

19 месяцев назад, # ^ |

Any hints for D?

→ Ответить

19 месяцев назад, # ^ |

The connected components are trees.

→ Ответить

drdilyor

19 месяцев назад, # ^ |

← Rev. 2 →

Could you explain how to find spanning tree such that remaining 3 edges don't form a cycle( triangle )?

→ Ответить

19 месяцев назад, # ^ |

+30

Random algorithm .

→ Ответить

nidaboge

19 месяцев назад, # ^ |

How to solve d with random algorithm

→ Ответить

https://codeforces.com/blog/entry/106586?#comment-950389

19 месяцев назад, # ^ |

→ Ответить

ikaurov

19 месяцев назад, # ^ |

+34

Determenistic solution: Do a DFS, for every vertex record parent and depth in DFS tree, find the 3 additional edges. If the edges do form a cycle, take any of the 3 edges (let's say (u-v), where depth[u] > depth[v]) and replace it with edge (u-parent[u]).

→ Ответить

thatsramen

19 месяцев назад, # ^ |

+32

Find any tree, then, if the remaining edges form a cycle, build a new tree with one edge of this cycle in it. It will guarantee that the new tree is ok.

→ Ответить

BULLMCHOW

19 месяцев назад, # ^ |

Nope, for an example, in test case 2, you have one connected component and it is cycle.

→ Ответить

19 месяцев назад, # ^ |

I mean the connected components formed by same color.

→ Ответить

BULLMCHOW

19 месяцев назад, # ^ |

← Rev. 2 →

Oh, okey when.

→ Ответить

19 месяцев назад, # ^ |

By the way , The $$$O(n\times \sqrt{nlog_2n})$$$ solution may be easier to implement.

→ Ответить

19 месяцев назад, # ^ |

FST now :(

→ Ответить

shauryasinha020

19 месяцев назад, # |

hints for D?

→ Ответить

z1bbo

19 месяцев назад, # ^ |

← Rev. 3 →

I also failed it, my approach was this:

use union find to color all red without loops
at the end at most 3 blue edges will be left over
if those three blue edges happen to form a loop, swap the last blue edge with one of the red edges -> there will be no blue loop any more
my problem was I didn't know how to select the correct red edge to swap with, since for some red edges you will create a red-cycle

→ Ответить

shadow9236

19 месяцев назад, # ^ |

You have to check if the edge you are changing from blue -> red should not be between an ancestor and child in the red tree

→ Ответить

Wielomian

19 месяцев назад, # ^ |

Hint 1

Hint 2

Hint 3

Solution

→ Ответить

19 месяцев назад, # ^ |

How is this optimal?

→ Ответить

Wielomian

19 месяцев назад, # ^ |

Each edge has to decrease number of either red components or blue components, and it can only decrese one of those by exactly 1. Thus, the optimal value is $$$2 * n - m$$$. In case of there not being a triangle we have exactly this value with the above method. In case of triangle also this value, but it's a little bit harder to see.

→ Ответить

gyh20

19 месяцев назад, # |

← Rev. 2 →

+34

Defeated by the memory limit of problem F.

I wrote a segement tree without optimizing anything in the last minutes, using the memory of $$$O(n\log n)$$$. When I noticed the memory limits I didn't have time to make a change.

→ Ответить

dl720125

19 месяцев назад, # ^ |

+10

Same here. 256MB is unnecessarily too tight! Lose the chance to gain rating.

→ Ответить

tzc_wk

19 месяцев назад, # ^ |

+20

My ST table didn't get MLE.

However, I forgot to check whether there's a time which can reach n without passing any red lights and got WA on test 7. What a pity.

→ Ответить

__hermit__

19 месяцев назад, # |

What is the expected time complexity for D?

→ Ответить

algoboi

19 месяцев назад, # |

← Rev. 2 →

Can we solve D by randomizing? My idea is you only need to randomize m — n + 1 edges, and check if any of the two sets create a cycle. m-n+1 is at most 3 so it should be fast enough?

The proof of correctness is that, if the graph is a tree, obviously it makes no difference how the edges are allocated. If we have extra edges, then every edges will reduce the connected component by 1, so we make a tree for the blue, and the rest for red, as long as they are both trees.

→ Ответить

shadow9236

19 месяцев назад, # ^ |

+12

Make MST. Pick the $$$m-(n-1)$$$ edges not in MST. Only when $$$m = n+2$$$ can these edges create a cycle. If they do, then take one edge and transfer it to other color and the edge to its parent to current color, provided that the swapped edge is not in its subtree.

→ Ответить

koqo

19 месяцев назад, # |

What is a 'connected component' in Problem D? In the first example, it says blue edges form 2 components, but I only see 1.

→ Ответить

19 месяцев назад, # ^ |

$$$1,2,3,5$$$ was one component, $$$4$$$ was the other

→ Ответить

feecIe6418

19 месяцев назад, # |

+41

F is so annoying to implement (256MB memory limit makes it even worse!). But D and E are interesting.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

How to solve E? I thought its about calculating sums of $$$\frac{P^n_{2k}}{2^k k!}$$$ or smth for $$$1\leq k \leq \lfloor \frac{n}{2} \rfloor$$$

(sorry about the big text, things were becoming unreadable)

→ Ответить

bajablast

19 месяцев назад, # ^ |

Yeah, the way you do that subproblem is by thinking about it conceptually instead of combinatorially. You're trying to find the ways to pair some elements from n things. This can be written as a dp[n] = dp[n-1] + (n-1)*dp[n-2] (you either pair the first element with something, or u don't), which can be precomputed before you do the loop over number of 4-cycles.

→ Ответить

19 месяцев назад, # ^ |

Instead of permutations I thought about the problem with cycles (by building the graph of the permutation). To be almost perfect, cycles either have length 1 (pointing to itself) or length 2 (pointing to each other) or length 4, see picture. Rest was combinatorics. I will link my solution after the grading finished (was 7 minutes too late sadly...). I iterated over the amount of length-4 cycles.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

OHHHHHHH. I was thinking about cycles too, in this process I came up with that formula. totally missed the length-4 cycles though. E was a good problem after all!

→ Ответить

19 месяцев назад, # ^ |

171160691.

First I calculated $$$P_i$$$ by this recursion: $$$P_0=1$$$, $$$P_1=1$$$, $$$P_i=P_{i-1}+(i-1)\cdot P_{i-2}$$$. This is the amount of partitions of $$$i$$$ elements into sets of size $$$1$$$ and $$$2$$$.

Then we calculate the following:

$$$\sum_{i=0}^{4i\le n} \binom{n-2i}{2i} (2i-1)!! \cdot 2^i P_{n-4i} $$$

The sum goes over the amount of length-$$$4$$$ cycles. The binomial calculates how many different distributions for $$$2i$$$ neighbouring 2-tile-pairs there are. The Double Factorial is the amount of combinations to form $$$4$$$-tile-cycles by choosing $$$2$$$ each from the previously distributed $$$2$$$-tile-pairs. Each $$$4$$$-tile cycle then can have 2 different orientations, so we need to multiply by $$$2^i$$$. Then $$$P_{n-4i}$$$ is the amount of combinations to form $$$1$$$ or $$$2$$$ tile pairs from the remaining nodes.

→ Ответить

19 месяцев назад, # |

← Rev. 7 →

why getting TLE at problem B? someone help me

t = int(input())
while t>=1:
    n,m = map(int,input().split())
    if m<n:
        print("No")
 
    elif n%2 == 0 and m%2 !=0 :
        print("No")
 
    else:
        ans = []
        if n%2 !=0:
            ans = [1] * (n-1)
            a = m - (n-1)
            ans.append(a)
        else:
            ans = [1] * (n-2)
            a = (m - (n-2))//2
            ans.append(a)
            ans.append(a)
 
        print("Yes")
        for i in range(len(ans)):
            if i == len(ans)-1:
                print(ans[i])
            else: print(ans[i],end= " ")
    t-=1

→ Ответить

Nikhil19259

19 месяцев назад, # ^ |

@u1602016 You are not decrementing variable t, so it continues to loop forever :)

→ Ответить

19 месяцев назад, # ^ |

oops sorry,last line just got canceled while copy pasting the code.still getting TLE

→ Ответить

Nikhil19259

19 месяцев назад, # ^ |

Can you share the your original submission link?

→ Ответить

19 месяцев назад, # ^ |

Yeah sure https://codeforces.com/contest/1726/submission/171148335

→ Ответить

Varad

19 месяцев назад, # ^ |

use sys module for input, here's my solution- https://codeforces.com/submissions/Varad2002

→ Ответить

19 месяцев назад, # ^ |

thanks a lot @varad2002

→ Ответить

Varad

19 месяцев назад, # ^ |

You’re welcome :)

→ Ответить

savsmail

19 месяцев назад, # ^ |

Same problem. TLE with Python/PyPy3 (pretest 4), OK with C++ (system testing). Slow input/output in Python, maybe.

Is it possible to get pretest 4 for experiments?

Submission https://codeforces.com/contest/1726/submission/171110352 Room (with the other submissions with slightly smodified input/output) https://codeforces.com/contest/1726/room/464

→ Ответить

pajenegod

19 месяцев назад, # ^ |

The way it works is that the input function in Python calls sys.stdout.flush. So everytime you call input you flush stdout, which can be really slow. The way to get around this is to use sys.stdin.readline instead of input. Worth noting is that input internally calls sys.stdin.readline.

If you take a look at C++ submissions will probably see cin.tie(0), which is how you turn off this very same feature in C++.

Knowing how to avoid flushing can be very useful in general. For example your (savsmail) C++ submission speeds up by a factor of 16 by avoiding to flush 171253842 .

→ Ответить

savsmail

19 месяцев назад, # ^ |

Wow, that explains a lot. Thank you!

→ Ответить

Nikhil19259

19 месяцев назад, # ^ |

@u1602016 yes, the problem is with the slow I/O in python as it takes 5-10 times more to run compare to c/c++.

For the cross-check part I have also converted your solution in c++, and tried to submit, and it works perfectly fine within time(561ms, note: your solution is correct) here

Solution??? you could either use the fast I/O for python while doing CP (as @Varad2002 mentioned) or you could use c++ for CP (I would personally recommend this, as I have experienced the situation where my JAVA code throws TLE (even after using fast I/O) whereas same algorithm works within time limit in C++)

→ Ответить

19 месяцев назад, # ^ |

thanks a lot for your suggestions.@Nikhil19259

→ Ответить

d_sqaure

19 месяцев назад, # |

I couldn't enjoy this contest :(, might be very clever problems.

→ Ответить

Rikitexh

19 месяцев назад, # |

hint for c?

→ Ответить

Citypop

19 месяцев назад, # ^ |

)(

→ Ответить

19 месяцев назад, # ^ |

+12

Spoiler 1

Spoiler 2

Solution

→ Ответить

faizanhussain2310

19 месяцев назад, # ^ |

Was this easy to catch this observation as i tried to solve trivally by making DSU but not able to do it

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

Phew, well, depends on your understanding of easy. As I was solving the problem, the Spoilers/Solution which I posted reconstruct my thought process. And I'd say I have noticed them pretty quickly. I didn't even consider building the graph explicitly (and using DSU or similar) yet.

I guess the first thing you want to do is find observations about the structure of the problem. Only if you can't find any structure, you take out the harder techniques. And then try to find structure on the harder techniques. And always user pen and paper!

→ Ответить

Theo830

19 месяцев назад, # |

Any hints for E?

→ Ответить

bajablast

19 месяцев назад, # ^ |

Look at cycle decomposition of $$$p$$$.

→ Ответить

TanSinTheta

19 месяцев назад, # |

Really nice problems ! Keep it up authors ^_^

→ Ответить

rgnerdplayer

19 месяцев назад, # |

+16

D: randomly color all edges. Break if both colors do not form cycles.

→ Ответить

19 месяцев назад, # ^ |

+20

We tried our best to break such solutions, but it seems it was not enough :(

→ Ответить

rgnerdplayer

19 месяцев назад, # ^ |

+13

I would like to know how to break (or attempt to) these kind of solutions.

→ Ответить

19 месяцев назад, # ^ |

My attempts were primarily focused on maximising the number of tests, with $$$n+2$$$ edges in every case, with graphs of ~1e3 (I think?) size. So mostly randomisation. I didn't have much hope of blocking everything because of the small number of extra edges compared to the number of possible spanning trees. If anyone has better ideas, I would be very interested to know...

→ Ответить

Radewoosh

19 месяцев назад, # ^ |

+21

Break? Isn't that correct?

→ Ответить

19 месяцев назад, # ^ |

Some of our testers' solutions using the same idea didn't pass, so I assumed it is incorrect.

Of course, if the number of iterations are sufficient it should pass with high probability. Admittedly, I did not do a thorough analysis of a randomised solution because the model solution does not use randomisation.

→ Ответить

Radewoosh

19 месяцев назад, # ^ |

+17

Well, this one looks way simpler than anything with some logic inside. I'm talking about the version with a guess that we can achieve maximum possible score ($$$2n - m$$$) and we repeat until we succeed.

The intuition for me was that if it's anyhow hard/not straightforward to color the edges so that there are no cycles, these additional edges (yes, it's relative which ones are additional, but I'm talking about kind of a part of the graph in which something interesting happens) have to be close to each other, so the "hard" part of the graph is small, so there are not so many possibilities and we will find good one quickly.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

I did this: Colored red if nodes are in different disjoint sets, blue otherwise. However, for m=n+2, there is a possibility of a cycle of 3 formed.

In that case, I made this observation: Suppose the 3-cycle is ABC then there is a node in A,B,C say A, such that AB and AC are connected using red. Then just take the last edge in the AB red path and make it blue, and make AB(blue) as red. It can be seen that this removes cycles in both red and blue.

→ Ответить

19 месяцев назад, # ^ |

Why the downvotes?

→ Ответить

19 месяцев назад, # |

Really enjoyed the contest, especially because all the questions were not only mathematics based. Also, waiting to submit D, solved just after the time ended. Same thing happening for the second time :')

→ Ответить

19 месяцев назад, # ^ |

+16

D accepted in 1 go after the contest :')

→ Ответить

19 месяцев назад, # |

+16

Code of Problem C <<< Solving Problem C

→ Ответить

19 месяцев назад, # |

-13

wait what the heck

Spoiler

→ Ответить

M_bolshakov

19 месяцев назад, # |

-14

I had to gain only 2 points to reach CM, and solved D on paper, started coding it more than 1 hr before the end, but in the end got TL 9 because i use maps which work slow. But my idea was fully correct. Now end up losing 7 points, and only 9 will be left before CM. this is fucking disqusting, it will be already 5th time when i have <10 points bafore CM!

→ Ответить

palindroam

19 месяцев назад, # ^ |

Oh :/

→ Ответить

sstrong

19 месяцев назад, # |

Isn't $$$1.205710448301$$$ the answer for the first sample in H? I've checked that in geogebra and it seems to be so.

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

Are you sure it's the first sample? I mean to say, you don't mean the second sample by any chance, right?

→ Ответить

sstrong

19 месяцев назад, # ^ |

← Rev. 2 →

I think so, here's the geogebra link: we are looking for the area bounded by $$$AB$$$, $$$AC$$$, and the circle passing through H and center O.

→ Ответить

Artyom123

19 месяцев назад, # ^ |

+26

The area is bounded by a curve, but not an arc

→ Ответить

19 месяцев назад, # ^ |

If you are using a circle as an envelope for the red part, that's incorrect. The curve is not a circle.

Check this: Click here

→ Ответить

sstrong

19 месяцев назад, # ^ |

Oh I see, thanks

→ Ответить

Yahia_Emara

19 месяцев назад, # |

← Rev. 2 →

My solution to problem C passsed system tests, Even though I am pretty sure its so different from the intended solution

I solved with a sparse table and DSU, I am interested to know if the solution is correct and actually fast enough (I am 99% sure its fast enough but I don't know about its validity)

Can Someone Verify?
Submission : https://codeforces.com/contest/1726/submission/171128759

→ Ответить

19 месяцев назад, # ^ |

-8

do note that a lot of the faster ones (usually in Div1) solved it with DSU

→ Ответить

dream7

19 месяцев назад, # ^ |

I too solved it using seg tree and DSU.

→ Ответить

Cooper1214

19 месяцев назад, # |

Back to back bad performance from me, hope I can bounce back soon. People who are in a phase like me, "This shall pass too" :)

→ Ответить

19 месяцев назад, # |

← Rev. 2 →

Check out this ridiculously easy solution for C: 171112911 (don't pay attention to that bin_power_of_two function — I forgot to delete it)

→ Ответить

19 месяцев назад, # ^ |

The interesting thing is that I haven't found any of the red guys yet who would have approached the problem the same way.

→ Ответить

19 месяцев назад, # ^ |

yes, because for them, the simpler (in the sense of observation) DSU implementation came first in mind.

→ Ответить

19 месяцев назад, # ^ |

Could you explain the DSU solution?

→ Ответить

19 месяцев назад, # ^ |

they just constructed the DSU like how they would do a normal graph and counted the components like how they would do a normal graph. only tricky part is what to merge and that's it

→ Ответить

rgnerdplayer

19 месяцев назад, # ^ |

-8

171072071

→ Ответить

19 месяцев назад, # ^ |

→ Ответить

19 месяцев назад, # ^ |

literally ('('+input()+')').count('))') in python.

→ Ответить

19 месяцев назад, # ^ |

Absolutely

→ Ответить

19 месяцев назад, # ^ |

Even this works

→ Ответить

19 месяцев назад, # ^ |

    ll ans=1;
    forsn(i,1,2*n){
        if(s[i]=='(' && s[i-1]=='(') ans++;
    }

→ Ответить

7_7

19 месяцев назад, # |

-10

These unfamiliar names kinda throw me off the track. Wish we could use simpler names

→ Ответить

19 месяцев назад, # |

If the current problem C(bracket sequence) were problem A, would it have been as difficult as it is now?

→ Ответить

19 месяцев назад, # |

My exactly same code got ac after system test

AC code : https://codeforces.com/contest/1726/submission/171155848 TLE code : https://codeforces.com/contest/1726/submission/171146706

code was same compiler was same.... Just for system test load my code got tle...Please @authors do something about this...MikeMirzayanov please do something

→ Ответить

19 месяцев назад, # ^ |

-10

code was same, compiler was same, the difference is the seed

→ Ответить

19 месяцев назад, # ^ |

what is seed?

→ Ответить

19 месяцев назад, # ^ |

← Rev. 2 →

-10

the seed is the value an RNG uses to start with. in your code this is chrono::steady_clock::now().time_since_epoch().count(), which varies by when the submission is run.

→ Ответить

19 месяцев назад, # ^ |

I haven't used rng anywhere in my code...so it was not my fault at all.

→ Ответить

19 месяцев назад, # ^ |

-10

oh, didn't notice it. turns out that your code barely just fit into the TL. I think you would've gotten hacked if this happened during competition, though.

→ Ответить

19 месяцев назад, # ^ |

can you do something ? Newtech66

→ Ответить

MrOtter

19 месяцев назад, # ^ |

+15

Do you really think 1996ms solution for 2s problem is correct?

→ Ответить

19 месяцев назад, # ^ |

-7

How should I calculate this in contest time? Pretests got passed and even system tests too. But the judge load caused me TLE. Whats my fault here?

→ Ответить

ryskmax

19 месяцев назад, # |

Спасибо за раунд авторам, очень интересные задачи!

→ Ответить

dorijanlendvaj

19 месяцев назад, # |

← Rev. 2 →

+116

On A, I saw a solution which initializes the answer with $$$|a_n-a_1|$$$ and, while I could've simply made a test case which breaks that solution very obviously, I instead decided to make fun of the pretests by hacking it with a test case of 50 tests with $$$n$$$ being a random number between $$$1$$$ and $$$6$$$ and $$$a_i$$$ being random numbers between $$$1$$$ and $$$10$$$. While most obviously wrong solutions like the one I hacked FSTd due to hacks specifically made against such solutions, this test case of 50 random tests also unintentionally caused FST of almost 100 solutions that don't work if a test with $$$n=1$$$ has a test right before it such that $$$a_2$$$ of the test right before the test with $$$n=1$$$ is greater than $$$a_1$$$ of the $$$n=1$$$ test.

→ Ответить

19 месяцев назад, # ^ |

-13

LOL that is awesome. this is a legend, as you are too

→ Ответить

toam

19 месяцев назад, # |

+23

Why is the D's constraints so big? I can't understand why sum of N is 1e6. It is hard for python... (I passed pretest but got TLE on system test)

→ Ответить

19 месяцев назад, # ^ |

It was because we were attempting to block randomised solutions. I'm sorry about the situation with Python being too slow >_<

→ Ответить

FynjyBath

19 месяцев назад, # ^ |

← Rev. 2 →

I caught TL52 on the task D (https://codeforces.com/contest/1726/submission/171125630). After contest I sent the same solution again and it got Accepted (https://codeforces.com/contest/1726/submission/171157258). How did it happen? (>2 seconds vs 1.7 seconds)

→ Ответить

Kyou_mo_kawaii

19 месяцев назад, # ^ |

I didn't know randomized wasn't intended. Is this hackable? https://codeforces.com/contest/1726/submission/171121286

→ Ответить

shivam_360

19 месяцев назад, # |

Done C with DSU... how u guys come up with so easy solution...

→ Ответить

19 месяцев назад, # ^ |

-13

observation, but observation isn't all so easy. observation comes along with experience as well

→ Ответить

faizanhussain2310

19 месяцев назад, # ^ |

I am not very comfortable with these graph problem as you can see from my rating that i havent encountered many graph problems till now . Do these graph problem usually have these kind observation asking wrt C

And please guide my what i should do to reach specialist as while practicing i am comfortable upto *1500 problems but during contest i keep on getting stucked on problem C which are usually in the range of *1400 to *1600

→ Ответить

https://codeforces.com/contest/1726/submission/171146699
https://codeforces.com/contest/1726/submission/171158814

19 месяцев назад, # ^ |

I am not very comfortable with these graph problem

So am I! This was a different case though. I just drew some parentheses strings with pen and paper, like '(' = rising slope, ')' = falling slope. Then I connected what I needed to connect based on the statements. After that, it was a long phase of thinking, thinking hard. Usually time for thinking > time for coding, this is very normal. Accepting this is one crucial step to Specialist, imho.

→ Ответить

geranazavr555

19 месяцев назад, # |

+10

Ratings updated preliminarily. We will remove cheaters and update the ratings again soon!

→ Ответить

ganon

19 месяцев назад, # |

← Rev. 2 →

Got Accept with FST code for D.
Why is this so slow? It's just O(NlogN) and N <= 1e6
Can someone explain?

→ Ответить