0n25's blog

By 0n25, history, 14 months 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  

»
14 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been translated by dans (original revision, translated revision, compare)

»
14 months 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.com/contest/732/submission/21550209

  • »
    »
    14 months 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?

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      No, I'm talking about the ideal situation.

      Lets say b = 6, d = 3 and s = 3. Then Vasiliy has 6 breakfasts, and the minimum number of dinners and lunches he would have had is either 5 or 6. In no situation can it be lesser. We want to find the minimum, so our answer would be (5 — 3) + (5 — 3). (Where 5 is the minimum d we could have, and 3 is the d given to us in the problem statement)

»
14 months ago, # |
Rev. 3   Vote: I like it 0 Vote: I do not like it

managed to do a-e but, i need to read tutorials on problem F , im still a bit confused, can someone explain , what is :

  • component
  • connected component
  • largest component

thanks for your help :)

»
14 months 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)?

  • »
    »
    14 months 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.

    • »
      »
      »
      14 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      ok understood it. That really made the whole question. Thanks bro.

»
13 months 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.

»
13 months 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?

  • »
    »
    13 months 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.

    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Oh no, I am very sorry. I mixed up Answer and Output.

»
13 months 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;  
}
  • »
    »
    13 months 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.

»
12 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Why is complexity for Problem D O(mlogn)? For each guess, we want to take the subject at the latest possible day right? So we will need to perform a linear scan on the exam days so that we can find the latest day for each subject. So that should be O(nlogn) right? Is anyone able to confirm this?

»
11 months 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?

»
3 months 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.

»
3 months 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