Codeforces Round 606(Div.1, Div.2) and Technocup — Elimination Round 4

5 years ago, # |

← Rev. 2 →

+72

What is happeninggggggg!!!!!
3 rated contests in 24 hours :3 :3

→ Reply

nantf

5 years ago, # ^ |

Maybe that means some official div1 participants in div2 contest?

→ Reply

5 years ago, # ^ |

I don't think that would happen. They must have left 2 hours gap between tomorrow's 2 contests, so that they can update ratings.

→ Reply

prakhar_111

5 years ago, # ^ |

Will the ratings be updated after finish of both of them or individually?

→ Reply

5 years ago, # ^ |

Individually I guess. Otherwise, some div1 participants will end up participating in div2 contest

→ Reply

SatonoDiamond

5 years ago, # |

+15

There will be 3 Rated contests in 24 hours, it will be a happy weekend !!!!! Thanks to the writers of these contests. :)

→ Reply

5 years ago, # ^ |

-41

Unfortunately one of them clashes with my class time.

→ Reply

Nieb_Hasan_077

5 years ago, # ^ |

All three having unusual starting time.

→ Reply

5 years ago, # ^ |

-14

Thanks for reminding me so that i don't make a mistake like last div3 where i started 30 minutes late.

→ Reply

majk

5 years ago, # ^ |

+129

There are three (3) contests in 24 hours and you're unhappy that one of them clashes with something else. People are really hard to please!

→ Reply

5 years ago, # ^ |

+36

I don't want to miss single one. :(

→ Reply

spookywooky

5 years ago, # ^ |

I like your chart, it is going streight upwards.

→ Reply

Peregrine_Falcon

5 years ago, # |

Short notice for so many contests.

→ Reply

Farabi

5 years ago, # |

← Rev. 2 →

-9

Tomorrow is a great day.. Make a contest..take 2 hours rest..Then again...Boom.. Feeling very much excited...

→ Reply

scauweng

5 years ago, # |

so many contest!!! I've been waiting a long time!!!

→ Reply

Prakash11

5 years ago, # |

Flood of contests!

→ Reply

anupamshah_

5 years ago, # ^ |

Please don't use that word. It sounds negative :(

→ Reply

Nieb_Hasan_077

5 years ago, # |

+11

For those who may want to take part in both rounds.

→ Reply

Lawali

5 years ago, # |

Two div1 contests in the weekend! Great!

→ Reply

ck98

5 years ago, # |

-30

Will jqdai0815 able to reach at the top position today?

→ Reply

Ahmadsm2005

5 years ago, # ^ |

-47

Even if jqdai0815 overtakes Tourist today, tourist will be able to overtake him later. Also, a lot of Legendary Grand Masters like Radewoosh will compete. It is not as easy as you think!

→ Reply

ck98

5 years ago, # ^ |

-42

I know tourist will beat him in next contest. But today he hasn't registered till now. So I was curious about it :)

→ Reply

hocky

5 years ago, # |

← Rev. 3 →

+48

→ Reply

Peregrine_Falcon

5 years ago, # ^ |

Seems like your prediction was wrong. You got minus for only 606. Other two gave you positive rating.

→ Reply

WaterColor2037

5 years ago, # |

+27

WTF there're so many contests in a row (in a column?)

→ Reply

Ohuefmi

5 years ago, # ^ |

→ Reply

pls_be_short

5 years ago, # |

I hope the problem statements are short and clear.

→ Reply

Ohuefmi

5 years ago, # ^ |

← Rev. 4 →

-12

I think problem with short statement are hard to solve compare to problem with long statement.

→ Reply

jjang36524

5 years ago, # |

Scoring distribution?

→ Reply

SevenDeadlySins

5 years ago, # |

Score distribution for the contest?

→ Reply

blobugh

5 years ago, # |

← Rev. 2 →

-6

When Three contest starts at different time

There is still this issue.

→ Reply

NeiH

5 years ago, # |

-11

→ Reply

600iq

5 years ago, # |

+39

There is a very long queue :(

→ Reply

shahidul_brur

5 years ago, # |

Why I can't submit, though I have registered? It says you have submitted exactly same code before, when I submit any code, though there is no submission in my submissions or standing. Why? I tried to submit by editing my code. It is same.

→ Reply

alagorithmet

5 years ago, # |

RIP queue

→ Reply

box

5 years ago, # |

-10

queueforces right now

→ Reply

country_road

5 years ago, # |

-8

Such a long queue. This round should be unrated.

→ Reply

KKKonya

5 years ago, # ^ |

+10

Queue finished. And there was many queue in some of the previous rounds but that rounds doesn't become unrated so this round should be rated because the only worst thing is queue.(There isn't any problem...)

→ Reply

country_road

5 years ago, # ^ |

I submitted solution for problem A, then about 9 minutes later it gives WA. Then I submitted problem B solution, it took 11 minutes to show verdict AC. People who submitted earlier didn't face that problem I guess. So, how is that fair?

→ Reply

KKKonya

5 years ago, # ^ |

-19

I know but in previous rounds it doesn't be unrated for long queue. So i think this contest should be unrated too.

