11

Editorial of CodeTON Round 4 (Div. 1 + Div. 2, Rated, Prizes!)

 1 year ago
source link: http://codeforces.com/blog/entry/114521
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
By RDDCCD, history, 34 hours ago, In English

A. Beautiful Sequence

Hint
Tutorial
Solution

B. Candies

Hint
Tutorial
Solution

C.Make It Permutation

Hint 1
Hint 2
Tutorial
Solution

D.Climbing the Tree

Hint
Tutorial
Solution

E.Monsters

Hint 1
Hint 2
Tutorial
Solution

F.M-tree

Hint 1
Hint 2
Tutorial
Solution

G. The Maximum Prefix

Hint
Tutorial
Solution

H will coming soon.

6 hours ago, # |

Wow. Tutorial was released even before system testing was over. Nice contest overall <3

6 hours ago, # |

super fast editorial. Thanks!

6 hours ago, # |

well prepared !

  • 6 hours ago, # ^ |

    it is possible without dp also link

6 hours ago, # |

Wow! . Very Fast . Excellent Contest . Jiangly is new No. 1 :)

6 hours ago, # |

OMG!Jiangly rk 1!

  • 4 hours ago, # ^ |

    Yeah! He might cross 4000 soon

6 hours ago, # |

Jiangly is very cool

6 hours ago, # |

← Rev. 2 →  

+15

Problem F is basically a generalization of 1705E - Mark and Professor Koro. I described a segment tree-free solution here that can easily be generalized to this problem.

6 hours ago, # |

← Rev. 2 →  

0

Can someone please help me with problem C My approach was to find the upper bound for each value and calculating values required to be removed and added using it Code

  • 5 hours ago, # ^ |

    work with lower bound

    • 5 hours ago, # ^ |

      Could you please help me with a tc where this might fail. Or why does this fail.Thank you for your time

  • 5 hours ago, # ^ | 

    1
2 813259240 924953903
21 100

run this....

    • 4 hours ago, # ^ |

      Thank you so much bro. I multiplied insert twice :((

6 hours ago, # |

Well prepared for the contest .

6 hours ago, # |

← Rev. 2 →  

0

can anyone tell my which testcase my code is failing in problem c Code...

6 hours ago, # |

Nice problems and fast editorial.

6 hours ago, # |

In problem E, how do they come to conclusion that |S(u′)|>2|S(u)|?

  • 6 hours ago, # ^ |

    If can reach any vertex in then it can reach all vertices in . Before reaching , and after visiting all of ,

6 hours ago, # |

In problem B, "Then consider how the binary representation changes..." — I mean, all of a sudden people have to consider binary representation of a number? :) I find this kind of problem a bit weird. I know that the idea and solution is nice and neat but when you solve it you kind of expect more general approaches to work here like backtracking or some easy calculations but this kind of reasoning seem to be not suitable for problem B. I solved it exactly the way it is described in the solution, but it was just kind of a luck.

  • 6 hours ago, # ^ |

    When is odd, either one of or is odd. You can perform the operation that makes remain in odd, eventually will end at .

    • 5 hours ago, # ^ |

      yeah, that's how I did it too

    • 5 hours ago, # ^ |

      Oh, you mean (n+1)/2 or (n−1)/2 is literally the recursive binary representation of a number :)

6 hours ago, # |

is there any reason as to why we do not consider the 40 spell limit in the 2nd question?

  • 5 hours ago, # ^ |

    ← Rev. 2 →  

    0

    Each operation you might want to do increases the number of significant bits in the number's binary representation. As the maximum value of we might want is which has only bits, we would need at most operations (+/-1 if my logic has some off-by-one error) which is clearly less than .

5 hours ago, # |

← Rev. 6 →  

-35

Cheers to authors. Overall Great round. I wanted to share my opinion on problem D.

Problem D is the little bit bad for C++ users compared to python.

There is a formula to find number of days require to reach height 'h'.

But instead of using formula, if we use BINARY SEARCH , then there is very stupid long long overflow.

