Blog entries - Codeforces

send_nodes's blog

Codeforces Round #420 (Div. 2) Editorial

By send_nodes, history, 7 years ago, In English

First, I really need to apologize for the round. There was a serious problem in D that was even covered in the sample test, that the main solution did not handle correctly. I should have been much more careful with this problem and looked for these kind of cases. Unfortunately, it was a big enough issue that caused the round to be unrated. I know this upset a lot of people, but it's tricky to find a solution to this kind of problem after the problem has happened.

I still hope the problems were good quality. If you learned something new from the round, or from this editorial, then the round was worth it. I would advise to solve the problems you couldn't solve during the contest, so you can take away something from the round.

If you want any further clarification on a problem, please ask in comments!

821A — Okabe and Future Gadget Laboratory

We can simulate exactly what's described in the statement: loop over all cells not equal to 1 and check if it doesn't break the city property. To check if a cell breaks the property, just loop over an element in the same row, and an element in the same column, and see if they can add to give the cell's number. The complexity is O(n⁴).

Sidenote: The definition of lab here was actually inspired from a USAMTS problem in 2016.

Code

#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <complex>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
using namespace std;
//macros
typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;




#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define INF 999999999
#define INFLONG 1000000000000000000LL
#define MOD 1000000007
#define MAX 100
#define ITERS 100
#define pi 3.1415926
#define MAXN 100000
#define _gcd __gcd

int main()
{
    int n;
    cin >> n;
    int grid[50][50];
    REP(i,n){
        REP(j,n){
            cin >> grid[i][j];
        }
    }
    REP(i,n){
        REP(j,n){
            if(grid[i][j]==1) continue;
            bool pass = false;
            for(int r = 0;r<n;r++){
                if(r==i) continue;
                for(int c = 0; c < n; c++){
                    if(c==j) continue;
                    int sum = grid[r][j]+grid[i][c];
                    if(sum==grid[i][j]){
                        pass=true;
                        break;
                    }
                }
                if(pass)break;
            }
            if(!pass){
                cout << "No"<<endl;
                return 0;
            }
        }
    }
    cout << "Yes"<<endl;
}

821B — Okabe and Banana Trees

The critical observation to make is that the optimal rectangle should always have a lower-left vertex at the origin. This is due to the fact that the line has positive y-intercept and negative slope: any rectangle which doesn't have a vertex at the origin could easily be extended to have a vertex at the origin and even more bananas.

Then, we just need to try every x-coordinate for the upper-right corner of the box and pick the maximum y-coordinate without going over the line. We can compute the sum of any rectangle in O(1) using arithmetic series sums, so this becomes O(bm) because the x-intercept can be up to bm. You can make it faster by trying every y-coordinate; this makes the complexity O(b), but this was unnecessary to solve the problem.

$\text{[math]}$ Can you solve the problem with better complexity?

O(b) Code


#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <complex>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
using namespace std;

//macros
typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;




#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define INF 999999999
#define INFLONG 1000000000000000000
#define MOD 1000000007
#define MAX 100
#define ITERS 100
#define MAXM 200000
#define MAXN 1000000
#define _gcd __gcd
#define eps 1e-9
ll series(ll x){
	return x*(x+1)/2;
}
int main() {
	int m,b;
	cin >> m >> b;
	ll best = 0;
	for(int y = b; y >=0; y--){
		//y = -x/m + b
		ll x = m*(b-y);
		ll t = 0;
		t+=(x+1)*series(y)+(y+1)*series(x);
		best = max(best,t);
	}
	cout << best << endl;
}

821C — Okabe and Boxes

It looks like Daru should only reorder the boxes when he has to (i.e. he gets a remove operation on a number which isn't at the top of the stack). The proof is simple: reordering when Daru has more boxes is always not worse than reordering when he has less boxes, because Daru can sort more boxes into the optimal arrangement. Therefore, our greedy algorithm is as follows: simulate all the steps until we need to reorder, and then we resort the stack in ascending order from top to bottom.

This has complexity O(n² log n). However, we can speed this up if we note that whenever we reorder boxes, any box currently on the stack can be put in an optimal position and we can pretty much forget about it. So whenever we reorder, we can just clear the stack as well and continue. This gives us O(n) complexity because every element is added and removed exactly once.

Code

#include <vector>
#include <utility>
#include <iostream>
#include <cassert>
#include <map>
#include <climits>
#include <deque>
#include <algorithm>
#include <set>
#include <stack>
using namespace std;

#define ll long long
#define REP(i,a) for(int i = 0; i < (a); i++)
#define PB push_back
#define SZ(a) (a).size()
#define MP make_pair
#define ALL(a) (a).begin(),(a).end()
#define fs first
typedef vector<int> vi;
typedef pair<int,int> pii;



int main()
{
    int n;
    cin >> n;
    stack<int> st;
    int curr=1;
    int ans = 0;
    REP(i,2*n){
        string str;
        cin >> str;
        assert(str[0]=='a' || str[0]=='r');
        if(str[0]=='a'){
            int x;
            cin >> x;
            st.push(x);
        }else if(str[0]=='r'){
            if(!st.empty()){
                if(st.top()==curr){ //last thing added is what we need to remove
                    st.pop();
                }else{ //last thing we added is NOT what we need to remove
                    ans++;
                    while(!st.empty()) st.pop(); //clears the stack
                }
            }
            curr++;
        }
    }
    cout << ans << endl;
}

821D — Okabe and City

First, let's make this problem into one on a graph. The important piece of information is the row and column we're on, so we'll create a node like this for every lit cell in the grid. Edges in the graph are 0 between 2 nodes if we can reach the other immediately, or 1 if we can light a row/column to get to it. Now it's a shortest path problem: we need to start from a given node, and with minimum distance, reach another node.

Only problem is, number of edges can be large, causing the algorithm to time out. There are a lot of options here to reduce number of transitions. The most elegant one I found is Benq's solution, which I'll describe here. From a given cell, you can visit any adjacent lit cells. In addition, you can visit any lit cell with difference in rows at most 2, and any lit cell with difference in columns at most 2. So from the cell (r,c), you can just loop over all those cells.

The only tricky part is asking whether the current lit row/column should be a part of our BFS state. Since we fill the entire row/col and can then visit anything on that row/col, it doesn't matter where we came from. This means that you can temporarily light each row/column at most once during the entire BFS search.

So complexity is O(n + m + k), with a log factor somewhere for map or priority queue. Interestingly enough, you can remove the priority queue log factor because the BFS is with weights 0 and 1 only, but it performs slower in practice.

You can see the code implementing this approach below.

Benq's code:

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

using namespace std;
//using namespace __gnu_pbds;
 
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
//typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) for (int i=0; i<a; i++)
#define FORd(i,a,b) for (int i = (b)-1; i >= a; i--)
#define F0Rd(i,a) for (int i = (a)-1; i >= 0; i--)
 
#define mp make_pair
#define pb push_back
#define f first
#define s second
#define lb lower_bound
#define ub upper_bound

const int MOD = 1000000007;
double PI = 4*atan(1);

int dr[10001], dc[10001];
vi row[10001], col[10001];
priority_queue<pii> todo;
vector<pii> lights;
int dist[10001];
map<pii,int> label;
int xdir[4] = {1,0,-1,0}, ydir[4] = {0,1,0,-1};
int n,m,k; 

void filrow(int i, int val){
    if (i >= 1 && i <= n && dr[i] == 0) {
        dr[i] = 1;
        for (int x: row[i]) if (val < dist[x]) {
            dist[x] = val;
            todo.push({-dist[x],x});
        }
    }
}

void filcol(int i, int val) {
    if (i >= 1 && i <= m && dc[i] == 0) {
        dc[i] = 1;
        for (int x: col[i]) if (val < dist[x]) {
            dist[x] = val;
            todo.push({-dist[x],x});
        }
    }
}

void ad(int x, int y, int val) {
    if (label.find({x,y}) != label.end()) 
        if (dist[label[{x,y}]] > val) {
            dist[label[{x,y}]] = val;
            todo.push({-val,label[{x,y}]});
        }
}

int main() {
    cin >> n >> m >> k;
    
    F0R(i,k) {
        int r,c; cin >> r >> c;
        lights.pb({r,c});
        row[r].pb(i);
        col[c].pb(i);
        label[{r,c}] = i;
    }
    
    F0R(i,10001) dist[i] = MOD;
    
    if (label.find({n,m}) == label.end()) {
        filrow(n-1,1);
        filrow(n,1);
        filcol(m-1,1);
        filcol(m,1);
    } else todo.push({0,label[{n,m}]});
    
    
    while (todo.size()) {
        auto a = todo.top(); todo.pop();
        a.f = -a.f;
        if (a.f > dist[a.s]) continue;
        
        F0R(i,4) ad(lights[a.s].f+xdir[i],lights[a.s].s+ydir[i],a.f);
        FOR(i,lights[a.s].f-2,lights[a.s].f+3) filrow(i,a.f+1);
        FOR(i,lights[a.s].s-2,lights[a.s].s+3) filcol(i,a.f+1);
    }
    
    if (dist[0] != MOD) cout << dist[0];
    else cout << -1;
}

Another approach to this problem was using "virtual nodes". Virtual nodes are an easy way to put transitions between related states while keeping number of edges low. In this problem, we can travel to any lit cell if its row differs by <=2, or its column differs by at most 2, but naively adding edges would cause O(k^2) edges.

Instead, for every row, lets make a virtual node. For every lit cell in this row, put an edge between the lit cell and this virtual node with cost 1. We can do something similar for every column.

Now, it's easy to see that the shortest path in this graph suffices. A minor detail is that we should divide the answer by 2 since every skipping of a row or column ends up costing 2 units of cost.

821E — Okabe and El Psy Kongroo

You can get a naive DP solution by computing f(x, y), the number of ways to reach the point (x, y). It's just f(x - 1, y + 1) + f(x - 1, y) + f(x - 1, y - 1), being careful about staying above x axis and under or on any segments.

To speed it up, note that the transitions are independent of x. This is screaming matrix multiplication! First, if you don't know the matrix exponentiation technique for speeding up DP, you should learn it from here.

Now, let's think of the matrix representation. Since the x dimension is the long one and the y dimension is small, lets store a vector of values dp where dp_i is the number of ways to get to a y value of i at the current x value. This will be the initial vector for matrix multiplication.

Now, what about the transition matrix? Since our initial vector has length y and we need a matrix to multiply it with to map it to another vector with length y, we need a y by y matrix. Now, if you think about how matrix multiplication works, you come up with an idea like this: put a 1 in the entry (i,j) if from a y value of i we can reach a y value of j (i.e. |i - j| ≤ 1). Don't believe me, multiply some vector times a matrix of this form to see how and why the transition works.

You can then build this matrix quickly and then matrix exponentiate for under every segment and multiply by the initial vector, then make the result as the new initial vector for the next segment. You should make sure to remove values from the vector if the next segment is lower, or add values to the vector if the next segment is higher. This gives complexity O(nh³ log w) where h = 16 and w = k.

Code

#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <complex>
#include <fstream>
#include <cstring>
#include <string>
#include <climits>
#include <chrono>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <assert.h>
using namespace std;

//macros
typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;




#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define INF 1000000001
#define INFLONG 1000000000000000000
#define MOD 1000000007
#define MAX 100
#define ITERS 100
#define MAXM 200000
#define MAXN 1000000
#define _gcd __gcd
#define EPS 1e-7
#define PI 3.1415926535897932384626
#define ERR -987654321

//multiplies m1 and m2 and stores in m3
vector<vector<long long> > matmul(vector<vector<long long> > m1, vector<vector<long long> > m2, vector<vector<long long> > &m3){
    m3.clear();
    vector<vector<long long> > ans;
    REP(i,SZ(m1)){
        vector<long long> v;

        REP(j,SZ(m2[0])){
            v.PB(0);
        }
        ans.PB(v);
    }

    REP(r,SZ(m1)){
        REP(c,SZ(m2[0])){
            REP(k, SZ(m2)){
                ans[r][c] += m1[r][k]*m2[k][c];
                ans[r][c]%=MOD;
            }
        }
    }

    REP(i,SZ(m1)){
        vector<long long> cur;
        REP(j,SZ(m2[0])){
            cur.PB(ans[i][j]);
        }
        m3.PB(cur);
    }
    return m3;


}
vector<ll> mymul(vector<ll> vec, vector<vector<ll> > mat, vector<ll> &ret){
    vector<ll> res;
    REP(i,SZ(vec)){
        ll sum = 0;
        for(int co = 0; co < SZ(mat); co++){
            sum += vec[co]*mat[co][i];
            sum%=MOD;
        }
        res.PB(sum);
    }
    ret.clear();
    REP(i,SZ(res)) ret.PB(res[i]);
    return ret;
}
void printmat(vector<vector<long long> > matr){
    REP(i,SZ(matr)){
        REP(j,SZ(matr[i])){
            cout << matr[i][j] << " " ;
        }
        cout << endl;
    }
}
vector<vector<long long> > matexp(vector<vector<long long> > matr, long long n){
    vector<vector<long long> > ans;
    REP(i,SZ(matr)){
        vector<long long> v;
        REP(j,SZ(matr[0])){
            v.PB((i==j));
        }
        ans.PB(v);
    }
    long long t = n;

    while(t>0){

        if(t%2==0){
            matmul(matr,matr,matr);
            t/=2;
        }
        else{
            matmul(ans,matr,ans);
            t--;
        }
    }

    return ans;
}

int main()
{
    int n;
    ll k;
    cin >> n >> k;
    vector<ll> a1,a2,b;
    REP(i,n){
        ll a1r, a2r, br;
        cin >> a1r >> a2r >> br;
        a1.PB(a1r);
        a2.PB(a2r);
        b.PB(br);
    }
    vector<ll> ans;
    ans.PB(1);
    a2[SZ(a2)-1] = k;
    REP(i,n){
        //update ans size
        while(SZ(ans) < b[i]+1) ans.PB(0);
        while(SZ(ans) > b[i]+1) ans.erase(prev(ans.end()));
        vector<vector<ll> > trans;
        int len = b[i]+1;
        REP(pr,len){
            vector<ll> lol;
            REP(pro,len){
                lol.PB(0);
            }
            trans.PB(lol);
        }
        REP(co,len){
            if(co>0) trans[co-1][co] = 1;
            trans[co][co] = 1;
            if(co+1<len) trans[co+1][co] = 1;
        }
        mymul(ans,matexp(trans,a2[i]-a1[i]),ans);
    }
    cout << ans[0] << endl;
}

Full text and comments »

Tutorial of Codeforces Round 420 (Div. 2)

+127

send_nodes
7 years ago
160

Codeforces Round #420 (Div. 2)

By send_nodes, history, 7 years ago, In English

Hi everyone!

It's the round you've been waiting for... Codeforces Round #420 (Div 2). It will take place tomorrow, 25 June 2017, at 17:35 MSK. As always, Div. 1 participants are encouraged to join out of competition. The round will be rated for Div. 2 participants and will have 5 problems to be completed in 2 hours.

I wouldn't be able to create this round without the help of many people: KAN for lots of help in preparing the contest, 300iq and Alladdin for testing and providing feedback, and as always MikeMirzayanov for the Codeforces and Polygon platforms.

This will be my second contest, and I'm glad to get such a nice round number :). Hopefully, you'll find the problems interesting. Of course, you should read all the problems so you can solve problems you find easy or interesting.

To excite some and disappoint others, the round theme will have nothing to do with the number 420. Instead, continuing the anime themes of the last two rounds, round #420 will feature mad scientist Rintaro Okabe (don't read spoilers!) from the anime Steins;Gate. Statements will not contain any spoilers, but you might find the problems slightly more amusing if you've watched the series. Of course, you should watch the series if you havent :)!

As per Codeforces tradition, scoring distribution will be announced shortly before the contest. Good luck, and I hope you can help Okabe with all 5 tasks :D!

Scoring is standard: 500-1000-1500-2000-2500!

Update: Sorry for delays.

Update: Editorial is here: http://codeforces.com/blog/entry/52895

I really apologize for the issues during the round. It's upset a lot of people and I should have taken more care. Hopefully you won't hold this against Okabe or Steins;Gate anime :P

Here are the contest winners! Congratulations!

Div. 1

Div. 2

Thanks for participation everyone! Hope to write more problems in the future (without bugs)!

Full text and comments »

Announcement of Codeforces Round 420 (Div. 2)

+104

send_nodes
7 years ago
284

Ticket Exchange Problem

By send_nodes, history, 7 years ago, In English

Hi community,

I've been thinking about some problem for a while, and was wondering if it has a polynomial time solution. The problem goes as follows:

You character starts with B blue tickets and R red tickets. There are N offers proposed to you, the i'th in which you first lose a_i blue tickets, b_i red tickets, and then right afterwards gain c_i blue tickets and d_i red tickets (Suppose all values except N are ≤ 10⁹). You lose if you ever have a negative amount of either ticket type. Is it possible to complete all offers and not lose?

Obviously you first want to complete all offers that yield positive profit for both red and blue tickets, but even then there might be some offers you can't complete. The rest is not so trivial.

Does anyone have ideas or seen this problem before? As said, this is original, so I don't have a problem link and am simply looking for the best time complexity possible.

Full text and comments »

send_nodes
7 years ago
4

Codeforces Round #370 Editorial

By send_nodes, history, 8 years ago, In English

Hi everyone, here are the solutions to the contest problems.

712A — Memory and Crow

Note that a[i] + a[i + 1] = b[i]. Use the initial condition b[n] = a[n] and we can figure out the entire array b.

Time Complexity: O(n)

Code

#include <bits/stdc++.h>

using namespace std;

int arr[100000];
int ans[100000];
int main()
{
    int n;
    cin >> n;
    for(int i=0; i < n; i++){
        cin >> arr[i];

    }

    for(int i = n-1; i >=0; i--){
        if(i==n-1) ans[i] = arr[i];
        else ans[i] = arr[i] + arr[i+1];
    }
    for(int i=0; i < n; i++){
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

712B — Memory and Trident

First, if S has odd length, there is no possible string because letters must come in opposite pairs. Now, let's denote the ending coordinate after following S as (x, y). Since S has even length, |x| has the same parity as |y|. Suppose they are both even. Then clearly, we can make x = 0 in exactly $\text{[math]}$ moves, and same for y. If instead they are both odd, then we can change exactly one x-character into a y-character. With the correct choices of these characters, now our string has |x| and |y| with even parity, thus reducing to the problem above. Therefore, the answer is (|x| + |y|) / 2.

Time Complexity: O(|S|)

Code

#include <string>
#include <iostream>
#include <stdlib.h>
using namespace std;


int main()
{
    string str;
    cin >> str;
    if(str.length()%2==1){
        cout << -1 << endl;
        return 0;
    }

    int x=0,y=0;
    for(int i=0; i < str.length(); i++){
        if(str[i]=='U')y++;
        if(str[i]=='D')y--;
        if(str[i]=='L')x--;
        if(str[i]=='R')x++;
    }
    cout << (abs(x)+abs(y))/2 << endl;
}

712C — Memory and De-Evolution

Let's reverse the process: start with an equilateral triangle with side length y, and lets get to an equilateral triangle with side length x. In each step, we can act greedily while obeying the triangle inequality. This will give us our desired answer.

Time Complexity: O(log x)

Code

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int x,y;
    cin >> x >> y;

    int besta=y,bestb=y,bestc=y;

    int turns = 0;
    while(true){
        //check the current
        if(besta>=x && bestb>=x && bestc>=x){
            cout << turns << endl;
            break;
        }
        turns++;
        if(turns%3==1){
            //update a
            besta = bestb+bestc-1;
        }
        if(turns%3==2){
            //update b
            bestb = besta+bestc-1;
        }
        if(turns%3==0){
            //update c
            bestc = besta+bestb-1;
        }
    }
    return 0;
}

712D — Memory and Scores

One approach to this problem is by first implementing naive DP in O((kt)²). The state for this is (diff, turn), and transitions for (diff, turn) is the sum (diff - 2k, turn - 1) + 2(diff - 2k + 1, turn - 1) + 3(diff - 2k + 2, turn - 1) + ... + (2k + 1)(diff, turn - 1) + 2k(diff + 1, turn - 1) + ... + diff( + 2k, turn - 1).

Now, if we use prefix sums of all differences in (turn-1), along with a sliding window technique across the differences, we can cut a factor of k, to achieve desired complexity O(kt²).

However, there is a much nicer solution in O(kt log kt) using generating functions(thanks to minimario). We can compute the coefficients of $\text{[math]}$ , and the coefficient to xⁱ corresponds to the number of ways we can form the difference i. To compute these coefficients, we can use the binomial theorem.

Time Complexity: O(kt²)

Code


#include <bits\stdc++.h>
using namespace std;

int MOD = 1000000007;
long long dp[2][1000000];
int lowest;

int h(int v){
    return v - lowest;
}
int main()
{
    int a,b,k,t;
    cin >> a >> b >> k >> t;
    int lowb = a-b;
    int highb = a-b;

    lowest = lowb - 2*k*(t);
    dp[0][h(lowb)] = 1l;
    //solve for ti = 0
    int curr = 1;
    for(int p = lowb-2*k; p<= lowb; p++){
        dp[1][h(p)] = curr;
        curr++;
    }
    curr--;
    for(int p = lowb+1; p<= lowb+2*k; p++){
        curr--;
        dp[1][h(p)] = curr;
    }
    lowb -=2*k;
    highb+=2*k;
    for(int ti = 1; ti <= t-1; ti++){
        int o = ti%2;
        vector<long long> pref;
        pref.push_back(dp[o][h(lowb)]);
        long long su = dp[o][h(lowb)];
        for(int p = lowb+1; p <= highb; p++){
            su = (su+dp[o][h(p)])%MOD;
            pref.push_back(su);
        }
        int pe = 2*k;
        int il = 0;
        int ir = 0;
        int l = lowb;
        int r = lowb;
        int np = lowb-2*k;
        long long sum = 0;
        //get the prefix first

        while(ir<=2*k){
            //evaluate current
            sum = (sum + pref[ir])%MOD;
            dp[!o][h(np)] = sum;
            //update for the next thing
            ir++;
            r++;
            np++;
        }
        pe = 0;
        ir--;
        r--;
        np--;
        while(pe<2*k){
            pe++;
            ir++;
            r++;
            np++;
            //evaluate
            sum = (sum + pref[ir])%MOD;
            sum = (sum - 2*pref[pe-1])%MOD;
            sum = (sum+MOD)%MOD;
            dp[!o][h(np)] = sum;
        }

        //slide into those dm's
        while(r<highb){
            //update
            pe++;
            r++;
            l++;
            ir++;
            il++;
            np++;

            long long sum1 = pref[pe-1] - ( (il==1) ? 0 : pref[(il-1)-1]);
            long long sum2 = pref[ir] - pref[pe-1];
            sum = (sum - sum1 + MOD)%MOD;
            sum = (sum + sum2)%MOD;
            dp[!o][h(np)] = sum;
        }
        //finally, suffix
        while(l<highb){
            l++;
            il++;
            pe++;
            np++;
            //subtract [l-1,pe-1]
            long long sum1 = pref[min(pe-1,ir)] - ((il==1) ? 0 : pref[il-1-1]);
            sum = (sum - sum1 + MOD)%MOD;
            if(pe>ir){

            }
            else{
                long long sum2 = pref[ir]-pref[pe-1];
                sum = (sum + sum2)%MOD;
            }
            dp[!o][h(np)] = sum;
        }

        lowb-=2*k;
        highb+=2*k;
    }
    long long ans = 0;
    int o = t%2;
    for(int p = 1; p <= highb; p++){
        ans = (ans+dp[o][h(p)])%MOD;
    }
    cout << ans << endl;
}

Time Complexity: O(kt log kt)

Code

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

#define f first
#define s second
#define pb push_back
#define mp make_pair

#define FOR(i, a, b) for (int i=a; i<b; i++)
#define F0R(i, a) FOR(i, 0, a)

const int MAX = 1000005;
const int MOD = 1000000007;

int f[MAX];
int fi[MAX];

int pos(int a) { return ((ll)a%MOD+MOD)%MOD; }
int add(int a, int b) { return ((ll)a+(ll)b)%MOD; }
int sub(int a, int b) { return pos(a-b); }
int mult(int a, int b) { return (ll)pos(a)*b%MOD; }
int sq(int a) { return (ll)a*a%MOD; }

int expo(int a, int b) {
    if (b == 0) { return 1; }
    if (b%2) { return mult(a, sq(expo(a, b/2))); }
    else { return sq(expo(a, b/2)); }
}
int inv(int a) { return expo(a, MOD-2); }

int c(int n, int k) {
    return mult(f[n], mult(fi[k], fi[n-k]));
}

int poly1[MAX];
int pref2[MAX];
int main() {
    f[0] = fi[0] = 1;
    FOR(i, 1, MAX) { f[i] = mult(f[i-1], i); fi[i] = inv(f[i]); }
    int a, b, k, t;
    cin >> a >> b >> k >> t;
    if(b-a > 2*k*t){
    	cout << 0 << endl;
    	return 0;
    }
    F0R(i, 2*t+1) { poly1[(2*k+1)*i] = ((i%2==0)?1:-1)*c(2*t, i); }
    F0R(i, MAX) { pref2[i] = c(2*t-1+i+1, 2*t); }
    int lb = 2*k*t+b-a+1;
    int ub = 4*k*t;
    int ans = 0;
    F0R(i, 2*t+1) {
        int l = lb-(2*k+1)*i;
        int u = ub-(2*k+1)*i;
        if (u < 0) { break; }
        if (l < 0) { ans = add(ans, mult(poly1[(2*k+1)*i], pref2[u])); }
        else { ans = add(ans, mult(poly1[(2*k+1)*i], sub(pref2[u], pref2[l-1]))); }
    }
    cout << ans << endl;
}

712E — Memory and Casinos

Lets think about two segments of casinos [i, j] and [j + 1, n]. Let L([a, b]) denote the probability we dominate on [a, b], and let R([a, b]) denote the probability we start on b and end by moving right of b. Let

l₁ = L([i, j]),

l₂ = L([j + 1, n]),

r₁ = R([i, j]),

r₂ = R([j + 1, n]).

You can use a geometric series to figure out both L([i, n]) and R([i, n]) using only l₁,l₂,r₁, and r₂. To derive these series, think about the probability we cross over from j to j + 1 once, twice, three times, and so on. The actual formulas are,

$\text{[math]}$

Now we can build a segment tree on the casinos, and use the above to merge segments.

Time Complexity: O(N + QlogN)

Code

#include <bits/stdc++.h>
using namespace std;


int n;
double pr[100000];
pair<double,double> seg[400000];
bool ze(double d){
	return (abs(d) <= 0.0000000001);
}
pair<double,double> merge(pair<double,double> a, pair<double,double> b){
	if(ze(a.first+1) && ze(a.second+1)) return b;
	if(ze(b.first+1) && ze(b.second+1)) return a;
	double l1 = a.first;
	double r1 = a.second;
	double l2 = b.first;
	double r2 = b.second;
	if(ze(((l2-1)*r1+1))) return make_pair(0,0);
	double le = l1*l2/((l2-1)*r1+1);
	double ri = r2+(r1*l2*(-r2+1))/(-r1*(-l2+1)+1);
	return make_pair(le,ri);
}
void build(int no, int b, int e){
	if(b==e){
		seg[no] = make_pair(pr[b],pr[b]);
		return;
	}
	int mid = (b+e)/2;
	build(2*no,b,mid);
	build(2*no+1,mid+1,e);
	seg[no] = merge(seg[2*no],seg[2*no+1]);
}
void upd(int no, int b, int e, int i, double val){
	if(i<b || i>e) return;
	if(b==e){
		seg[no] = make_pair(val,val);
		return;
	}
	int mid = (b+e)/2;
	upd(2*no,b,mid,i,val);
	upd(2*no+1,mid+1,e,i,val);
	seg[no] = merge(seg[2*no],seg[2*no+1]);
}
pair<double,double> query(int no, int b, int e, int l, int r){
	if(b>r || e<l) return make_pair(-1,-1);
	if(l<=b && e<=r) return seg[no];
	int mid = (b+e)/2;
	return merge(query(2*no,b,mid,l,r),query(2*no+1,mid+1,e,l,r));
}
int main(){
    int q;
	scanf("%d %d", &n, &q);
	for(int i=0; i < n; i++){
		int a,b;
		scanf("%d %d", &a, &b);
		pr[i] = (double)a / (double)b;
	}
	
	build(1,0,n-1);
	for(int que = 0; que < q; que++){
		int ty;
		int a;
		int b;
		scanf("%d %d %d", &ty, &a, &b);
		if(ty==1){
			int c;
			scanf("%d", &c);
			upd(1,0,n-1,a-1, (double)b / (double)c);
		}
		else{
		    printf("%.20f\n", query(1,0,n-1,a-1,b-1).first);
		}
	}
	
	return 0;
}

Full text and comments »

Tutorial of Codeforces Round 370 (Div. 2)

send_nodes
8 years ago
88

Codeforces Round #370 (Div. 2)

By send_nodes, history, 8 years ago, In English

Hi everyone. I'm trashfirstsearch, and I used to be blue...

Anyways, Codeforces Round #370 (Div. 2) will take place on 10 September 2016 at 19:35 MSK. As usual, Div.1 participants can join out of competition.

Much thanks to GlebsHP for helping me with preparing the contest, MikeMirzayanov for the Codeforces and Polygon platforms, and minimario and Wrong_Answer_Exceeded for testing problems.

This will be my first contest prepared on Codeforces, and I have prepared all the problems with the intent of making them interesting for everyone. It is, as usual, strongly advised to read all the problems.

Good luck, and I hope you will gain rating(and force someone else to lose it >:) ).

Update: Congratulations to the winners:

Div.1

Div.2

Here is the editorial.

I sincerely apologize for the problems during the contest. However, I hope everyone found the problems interesting! Thanks to everyone who participated and helped with the problems!

Full text and comments »

Announcement of Codeforces Round 370 (Div. 2)

+264

send_nodes
8 years ago
145

Code(C++) crashing when allocating 2-D arrays

By send_nodes, history, 9 years ago, In English

I've been having a problem with 2-D arrays for a while. If I allocate a 2-D array with dimensions 1000x1000, then when I debug, the program crashes. For example, this code is crashing:

#include <queue>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <complex>
#include <fstream>
#include <cstring>
#include <string>

using namespace std;

//macros
typedef long long ll;
typedef complex<double> point;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector< vector<int> > vvi;




#define FOR(k,a,b) for(int k=(a); k<=(b); ++k)
#define REP(k,a) for(int k=0; k<(a);++k)
#define SZ(a) int((a).size())
#define ALL(c) (c).begin(),(c).end()
#define PB push_back
#define MP make_pair
#define INF 99999999
#define MOD 1000000007
#define MAX 100000
#define ITERS 10000
#define pi 3.1415926

int main(){
	int n,m;
	cin >> n >> m;
	int arr[1000][1000];
	REP(i,n){
		REP(j,m){
			int nxt;
			cin >> nxt;
			arr[i][j] = nxt;
		}
	}
	int dpa[1000][1000];
	int dpb[1000][1000];
}

I'm using MinGW GCC g++ 4.8.1. Any ideas on what the issue is? When I run, I get an error message saying:

".exe has stopped working. Windows is checking for a solution to the problem..."

Full text and comments »

send_nodes
9 years ago
12

What do you guys keep in your coding library?

By send_nodes, history, 9 years ago, In English

I'm curious to know what all of you keep in your coding library to make your coding faster. I'm keeping a geometry library storing basic computational geometry tools(dot, cross, intersect, distance to line, centroid, area, etc.) and a graph theory library having max flow and flood fill.

I ask because I want to know how much is necessary to perform well in contests.

Full text and comments »

code-library

-9

send_nodes
9 years ago
8

Topcoder SRM 665 Div1 Medium

By send_nodes, history, 9 years ago, In English

Hi, I was having some trouble on figuring out the solution to this

It's obviously some sort of DP, and by looking at some code, I can tell that they are using left and right pointers, but I am unable to grasp the overall solution. Could someone please let me know the solution :D

Full text and comments »

topcoder

send_nodes
9 years ago
1

What is an offline solution?

By send_nodes, history, 9 years ago, In English

I've seen "offline solution" a lot on codeforces. What does it mean? Is it a solution that precomputes answers?

Full text and comments »

offline

send_nodes
9 years ago
6

Topological Sort Question

By send_nodes, history, 9 years ago, In English

I was working on this problem: http://codeforces.com/contest/510/problem/C

I spent a fair bit of time on it, and I knew while solving it that it was a topological sorting problem. However, I have gone through the USACO training pages to learn my algorithms, which doesn't have a section on topological sorting. I know standard graph algorithms like bfs,dfs,warshall,dijkstra, etc. but I don't know how to solve these topological sorting problems. The editorial mentions that this is a classic topological sort problem.

My question is, how can dfs be applied to solve this problem, and where can I find more theory/practice problems to practice topological sorting.

Thanks!

Full text and comments »

graph, topological sort

-3

send_nodes
9 years ago
11

#	User	Rating
1	jiangly	3640
2	Benq	3593
3	tourist	3572
4	orzdevinwang	3561
5	cnnfls_csy	3539
6	ecnerwala	3534
7	Radewoosh	3532
8	gyh20	3447
9	Rebelz	3409
10	Geothermal	3408

#	User	Contrib.
1	maomao90	174
2	awoo	164
3	adamant	163
4	TheScrasse	159
5	nor	158
6	maroonrk	156
7	-is-this-fft-	151
8	SecondThread	147
9	orz	146
10	pajenegod	145