→ Reply

cup_of_tea

5 years ago, # ^ |

-11

Even if it's annoying, it's "fair" in a sense that the guy who submitted earlier was rewarded for his speed.

→ Reply

WoodMachine

5 years ago, # |

+21

Probably it should be good to close gym during online rounds.

→ Reply

Nieb_Hasan_077

5 years ago, # |

+33

→ Reply

5 years ago, # |

+10

How to solve B without building tree of biconnected components?

→ Reply

5 years ago, # ^ |

← Rev. 3 →

+85

DFS from $$$a$$$ without going past $$$b$$$, call the set of reached vertices $$$r_a$$$, and DFS from $$$b$$$ without going past $$$a$$$, call this set of reached vertices $$$r_b$$$. The answer should be $$$|r_a \setminus r_b|*|r_b \setminus r_a|$$$.

→ Reply

mayank_ag

5 years ago, # ^ |

I did the same. Can you please tell how can we solve it by building tree of biconnected components?

→ Reply

hitch

5 years ago, # ^ |

I did the same, got TLEd

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+16

Did you use memset?

If you use a memset on an array like vis[200005] on each testcase... Then as the constraints says, there can be a testcase with 40000 sub-tests.

2e5*4e4=8e9... Then you will surely get a TLE.

generator:

#include<cstdio>
int main()
{
	freopen("1.in","w",stdout);
	register int i;
	puts("40000");
	for(i=1;i<=40000;i++)
	{
		puts("5 5 1 4\n1 2\n1 3\n1 4\n4 5\n2 3\n");
	}
}

UPD: There is a mistake in my generator. Fixed.

→ Reply

hitch

5 years ago, # ^ |

Oh man, you're right. I'm creating a vector array of size 2e5 for every test. resubmitted and got AC. Daaang this could've been my first time solving an E in a contest.

→ Reply

BanazadehAria

5 years ago, # ^ |

Is it true that the common of ra and rb are the vertices that lie one at least one path between a and b? So we can use this to find all vertices that lie to at least one path between vertexes a and b in a graph?

→ Reply

flashmt

5 years ago, # ^ |

We can't (if you mean simple path). a = 1, b = 3, but 4 doesn't lie on the path from 1 to 3.

1--2--3
   |
   4

→ Reply

BanazadehAria

5 years ago, # ^ |

Right so is there a solution to this?

→ Reply

5 years ago, # ^ |

If you're asking about how to solve the problem "given an undirected graph $$$G$$$ and two vertices $$$a$$$ and $$$b$$$, find all $$$v$$$ such that there exists a simple path from $$$a$$$ to $$$b$$$ containing $$$v$$$", I thought about it for a bit and here's what I came up with:

Note that for a tree the answer is trivial; there is only one path from $$$a$$$ to $$$b$$$, so all the vertices from that path must be the answer. Now, for a general undirected graph, we decompose it into the biconnected components tree, and now there exists a path of blocks and cut vertices from $$$a$$$ to $$$b$$$ in our BCC tree, and we take all of the vertices in those blocks and the cut vertices on the path and that should be our answer. I don't know if there's a solution with a simpler algorithm, but I couldn't think of one.

→ Reply

BanazadehAria

5 years ago, # ^ |

what is bcc?

→ Reply

5 years ago, # ^ |

Biconnected components.

→ Reply

RobeZH

5 years ago, # ^ |

+32

It seems that the answer is $$$(\text{No. of vertex not reachable by 'a' without going through 'b'}) \cdot (\text{No. of vertex not reachable by 'b' without going through 'a'})$$$

→ Reply

5 years ago, # ^ |

I'm so stupid. :(

→ Reply

5 years ago, # ^ |

Yeah... After the contest I realized that it is correct:

Define three subsets of the n-2 vertices except a and b:

A={Ai} be the subset of the vertices which can only reach a without passing through a and b;

B={Bi} be the subset of the vertices which can only reach b without passing through a and b;

C={Ci} be the subset of the vertices which can reach both a and b without passing through a and b.

It's obvious that these sets contains all the n-2 vertices and the three sets have none in common. (Since the graph is connected there shouldn't be a point that can't go to both a and b.)

For each unordered pair (x,y) (x!=y):

1)x and y both belong to A. Then there is a path x-...-y don't contain b.

(Both x and y can reach a without passing through b)

2)x and y both belong to B. Then there is a path x-...-y don't contain a.

(Both x and y can reach b without passing through a)

3)x belongs to C. Like 1) and 2), the path needn't contain both a and b.

If y belongs to A or C the situation is similar to 1).

If y belongs to B the situation is similar to 2).

4)x belong to A and y belong to B. then x can't reach y without passing through a or b.

Otherwise:

If a is not on a valid path x to y, then x-...-y-...-b should not contain a (Since y belongs to B). Then according to the definition of B, x belongs to B.

If b is not on a valid path x to y, then y-...-x-...-a should not contain b (Since x belongs to A). Then according to the definition of A, y belongs to A.

Both two suppositions lead to conflictions.

so the answer is |A|*|B|.

→ Reply

ujjk29