Sincere request to authors to avoid these kind of problems which are language specific. In this problem, using binary search in c++ is 10x more difficult than using python. RDDCCD

Below is my implementation in c++, EVEN AFTER USING LONG LONG, I am getting overflow. is there any way to overcome this ? 


// "ll" stands for long long 
ll getDays(ll h, ll a , ll b) { // returns minimum number of days required to reach height 'h'
    ll l = 1LL , r = h;
    while(l < r) {
        ll m = (l+r)/2LL;
        ll climb = (m-1LL) * (a-b) + a; // this line gets overflow 
        if(climb >= h) {
            r = m;
        } else {
            l = m+1LL;
        }
    }
    return l;
}

  • 5 hours ago, # ^ |

    One possible way is to set I think. Or using int128. You can also detect whether overflow occurs, like checking (climb > (8e18/(a-b)). If it occurs, just set r = m.

    • 5 hours ago, # ^ |

      sure, thanks, will give it try.

      • 3 hours ago, # ^ |

        Yes , I also got the same signed integer overflow and int128 doesn't work in c++17 so , r=h/(a-b)+1 works fine.

  • 5 hours ago, # ^ |

    ← Rev. 2 →  

    0

    There exists 128-bit integer in C++ which is big enough since you aren't crossing ~ and 128-bit integer can hold numbers up to ~.

  • 5 hours ago, # ^ |

    ← Rev. 2 →  

    0

    You can also use the thing I used to get AC : 200027884. This prevents overflow. I got this idea from ' binary search — edu section ' of codeforces.

    code

5 hours ago, # |

Great round, thank you problemsetters!

5 hours ago, # |

The proof of the time complexity of E is quite an impressive part of this problem. I like it very much. (I came up with this solution in the last 20 minutes, but I thought that was and lost the chance for a nice rating change. T_T)

ABCD are a little too easy, considering the difficulty difference between D and E. I was somehow slower on ABCD than usual, and then my rank fell down a lot.

Anyway, a nice contest. Really enjoyed it.

5 hours ago, # |

← Rev. 2 →  

0

200033270 I am getting the wrong answer in test case 7. I think there is some overflow error, but I cannot get it. I am using long long everywhere still. It will be helpful if somebody can find out what I am doing wrong. Thanks in advance.

5 hours ago, # |

← Rev. 2 →  

+12

Today's Codeforces contest crossed the mark of 200 million submissions, what a coincidence! Congratulations!

  • 5 hours ago, # ^ |

    May be 200 million submissions?

3 hours ago, # |

In problem D, the tutorial and the solution use different formulas to compute n, given h, a and b. When I tried, the tutorial formula gives Wrong Answer on Test Case 7 or something. Can someone please help me understand how to arrive at the formula given in the solution code? Also, please confirm if the tutorial formula is wrong. Thanks in advance :)

111 minutes ago, # |

Can someone tell me what is wrong with the code for problem E? Am i missing something? I am getting WA on TC 3

C++ CODE

ll n, m, x, y; 
vll dgr; 
vector<vll> adj;
bool modBFS(ll st){
    unordered_map<ll,ll,custom_hash> ump;
    priority_queue<pll,vector<pll>,greater<pll>> pq;// damage, node 
    pq.push({0,st});ll hlt = 0;
    while(!pq.empty()){
        ll dmg = pq.top().first, node = pq.top().second;
        ump[node]=1; pq.pop();
        if(dmg>hlt) return false; else hlt++;
        for(auto it: adj[node]) 
            if(!ump.count(it)) pq.push({dgr[it],it});
    }
    return sz(ump)==n;
}
int solve() {
    cin>>n>>m; dgr=vll(n); adj=vector<vll>(n); cin>>dgr; 
    while(m--){
        cin>>x>>y; x--,y--;
        adj[x].pb(y); adj[y].pb(x);
    }
    rep(i,0,n){
        if(!dgr[i] and modBFS(i)) {yes; return 0;}
    }
    no;
    return 0;
}

21 minute(s) ago, # |

← Rev. 3 →  

0

Problem B is exactly the same as problem D from yesterday's Constructor University contest.

D. Mana

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK