vovuh's blog

Codeforces Round #377 (Div. 2) Editorial
By vovuh, history, 8 years ago, translation, In English
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
  • Vote: I like it
  • +24
  • Vote: I do not like it

Comments Comments (20)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by danilka.pro (original revision, translated revision, compare)

→ Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think I used a simpler method for C, this is the observation:

Let M be the maximum of {b, d, s}; then the other 2 would be in the best case M — 1. So if b is the maximum, then (d >= b — 1 and s >= b — 1) always holds true.

This is the code: http://codeforces.net/contest/732/submission/21550209

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    "So if b is the maximum, then (d >= b — 1 and s >= b — 1) always holds true."

    In case {b = 6, d = 3, s = 3} your statement is wrong. In that case b is maximum, but d < b - 1 and s < b - 1. Or did I miss something?

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone explain last line for f. with example? why orient (v,to) to (to,v)?

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just think about it, if you are pointing from v→to, you are leaving the largest cycle pointing outwards.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi, I'm not understanding why my submission is getting TLE for Div2 F. can anyone please check it? Here's my submission, 21830666 I have implemented it exactly as given in the tutorial.

→ Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In Problem B, test-10:

Input
5 2
0 0 0 1 0
Output
4
0 2 1 1 1 
Answer
3
0 2 0 2 0
Checker Log
wrong answer Jury answer is better.

Obviously my answer is better?

→ Reply
  • »
    »
    8 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    " Write a program that will find the minumum number of additional walks "

    I am pretty sure it is not obvious that 4 < 3.

    → Reply
»
8 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Div2D Exams

Consider the following test case

10 3
0 3 0 1 0 0 0 0 2 0
1 1 4

The following AC submission gives the answer as 9. I would like to know how is the answer 9 correct. Since subject 3 requires 4 days of preparation, which clearly isn't possible, shouldn't the answer be -1 ?

#include<bits/stdc++.h>  
using namespace std;  
int main()  
{  
int n,m;  
cin>>n>>m;  
int arr[n+1];  
for(int i=1;i<=n;i++)cin>>arr[i];  
int sum=m,x;  
for(int i=0;i<m;i++){cin>>x; sum+=x;}  
  
for(int i=sum;i<=n;i++)if(arr[i]){cout<<i; return 0;}  
cout<<-1;  
}
→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It was mentioned that the test cases are flawed and some wrong solutions managed to get an AC.

    → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can someone provide an explanation on why is the mentioned strategy of orienting edges in problem F optimal? i.e. why does it allow us to traverse from any vertex to any other vertex in an 'edge' connected component?

→ Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Test cases for D are very trivial. All of them pass through wrong solution also.

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

Can anyone provide proof of correctness for problem F ? I am not sure whether the solution in tutorial is correct

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain the editorial of Problem F? I can't get why the answer is the largest component!

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    For example take the following graph:

    1----2---5
|        |         8------9         12----|
|        |         |      |         |     |
3----4---6---------7------10--------11----13

    We have two bridges (6,7),(10,11). Now first without considering bridges we will direct other edges,and they will be obviously completely connected as there will be a cycle(because all the bridges already have been removed)

    Now come to bridges, if we direct 10--->11 then ri for (i=11,12,13) will be equal to 3 else if we direct 10<---11 then ri for (i=11,12,13) will be equal to 7

    So we direct edge from smaller to larger ,to get 7 over 3 Similarly we will do this with 6<---7 else (7--->6) ri for (i=7,8,9,10) will be 4 (focusing on minimum ri)

    So largest component can reach only to the vertices which come in its component after removing all bridges.If we take direct edge from higher component to lower component (higher and lower is with respect to number of vertices in component) ,then minimum can't be maximize,therefore answer will be largest component.

    Happy Coding :)

    → Reply
»
5 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

Problem D please someone Add this Test Case if possible

17 3
0 0 1 0 2 0 3 0 0 0 0 3 0 0 0 0 1
6 1 1

My Code Output
12

Actual Output
17

Still it got Accepted

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

the test cases of problem D are weak.my solution is wrong but got ac. for the test case
16 3
0 0 1 0 2 0 0 3 0 0 0 0 0 0 0 1
2 4 7
ans should be -1 but mine gives 16

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Actually we don't need to find bridges in problem F. For every edge $$$(u, v)$$$ in our DFS path, just orient it from $$$v$$$ to $$$u$$$. Refer to my submission: 117700144.

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone please explain D

→ Reply