5 years ago, # ^ |

Can you please explain it more.

Explain with this example.

I have graph with 11 nodes. Consider 10th node as a and 11th node as b.

Now edges are:


1-a

2-a

3-a



a-4

a-5

a-6



4-b

5-b

6-b



b-7

b-8

b-9

According to your explanation:

A = [1,2,3]

B = [7,8,9]

C = [4,5,6]

So the answer must be |A|*|B| = 3*3 = 9.

But my question is why we aren't considering the path 1-a-4-b-5 as valid?

I know you have written last two lines regarding this but still I am not getting.

Please help me out.

→ Reply

5 years ago, # ^ |

For the solution 1-a-4-b-5...

It doesn't prove that all the paths from 1 to 5 pass through a and b.

Simply we can find another path 1-a-5 proving that the pair (1,5) is invalid.

→ Reply

ujjk29

5 years ago, # ^ |

Ok so we need to find pairs x,y such that all paths from x to y must contain a and b. But in question it was written that find pairs x,y such that any path from x to y must contain a and b.

Please clarify this.

→ Reply

5 years ago, # ^ |

I wonder what is different between those two statements. :(

Logically, "all the things are" equals to "any of the things is", I think.

P.S. Maybe you understood the problem as "Find pairs x,y such that there exists a simple path from x to y that contains a and b"?

→ Reply

Muhimin_Osim

5 years ago, # ^ |

← Rev. 3 →

+10

Run two DFS from a and b individually ignoring b and a respectfully and save the visited nodes in two sets. Now, we have to delete the commonly visited nodes from the two sets. Then, the answer will be the multiplication of the size of these two sets.

→ Reply

majk

5 years ago, # ^ |

+37

Find connected components of the graph without $$$a$$$ and $$$b$$$. Then for each component, determine whether it is adjacent to $$$a$$$, $$$b$$$, or both. The answer is the product of (sums of sizes of components adjacent to $$$a$$$ only) and (sums of sizes of components adjacent to $$$b$$$ only).

→ Reply

abhayps

5 years ago, # ^ |

← Rev. 3 →

My approach was bit different. I did it by doing dfs from a. Find the sum of size of subtree of b's children in dfs tree from which there is no back edge above b. Now, multiply it by (n — (Size of subtree of a's child which contains b) — 1).

→ Reply

joaom

5 years ago, # ^ |

I made two dominator trees, using a and b as roots. The answer is: ((size of subtree b on first tree) -1) * ((size of subtree a on second tree) -1)

→ Reply

_nicktz1408_

5 years ago, # ^ |

← Rev. 4 →

Another way to find it:

Run a dfs from A and as soon as you reach a vertex (and it's not visited), add it to cnt. If you reach B, add it to cnt but do not move forward. It's obvious that n — cnt is equal to the nodes that are not reachable by A if we disconnect B.

Do the same from B and you'll find the nodes that are not reachable from B if we disconnect A. Now, if we get 1 node from cntA and 1 from cntB, we can see that the only way to connect them would be to pass through both A and B. Hence, it's a valid answer!

So, if we multiply cntA and cntB, we get the answer! :)

→ Reply

jsahil730

5 years ago, # ^ |

← Rev. 5 →

Can anyone tell me why my solution is wrong? 66888589

My approach was as follows :-

Remove all the edges from and to b, then count the number of nodes which can't be visited through dfs from a, since these nodes could be visited by adding the edges of b, this simply means that any path from a to these nodes passes through b. Count this number and let it be A.

Do the same after swapping a and b. Let the new number be B.

Then the answer should be A*B, this fails testcase 18 :(

UPD :- Nevermind, I messed up ll and int, fuck my life

→ Reply

blobugh

5 years ago, # |

+10

Too many query problem resulted in too long queue. :(

→ Reply

5 years ago, # |

Any particular edge cases on Div1 C? Failed on pretest 48 :/

→ Reply

NJR9

5 years ago, # ^ |

-15

Check when shortest side is greater than the biggest number of duplicates.

→ Reply

5 years ago, # |

+14

One of my best contests ever. Thank you Endagorion.

→ Reply

AMeyburgh

5 years ago, # ^ |

-18

CF-Predictor is predicting you're going green :)

→ Reply

5 years ago, # |

What is testcase 3 in Div2C

→ Reply

5 years ago, # ^ |

← Rev. 2 →

Try "ttwoonee" For me this was the case.

→ Reply

5 years ago, # ^ |

is answer 2 3 6 acceptable?

→ Reply

5 years ago, # ^ |

Yes

→ Reply

5 years ago, # ^ |

Thanks BTW for your time.

→ Reply

5 years ago, # ^ |

Does your solution pass this case?

→ Reply

5 years ago, # ^ |

The answer is

2
3 6

in my machine Does it matches with your answer

→ Reply

5 years ago, # ^ |

I see your code in comment below. I think "twone" is making both f2 and f3 true in your code which makes an issue here. As it match both with "two" and "twone" starting from t. I hope using else will solve your problem.

→ Reply

5 years ago, # ^ |

And why are you trying to match "twon"?

→ Reply

MohamedHassan499

5 years ago, # ^ |

t##oo#ee Your answer should be correct

→ Reply

5 years ago, # ^ |

Not t##oo#ee it's tt#oo#ee. Here 2 is no of index and 3 and 6 are index.

→ Reply

mayank_ag

5 years ago, # |

Can someone explain Div2 D?

→ Reply

chaitanya99

5 years ago, # ^ |

← Rev. 2 →

[Deleted]

→ Reply

soul_voyage

5 years ago, # ^ |

Resulting sequence can be made of the form — (10)(00,00,00,....00)(01+10, 01+10,......,01)(11,11,11,.....11)(10)

→ Reply

darnley

5 years ago, # |

In Div1C did the authors want an O(n sqrt(n)) solution to pass, or not?

If "yes", then why set TL to 1 second, isn't it right on the edge? Would the problem be spoiled by 2 or 3 second TL?

→ Reply

ChickenInKitchen

5 years ago, # ^ |

it can be solved in O(nlog(n)) but still 800 ms for me ...

→ Reply

5 years ago, # ^ |

← Rev. 5 →

It's easy to improve $$$O(n \sqrt{n})$$$ solution to $$$O(n\log(n))$$$ with 2 pointers.

→ Reply

darnley

5 years ago, # ^ |

Yep, I did it as well, took like 4 lines of code. Thanks :)

My question is not how to do it, but whether authors thought about it, or just decided on a 1 second TL by default.

→ Reply

darnley

5 years ago, # ^ |

Actually, my question to the public is: Did your fast and furious C++ O(n sqrt(n)) solution pass successfully?

→ Reply

ekaerovets

5 years ago, # ^ |

+10

Yes — 66860664

Let's say the size of the compressed input array is m. Then the submission with O(n log(n)) (sort the original array) + O(m log(m)) (sort the compressed array) + O(m sqrt(n)) ≈ O(n sqrt(n)) passes in 0.5s.

Sometimes you may spend a lot of time making a very efficient code just to be bypassed by someone with a bruteforce approach.

→ Reply

yan-zp

5 years ago, # ^ |

← Rev. 2 →

I think author set 1 second, cause it can be done in O(n). my solution pass pretest about 200ms.

→ Reply

ChickenInKitchen

5 years ago, # ^ |

what is the O(nsqrt(n)) solution ?

→ Reply

ekaerovets

5 years ago, # ^ |

Compress the array, and then for i = 1..sqrt(n) find the amount of numbers such that for each a count(a) in input is no greater than i, thus for the current i you may have a rectangle with sides i, count(...) / i;

→ Reply

hocky

5 years ago, # ^ |

← Rev. 3 →

My solution has O(n) complexity :O Capped by the input tho. only took sqrt(n)*log^2(n) to binary search the grid. Upd : nvm. i got sort.

→ Reply

Xellos

5 years ago, # |

+41

Is it just me or was this round overkilled? I tried hard stuff but in the end, if I had a screencast, it would look like this.

→ Reply

RobeZH

5 years ago, # |

Tell me, no one (especially me) is gonna fail in system test.

→ Reply

AM_I_Learning

5 years ago, # |

-9

THIS IS THE POWER OF CODEFORCES TO HOST MANY CONTESTS IN A ROW SALUTE CODEFORCES

→ Reply

Vsevolod_Kaplin

5 years ago, # |

The true way to solve Technocup Elimination A,B,C(sometimes D) problems:

int main()
{
	int t;
	cin >> t;
	for (int i = 0; i < t; i++)
	{
		Evolution();
	}
	return 0;
}

Maybe it will help someone next year...

→ Reply

bicsi

5 years ago, # |

-24

Looks like the key to doing well in contests nowadays is having code snippets for everything.

→ Reply

TheOneYouWant

5 years ago, # ^ |

+33

Can you elaborate? I did A,B,C without needing anything specific (unless my solutions fail).

→ Reply

bicsi

5 years ago, # ^ |

-58

Did you not use biconnected components for B?

→ Reply

ChickenInKitchen

5 years ago, # ^ |

i found B very easy .. just 2 dfs to check the component of each vertex in G-a and G-b ..

→ Reply

TheOneYouWant

5 years ago, # ^ |

Oh, I see. I just did a dfs on a and b, and broke the set of vertices reachable from each into different parts, and then multiplied those reachable by a but not b, and those reachable by b but not a. It probably is the same solution, but the code seemed short (I wrote it myself, didn't use some library code).

→ Reply

theshameem

5 years ago, # |

Can anyone explain how to solve Div.2 D, please?

→ Reply

blobugh

5 years ago, # ^ |

Check the first and the last digit of each string. And you'll be able to classify them as [0~0], [0~1], [1~0], [1~1]. If the second and the third group are all empty, handle that case separately, otherwise regulate the size of the second and the third group properly.

→ Reply

Ohuefmi

5 years ago, # |

Everyone is posting screenshot of list of contest to get UPVOTES .

→ Reply

5 years ago, # |

what are the edge cases in Div 2C

→ Reply

5 years ago, # ^ |

Maybe this "twoooneeee"

→ Reply

5 years ago, # ^ |

is the answer

2
2 6

acceptable?

→ Reply

5 years ago, # ^ |

ok. now try "ooonee"

→ Reply

5 years ago, # ^ |

my answer is

1
4

→ Reply

5 years ago, # ^ |

What about "oonnee"?

→ Reply

5 years ago, # ^ |

answer 0

→ Reply

5 years ago, # ^ |

Can you show me your code.

→ Reply

5 years ago, # ^ |

-31

#include<bits/stdc++.h>
#define lli long long int
using namespace std;
lli mod= 1e9+7;
void solve()
{
   string s;
   cin>>s;
   s+=".......";
   lli ans=0;
   vector<lli>pos;
   lli n=s.size();
   for(lli i=0;i<n;i++)
   {
   // cout<<i<<endl;
      char x= s[i];
      bool f1= false;
      bool f2=false;
      bool f3= false;
      if(x=='o')
     {
       if(s[i+1]=='n' && s[i+2]=='e')
        f1= true;
     }
      if(x=='t')
     {
       if(s[i+1]=='w' && s[i+2]=='o' && s[i+3]=='n' && s[i+4]=='e')
        f3= true;
     }
       if(x=='t')
     {
       if(s[i+1]=='w' && s[i+2]=='o' && s[i+3]!='n')
        f2= true;
     }
     if(f1==true)
     {
       ans++;
       pos.push_back(i+2);
       i+=2;
     }
      if(f2==true)
     {
       ans++;
       pos.push_back(i+2);
       i+=2;
     }
      if(f3==true)
     {
       ans++;
       pos.push_back(i+2+1);
       i+=4;
     }
   }
   cout<<ans<<endl;
   for(lli i=0;i<pos.size();i++)
    cout<<pos[i]<<" ";
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
      solve();
      cout<<endl;
    }
    return 0;
}

→ Reply

Vsevolod_Kaplin

5 years ago, # ^ |

Are you sure about s[n + 3]? Also, this scheme:

one->f1; twone->f2; twon->f3

is very strange.What to do with "twontwontwo"? You doesn't even look at "two" itself.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

1) two -> t#o 2) one -> o#e 3) twone -> tw#ne

→ Reply

5 years ago, # ^ |

I tried the same but failed in TC 3

→ Reply

5 years ago, # ^ |

Do you need my code? I was doing like this and it worked.

→ Reply

whoismrrobot

5 years ago, # ^ |

the case you're looking for is probably twoone

→ Reply

5 years ago, # ^ |

Thank you man, but none are correct. I think there is some kind of overflow of large value

→ Reply

whoismrrobot

5 years ago, # ^ |

after you handle the case of twone, make sure you're advancing iterator by 3, otherwise it'll check the case of one after handling two. This was the case with me.

→ Reply

5 years ago, # ^ |

I did the same and my solution passed two test case,

→ Reply

5 years ago, # ^ |

← Rev. 2 →

I think "twone" is making both f2 and f3 true in your code which makes an issue here. As it match both with "two" and "twone" starting from t. I hope using else will solve your problem.

→ Reply

spookywooky

5 years ago, # ^ |

← Rev. 2 →

There are none. No of indices are twone + (twone-one) + (twone-two).

Remove allways the middle character of the match.

→ Reply

I_Love_Palestine

5 years ago, # ^ |

if the string is "ooneee" , you should only delete 'n' not('o' or 'e') coz if you did you will get oneee or oonee (Invalid output)

→ Reply

5 years ago, # ^ |

I did the same, unfortunately it's not working Thank BTW

→ Reply

5 years ago, # ^ |

svkrdj I have the same problem with it. Could you find out the issue behind it? Please help me with it.

→ Reply

5 years ago, # ^ |

try twontwontwo

→ Reply

5 years ago, # ^ |

← Rev. 2 →

3
10 2 6

This is the output given by my machine. What is the answer?

PS: Can you please tell me what is in pretest 3, if possible?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

As there are multiple test case so there can be many things. For me it was "ttwoonee". Can you show your code?

→ Reply

5 years ago, # ^ |

My code

I've basically stored the starting indices of the substrings where, "one", "two", "twone" occur. And stored them in 3 vectors. And then removed characters accordingly.

→ Reply

5 years ago, # ^ |

Please add '\0' at the end off character array when you are using it as string.

→ Reply

5 years ago, # ^ |

But I guess it's not helping. What should I do? Where's the problem?

→ Reply

5 years ago, # ^ |

I added '\0' at the end of array as 'one\0', 'two\0', 'twone\0' and s[input.size()]='\0'

Don't forget to increase legnth of s by 1.

It got accepted for me then why not for you?

→ Reply

5 years ago, # ^ |

Thanks brother. AC now! Such small mistakes can do big blunders. Lost a lot of time due to it.

→ Reply

5 years ago, # ^ |

← Rev. 2 →

So many data structure in your solution. String,character array, integer array, vector, map. I have rarely seen such many data structure at a place. :p

→ Reply

I_Love_Palestine

5 years ago, # |

← Rev. 4 →

→ Reply

