tautology's blog

By tautology, history, 2 months ago, In English

Hello codeforces! Today is chemthan's birthday. Join me to wish him a very happy birthday.


Happy birthday, chemthan.

Read more »

 
 
 
 
  • Vote: I like it
  • +9
  • Vote: I do not like it

By tautology, history, 4 months ago, In English

Hi,

I found this solution to tri-tiling problem, but I am not able to prove it.

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


int ways(int tile)
{
	if (tile < 0) return 0;
	if (tile == 0) return 1;
	if (tile == 2) return 3;
	return ways(tile - 2) * 4 - ways(tile - 4);
}

signed main()
{ 
  int n;
  
  while(true){
  	 cin >> n;
  	 if(n == -1) break;
  	 if(n == 1){
  	 	 cout << 0 << '\n';
  	 	 continue;
  	 }

  	 cout << ways(n) << '\n';
  }
  return 0;
}

Read more »

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

By tautology, history, 8 months ago, In English

I was using inbuilt C++ single file build, but then I found it was using C++98. Later then I tried using this build and many others builds which I found on the web. But the issue is something else. Now I'm getting the following win-error :
Screenshot-101

Can anyone please help me out.

Read more »

 
 
 
 
  • Vote: I like it
  • -2
  • Vote: I do not like it

By tautology, history, 16 months ago, In English

Given a unweighted, undirected graph of N vertices and M edges, vertices are numbered from 1 to N. Also there are K special vertices. You have to answer Q queries. In each query, you're given a vertex V. You have to print shortest distance of nearest special vertex. If there is no special vertex reachable from V, print -1.
Note : Graph doesn't contain multiple edges or self loops and it may be disconnected.
Constraints :
1 <= N, K, Q <= 1e5
1 <= M <= 2e6
Sample Input:
5 3 3 // N M K
1 2 // edge 1
2 3 // edge 2
1 3 // edge 3
1 3 5 // special vertices
5 // Q
1 // V for 1st query
2 // " " " 2nd " "
3 // " " " 3rd " "
4 // " " " 4th " "
5 // " " " 5th " "

Sample Output:
0
1
0
-1
0

P.S. : This problem was asked in Codechef's CCDSAP advanced contest on 22th Sept.,2019. Now it's over.

Read more »

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

By tautology, history, 3 years ago, In English

Given array of n non-negative integers and a positive integer k. Is is possible to count all pairs with bitwise-OR equals to k?. Time complexity should be better than O(n^2). More formally , count no. of distinct pairs (ai,aj) such that ai|aj==k.[Note: pairs (ai,aj) and (aj,ai) are same.] If this is possible in T(n)<O(n^2),then how? Constraints: 1<=n<=1000000, 0<=ai<=10000.

Read more »

 
 
 
 
  • Vote: I like it
  • -29
  • Vote: I do not like it