2-sat | brain

Practice › Codeforces Solutions › Codeforces Round 936 (Div. 2) ›

CF 1946F - Nobody is needed

CF 1946F - Nobody is needed Rating: 2500 Tags: 2-sat, data structures, dfs and similar, dp Solve time: 1m 15s Verified: no Solution Problem Understanding We are given a permutation of the numbers from 1 to n. Each query gives us a segment $[l, r]$, and we are asked to count how many strictly increasing index sequences we can choose inside this segment such that every next chosen value is...

Practice › Codeforces Solutions › Codeforces Round 268 (Div. 1) ›

CF 468B - Two Sets

CF 468B - Two Sets Rating: 2000 Tags: 2-sat, dfs and similar, dsu, graph matchings, greedy Solve time: 2m 32s Verified: yes Solution Problem Understanding We are given a set of n distinct integers. Every number must be assigned to one of two groups. If a number x is placed into group A , then its complement with respect to a , namely a - x , must also be...

Practice › Codeforces Solutions ›

Codeforces Round 268 (Div. 1)

Codeforces Round 268 (Div. 1) Type: Div. 1 | Problems: 5 | Verified: 3/5 | Rating range: 1500-3100 | Time: 8m 30s Problem Name Rating Tags Solve Time Verified A 24 Game 1500 constructive-algorithms, greedy, math 1m 19s ✓ B Two Sets 2000 2-sat, dfs-and-similar, dsu 2m 32s ✓ C Hack it! 2500 binary-search, constructive-algorithms, math 1m 18s ✓ D Tree 3100 graph-matchings 1m 32s ✗ E Permanent 3100 dp,...

Practice › Codeforces Solutions › Codeforces Round 141 (Div. 2) ›

CF 228E - The Road to Berland is Paved With Good Intentions

CF 228E - The Road to Berland is Paved With Good Intentions Rating: 1900 Tags: 2-sat, dfs and similar, dsu, graphs Solve time: 1m 15s Verified: no Solution Problem Understanding We are asked to bring all roads in Berland to an asphalted state using a special operation. Each road connects two cities and has an initial state: asphalted or not. The only operation allowed is to pick a city, and...

Practice › Codeforces Solutions ›

Codeforces Round 141 (Div. 2)

Codeforces Round 141 (Div. 2) Type: Div. 2 | Problems: 4 | Verified: 2/4 | Rating range: 800-2100 | Time: 7m 21s Problem Name Rating Tags Solve Time Verified A Is your horseshoe on the other hoof? 800 implementation 2m 19s ✓ B Two Tables 1400 brute-force, implementation 2m 19s ✓ D Zigzag 2100 data-structures 1m 28s ✗ E The Road to Berland is Paved With Good Intentions 1900 2-sat,...

Practice › Codeforces Solutions › Codeforces Beta Round 27 (Codeforces format, Div. 2) ›

CF 27D - Ring Road 2