hasankhadra

5 years ago, # |

← Rev. 3 →

I solved the idea for E quickly and was happy about it, but I kept getting wrong answer on test 3 :(

Isn't the solution: We check if both a and b are articulation points and then multiply the number of nodes on a's side(nodes that can be reached by a but not b) by the number of nodes on b's side?

UPD: Can anyone check what is the bug in my code? 66862954

→ Reply

SugA

5 years ago, # ^ |

The idea is kinda seems correct, but it can be simplified by thinking it like:
Answer = (n -Size of the component where 'a' is present after removing 'b' and its incident edges) * (n -Size of the component where 'b' is present after removing 'a' and its incident edges).
This requires just 2 dfs's.
You can find my submission here.

→ Reply

5 years ago, # ^ |

Your idea is correct, but probably you have a bug in your implementation. Anyway, you can solve it much more easily, see here: https://codeforces.net/blog/entry/72120?#comment-564067 (I used a similar approach)

→ Reply

zxz_xmx

5 years ago, # ^ |

I also get the idea for E quickly but i have no time to code.

→ Reply

AM_I_Learning

5 years ago, # |

-25

when I saw A,B,C then --------->

But When I saw D&E,------------->

→ Reply

5 years ago, # |

+31

How to solve Div1D?

→ Reply

5 years ago, # ^ |

← Rev. 2 →

+44

We do subtree dp. For each vertex $$$v$$$ we calculate 3 dp values: when parent $$$p$$$ of $$$v$$$ is taken before we go through edge $$$(v, p)$$$, when $$$p$$$ is taken by edge $$$(v, p)$$$ and when $$$p$$$ is either taken after edge $$$(v, p)$$$ or never taken at all. To calculate it we go through edges incident to $$$v$$$ in sorted order and store intermediate dp for wether we have taken $$$v$$$ and $$$p$$$.

→ Reply

5 years ago, # ^ |

Aren't the first two states the same, because they do not affect the token on v and the tokens in the subtrees? (Of course, the distinction is needed when descending to subtrees)

→ Reply

5 years ago, # ^ |

In the first case when we pass through edge $$$(v, p)$$$ we do nothing and in the second case we have to take $$$p$$$(and in order to do that we must ensure that $$$v$$$ is not taken yet).

→ Reply

5 years ago, # ^ |

Oh right. I was trying to do something similar with just 2 states, I guess that's why I couldn't solve the problem.

→ Reply

MohamedHassan499

5 years ago, # |

How to solve E?

→ Reply

Muhimin_Osim

5 years ago, # ^ |

← Rev. 2 →

→ Reply

iMurat

5 years ago, # ^ |

Actually, we don't even need the sets. I did it in this way: my used[] has an integer type, and I exited DFS when I see a or b. Counted, how many vertices visited twice. Obviously, if used[V] == 2, then it has been visited by both APs. Then just subtracted this value from vA and vB, where vA — number of vertices, accessable from a, and vB — ... from b. The answer, as yours, multiplication of vA and vB.

→ Reply

Wild4Stone

5 years ago, # |

← Rev. 2 →

+11

Pretest 2 of Div2D ???

UPD : I think I found the case when both [0-0] and [1-1] type are present and I was handling this case seperately when abs( number of [0-1] — number of [1-0] ) will be even which was not required at all. After removing this part from the code, it passed perfectly.

→ Reply

Mucosolvan

5 years ago, # |

+10

How to solve Div1C? I figured that we can simulate the process for each rectangle height (at most sqrt(n)), but I couldn't do that in O(n).

→ Reply

5 years ago, # ^ |

+11

I also do the same, but consider only rectangles where height is smaller than or equal to width. Now consider that you don't need to simulate the process (except at the end). If you have a fixed height H, you know you can't take more than H samples from each number. So, with Fenwick tree, count the sum S of all numbers from which there are at most H samples. Then, count the number N of numbers which occur more than H times in the array. In the end, calculate S + H * N — this is the maximal amount of numbers you can get. You can then find the max. width you can have for height H.

→ Reply

Mucosolvan

5 years ago, # ^ |

All my countercases to similar approach failed only when W < H, this is so simple, yet so effective! Thanks :)

→ Reply

TheSawan

5 years ago, # |

Why the announcement for problem D in the contest was titled "Problem E" ??

→ Reply

skye_high

5 years ago, # |

Can someone show me pretest 3 for DIV2 C please?

I can't figure out why it failed for me.

→ Reply

5 years ago, # ^ |

Struggling for the same

→ Reply

Trgt_2021_explosion

5 years ago, # ^ |

mine was wrong bcz I didn't consider string of single character(of length 1.) and I got runtime error...after taking this in care it passed. so u can check this.

→ Reply

phantom11

5 years ago, # |

Is there any successful hacks in this contest? Strong pretests!!

→ Reply

hasankhadra

5 years ago, # |

← Rev. 2 →

+28

In problem D there is a problem in the constraints!

It's written "The sum of word lengths doesn't exceed $$$4*10^6$$$" but the length of a single word isn't mentioned, so we should consider that the maximum length could be $$$4*10^6$$$. I submitted D at minute 46 (with setting $$$2*10^5$$$ the size of the char array) but before the end of the contest I noticed this problem and I changed the size of the array to $$$4*10^6$$$ and resubmitted.

Now after the contest I resubmitted the code that has only $$$2*10^5$$$ array size and it passed! This is totally unfair. You either should consider my first submission or modify the tests for all of the contestants.

UPD: Please look in it, it would give me 150 ranks up! Endagorion voidmax

→ Reply

ofcoursenotsh

5 years ago, # |

I almost missed it...Although I didn't get good results in it...

→ Reply

xodeChemist

5 years ago, # |

Two rated contest within 4 hours of difference

→ Reply

lov.ish

5 years ago, # |

Not satisfied with the delay of submission verdict. Did a silly mistake and got WA on test 1 after 10 minutes.

→ Reply

hohl

5 years ago, # |

← Rev. 2 →

+13

For Div2 Problem C- "As simple as One and Two", an important test case is missing.

The test is repeated 'twone' and it will lead to TLE in some solutions.

Test generation in Python

print(10)
for _ in range(10): print('twone'*(3*(10**4)))

In my opinion, it should atleast be added to the testcases for those who try it in practice later so as to fully test correctness.

→ Reply

dtc03012

5 years ago, # |

+30

I BECAME THE PURPLE!!!!

→ Reply

SugA

5 years ago, # ^ |

Cherry bomb!
Same here :)

→ Reply

Tutis

5 years ago, # |

← Rev. 3 →

+26

For div1 E:

solution

→ Reply

Endagorion

5 years ago, # ^ |

+38

Damn, not again... I'm not doing great at making testcases for this kind of problems, do I.

Your solution seems to timeout on a case

-1000000000 -499999999 0 500000001
-750000000 -249999999 250000000 750000001

→ Reply

Tutis

5 years ago, # ^ |

← Rev. 3 →

What if I do 20 random moves in the beginning?

UPD: Does not work.

→ Reply

Endagorion

5 years ago, # ^ |

I'd expect a sufficient amount of fiddling should be enough to pass any given test.

I really should have made this a multitest, seems so obvious in hindsight.

→ Reply

sigma_g

5 years ago, # |

← Rev. 2 →

+26

My Div1C code passed pretests (50+ tests). It failed the main tests (runtime error on test 33). I submitted same code again twice after contest. It passed both times! Why?! How?

Two consecutive ACs submitting same code after contest https://codeforces.net/contest/1276/submission/66875312 https://codeforces.net/contest/1276/submission/66875827

RE on main tests of in contest submission https://codeforces.net/contest/1276/submission/66867062

→ Reply

sigma_g

5 years ago, # ^ |

Never mind, now that I had a look at pretests, it was a dumb out of bounds access.

→ Reply

theBanzaiPredicament

5 years ago, # |

+65

Why can't we see others submissions and tests past samples?

→ Reply

nethish

5 years ago, # |

Does anybody know why this code for Div 2 E failed?

Spoiler

#include
using namespace std;
#define ll long long
#define ld long double
#define endl "\n"
#define dbg(x) cout << #x << " = " << (x) << endl;
const ll MOD = 1000000007;
const ll INF = 0x7fffffffffffffff;


template 
void print(T v, int l = 0, int r = 5){
    for(int i = l;i < r;i++) cout << v[i] << " ";
    cout << endl;
}

int t;
int n, m;
const int M = 300000;
vector> g(M);
int v[M];
int vnum = 0;

void dfs(int x, int y) {
    v[x] = 1;
    vnum++;
    for(auto i: g[x]) if (!v[i] and i != y) {
        dfs(i, y);
    }
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> t;
    while(t--) {
        memset(v, 0, sizeof v);
        int a, b;
        cin >> n >> m >> a >> b;
        a--; b--;
        for(int i = 0; i < m; ++i) {
            int x, y;
            cin >> x >> y; x--; y--;
            g[x].push_back(y); g[y].push_back(x);
        }
        vnum = 0;
        dfs(a, b);
        int xx = n — vnum — 1;
        vnum = 0;
        memset(v, 0, sizeof v);
        dfs(b, a);
        int yy = n — vnum — 1;
        cout << max(0, (xx * yy)) << endl;
        for(int i = 0; i < n; ++i) g[i].clear();
    }
}

→ Reply

madhav_1999

5 years ago, # ^ |

Answer can be > INT_MAX Use long long for final multiplication

→ Reply

2022OVO

5 years ago, # ^ |

Is it wrong answer on pretest 18?

There're at most 2*1e5 points, xx * yy may become 1e10 as a result, you may use long long to store it.

→ Reply

mip182

5 years ago, # |

+45

Can you, please, open test's verdicts

→ Reply

5 years ago, # |

What was the idea for Div2 D?

→ Reply

WA_TLE_Procastinate_AC

5 years ago, # |

+12

Why submissions aren't visible?

→ Reply

alphatrance

5 years ago, # |

← Rev. 2 →

Can someone explain why this solution is failing? 66858891

Edit: It fails in the case

1 t

But I still can't figure out why?

→ Reply

aayushgarg_03

5 years ago, # |

Please post the editorials

→ Reply

soul_voyage

5 years ago, # |

Can someone please explain or provide a small case why this IEP based solution for E is wrong — 1. Add total pairs

We subtract those pairs which are in same component after removing a — because they can be reached without a.
Same as 2 but after removing b.
We add those pairs which are in same component after removing both a and b because they are subtracted twice.

→ Reply

Stelutzu

5 years ago, # ^ |

6 8 3 4 1 2 2 3 2 4 3 5 4 5 5 6 You will get a negative answer

→ Reply

soul_voyage

5 years ago, # ^ |

Thank you!

→ Reply

ZxCv

5 years ago, # |

Why are the solutions not visible?

→ Reply

verma_ankit484

5 years ago, # |

Can anybody see why does this code(div2 E) failed?

Code

//verma_ankit484

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

typedef long long ll;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
#define pb push_back
const ll mod = (ll) 1e9+7;

using namespace std;
using namespace __gnu_pbds;

#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>

ll n, m, a, b;

vector<vector<ll>> adj;
vector<bool> visited;
vector<ll> vv;

ll dfs(ll s) {
  if (s == a) return vv[s] = -1;
  ll ss = 0;
  visited[s] = true;
  for (auto i : adj[s]) {
    if (!visited[i]) {
      ll p = dfs(i);
      if (s != b and p == -1) return vv[s] = -1;
      if (p != -1) ss += p;
    } else {
      if (vv[i] == -1) {
        if (s != b) return -1;
      }
    }
  }
  return vv[s] = ss+1;
}

ll dfs2(ll s) {
  if (s == b) return vv[s] = -1;
  ll ss = 0;
  visited[s] = true;
  for (auto i : adj[s]) {
    if (!visited[i]) {
      ll p = dfs2(i);
      if (s != a and p == -1) return vv[s] = -1; 
      if (p != -1) ss += p;
    } else {
      if (vv[i] == -1) {
        if (s != a) return -1;
      }
    }
  }
  return vv[s] = ss+1;
}

int main() {
  IOS
  #ifdef AV
  freopen("int.txt", "r", stdin);
  #endif
  ll t;
  cin >> t;
  while (t--) {
    adj.clear();
    cin >> n >> m >> a >> b;
    adj.resize(n+1);
    ll x, y;
    for (ll i = 0; i < m; i++) {
      cin >> x >> y;
      adj[x].pb(y);
      adj[y].pb(x);
    }
    visited.clear();
    visited.resize(n+1, false);
    vv.clear();
    vv.resize(n+1, 0);
    ll p1 = dfs(b)-1; //minus one to exclude b
    visited.clear();
    visited.resize(n+1, false);
    vv.clear();
    vv.resize(n+1, 0);
    ll p2 = dfs2(a)-1; // minus one to exclude a
    ll ans = p1*p2;
    if (ans <= 0 or p1 <= 0 or p2 <= 0) {
      cout << 0 << endl;
    } else {
      cout << ans << endl;
    }
  }
  return 0;
}

→ Reply

5 years ago, # |

← Rev. 2 →

Can someone please explain the approach for DIV2 D and also the corner cases?

Thanks.

→ Reply

code_hard123

5 years ago, # |

+10

ConstructiveAlgorithmsForces

→ Reply

IWMG

5 years ago, # ^ |

-8

Welcome to the russian contests

→ Reply

pepelats

5 years ago, # |

Why cant we see testcases?

→ Reply

5 years ago, # |

How to solve div2D and div2E?

→ Reply

madlogic

5 years ago, # ^ |

← Rev. 3 →

Div2 D

Notice that the only important thing is the first and last character of the string so the possible values are (0,0), (0,1), (1,0) and (1,1)

Notice that you can continue alternating the (0,1) and (1,0) they will continue forming a good sequence and you can add all the (0,0)'s in between any (0,0) and (0,1) and all the (1,1)'s in between any (0,1) and (1,0)

With that said you just have to check if it's possible to alternate the (0,1)'s and (1,0)'s also reverse a few of them as possible and check that the reversed value is unique.

My solution: Link

This is the best I can explain my solution it's really difficult to explain it and I hope the code helps.

→ Reply

MidoriFuse

5 years ago, # ^ |

2E: Delete every nodes that can reach both A and B without going through the other. Now the answer is (how many nodes that can reach A)*(how many nodes that can reach B).

→ Reply

expect2004

5 years ago, # ^ |

And pay attention that the answer may over INT_MAX. I got WA on test18 because I didn't notice this before :( .

→ Reply

robotolev

5 years ago, # |

+11

When we can see the results of Technocup? How many people will be invited to the final?

→ Reply

expect2004

5 years ago, # |

Well...When will the solution be given?

→ Reply

KKpoker

5 years ago, # |

still could not see others solutions?

→ Reply

AvinashKartik

5 years ago, # |

In Div 2 F I'm getting WA on TC 37 and I'm not able to figure out why. Anyone else got WA on fixed it? It would be great anyone is able to give some corner test case.

→ Reply