### electro177's blog

By electro177, history, 2 years ago,

lets consider theatre to be a matrix of size n*m(n-rows,m-colums) and define adjacent seats to seat s(i,j) as s(i+1,j),s(i-1,j),s(i,j+1),s(i,j-1).Also some 'q' seats are blocked(may be chair is broken in theatre).what is the maximum number seats that u can select with given constraints?? n<=5; m<=1000; q<=m*n

my idea--i represented it as a graph and eliminated the broken seats,but for all connected componets i have find the maximum seats with this condition(but i do not know how?)

any ideas?

• +23

By electro177, history, 3 years ago,

given n(<=5e4) towns .every day we sell product in one of the towns.the towns that are chosen on any successive days should be different and a town i can be chosen max ci(<=n) times.find maximum number of sales? i/p: 3 (n) 7 2 3 (array of n elements) 0/p-11

exp:it is easy to see that use 7 and 2 and make it 5 and 0(ans-4) then 5 and 3 and make it to 2 and 0(ans-6+4).but finally we used a[3] now use a[0] only once ,and so ans is 11

my approach:i thought of using dp and find all possible sums using the array ,and take the nearest middle value,but this will tle and mle for the constraints

• 0

By electro177, history, 3 years ago,

Hey,any suggestion on this?..I am just able to solve the little variation of the things which i have practiced,but when new problems appear,i am not able to solve or even think with confidence.does this mean i have to solve many models or i have to develop out of box thinking(please says ways to improve out of box..i do not have friends who are as smart as you)

• -20

By electro177, history, 3 years ago,

hello all

given n cities from 1 to n and m flights.each flight is represented as(L,R,c) which means flight starts from city L and end at R and the cost is c(one can travel between any two cities from lower index to larger ,both inclusive)with cost c mathematically (l,r,c)--people can travel from u to v(l<=u<v<=r) at the cost c//not like our trains:)

find the minimum cost from city 1 to n,if not reachable o/p -1;

constraints: n<=1e5 //number of cities m<=1e5 /// number of flights 1<=l<r<=n //for each flight starting and ending points c<=1e9; // cost for each flight

i tried to create an adjacency list but to update the list i did not get idea how to do that effectively? bec it took (r-l)^2 for updating for each flight ,but that would tle

• -18

By electro177, history, 3 years ago,

I feel like an idiot and actually i am.Please give the idea how to become smart like u guys, i have many friends who does everything properly while i am not able to and in general decision making as well.please tell what have you done when you were in similar situation but came out smarter :) *smarter in the sense-iq,problem solving ,being away from distractions, decision making....... I know it feels like a really dumb question but please give 10 min of your life to help out a fool like me.

• +18

By electro177, history, 3 years ago,

There are N robots in a single row each having an integer value assigned to them.Each robot can terminate the closest robot (either left or right) if there is any When a robot with a value x terminates another robot with value y, then terminated robot vanishes and the value of the robot which terminated changes to x-y. The robots will destroy each other until one remains Find the maximum possible value of the last robot.

First line contains integer N and the next line contains N integers where ith element denotes the value of ith robot and these values are given in the same order in which those robots appear in the row.

CONSTRAINTS: 1<N<500000

-10^9 <= A, < 10^9 where A, is the value of ith robot

Example:

Input: 4

2 1 2 1

Output:

4

Explanation:

Second robot terminates third making array 2,-1,1 then second terminates the third one in this new array making the new array as 2,-2 and finally first terminate second leaving with value 4

I thought of doing range dp but it will be O(n^3),and also in the i had a doubt whether to find maximum value or minimum value Any ideas ??

• -23

By electro177, history, 3 years ago,

Hello codeforces,hope we all are doing well:)i have some doubts in some question which came in my coding test

1)Given a undirected tree,you are at the root node .some of the nodes have cake in them and you takes one secong to walk over one edge.find the minimum time to catch all the cakes and come back to the stating node(root node in which you were standing at time=0) (i thought it might be dfs but do not know how to come up with it)

constraints:N<=1e4;(no of nodes)

2)About modulo for large number: p=2^(100)-1 and q=2^(1000001)-1 how to find p*inverse(q),where inverse(q) is the inverse modulo of q with 10^9+7.I have no clue bec for smaller number we could do iterative thing

• +4

By electro177, history, 3 years ago,

A big binary number

You are given a number n. Find the decimal value of the number that is formed by concatenating the binary representations of the first n positive

Integers. Print the answer modulo 10^9 +7.

Example

Consider N = 2:

The binary representation of 1 is 1.

• The binary representation of 2 is 10

. So the number form after concatenation is 110. in decimals this is equivalent to 6.

n<1e9;

Some help what to do

• +1

By electro177, history, 3 years ago,

hello friends

Is there any way or stl trick to convert vector to vector but there should'nt be any equal elements eg)

[[1,1,6],[1,2,5],[1,2,5],[1,7],[1,7],[2,6]]

to

[[1,1,6],[1,2,5],[1,7],[2,6]]

for vector there exist a std::unique but for this case what to do :)

• +3

By electro177, history, 3 years ago,

Using set implementation it is working.but using vector the code gives some mingw error which i cannot understand.can anyone know what to do in order to make it work in vectors

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

#define ll long long
#define ar array

const int mxN = 2e5;
int n;
ar<int, 3> a[mxN];

int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i][1] >> a[i][0] >> a[i][2];
}
sort(a, a + n);
set<ar<ll, 2>> dp;
dp.insert({0, 0});
ll ldp = 0;
for (int i = 0; i < n; ++i) {
auto it = dp.lower_bound({a[i][1]});
--it;
ldp = max(ldp, (*it)[1] + a[i][2]);
dp.insert({a[i][0], ldp});
}
cout << ldp;
}


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

#define ll long long
#define ar array

const int mxN = 2e5;
int n;
ar<int, 3> a[mxN];

int main() {
cin >> n;
for (int i = 0; i < n; ++i) {
cin >> a[i][1] >> a[i][0] >> a[i][2];
}
sort(a, a + n);
vector<ar<ll, 2>> dp;
dp.push_back({0, 0});
ll ldp = 0;
for (int i = 0; i < n; ++i) {
auto it = lower_bound(dp.begin(), dp.end(), a[i][1]) ;
--it;
ldp = max(ldp, (*it)[1] + a[i][2]);
dp.push_back({a[i][0], ldp});
}
cout << ldp;
}

• -2

By electro177, history, 3 years ago,
const int mxN = 2e5;
int n, d[mxN], ans;

void dfs(int u = 0, int p = -1) {
for (int v : adj[u]) {
if (v == p)
continue;
dfs(v, u);
ans = max(d[u] + d[v] + 1, ans);
d[u] = max(d[u], d[v] + 1);
}
}


ans gives the diameter of the tree .It is not that trivial to understand for me.can someone explain please explain how the code works

• -10

By electro177, history, 3 years ago,
#include <bits/stdc++.h>
using namespace std;
#define ll  long long
#define ar array

const int mxa = 1e5 + 1;
ll a, b, c, n, m;
vector <ar<ll, 2>> adj[mxa];
ll dist[mxa];

int main() {

cin >> n >> m;
for (int i = 0; i < m; i++) {
cin >> a >> b >> c; --a, --b;

}

memset(dist, 0x3f, sizeof(dist));

priority_queue< ar<ll, 2>  , vector<ar<ll, 2>>, greater<ar<ll, 2>> > pq;
dist[0] = 0;
pq.push({0, 0});
while (pq.size()) {

ar<ll, 2> node = pq.top();
pq.pop();

if (node[0] > dist[node[1]])continue;

for ( ar<ll, 2> child : adj[node[1]]) {

if (dist[child[1]] > node[0] + child[0]) {
dist[child[1]] = node[0] + child[0];
pq.push({dist[child[1]], child[1]});
}
}

}

for (int i = 0; i < n; i++) cout << dist[i] << " ";

}


I have implemented code for Dijstra ,but it finds only min distance of each node from source node. could anyone please help how to retace the shortest path in this approach .Thank you

• -21

By electro177, history, 3 years ago,
priority_queue<ar<ll, 2>, vector<ar<ll, 2>>, greater<ar<ll, 2>>> pq;
pq.push({0, 0});
memset(d, 0x3f, sizeof(d));
d[0] = 0;
while (pq.size()) {
ar<ll, 2>    u = pq.top();
pq.pop();

if ( u [0]  > d[ u[1] ] ) // i have a doubt here
continue;

for (ar<ll, 2> v : adj[u[1]]) {

if (d[v[1]] > u[0] + v[0]) {
d[v[1]] = u[0] + v[0];
pq.push({d[v[1]], v[1]});
}

}
}


I do not understand why if ( u [0] > d[ u[1] ] ) continue; in the code .please give the reason ,is it related to connected component?

• -3

By electro177, history, 3 years ago,

while this is working fine ~~~~~ Your code here... bool emp (int i, int j) { if ( i >= 0 && i < n && j >= 0 && j < m && s[i][j] == '.' )return 1; else return 0;

} ~~~~~

this is giving run time error ~~~~~ Your code here...

bool emp (int i, int j) { if ( s[i][j] == '.' && i >= 0 && i < n && j >= 0 && j < m )return 1; else return 0;

} ~~~~~

does anyone know the reason

• -20

By electro177, history, 3 years ago,

I was doing problem towers.I sorted all the blocks according to weight + strength from exchange arguments and then now i did not get idea how to do transitions in dp ,but i saw some code and i thought i should do it by weights from 0 to total weight (but i do not know why) and the transition was

Your code here...

for (auto block : blocks) {
int w = block.w, s = block.s; ll v = block.v;
for (int i = w + s; i >= w; i--)
dp[i] = max(dp[i], dp[i - w] + v);
}


Please help me how to take the dp state and also the transitions mainly(i did not understand after thinking a lot) Thank you

• +5

By electro177, history, 3 years ago,

this template is not working in my sublime text

Your code here...
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
return os << '{' << p.first << ", " << p.second << '}';
}

template < class T, class = decay_t<decltype(*begin(declval<T>()))>,
class = enable_if_t < !is_same<T, string>::value >>
ostream & operator<<(ostream &os, const T &c) {
os << '[';
for (auto it = c.begin(); it != c.end(); ++it)
os << &", "[2 * (it == c.begin())] << *it;
return os << ']';
}
//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
_NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
(MACRO, ##__VA_ARGS__)
//Change output format here
#define out(x) #x " = " << x << "; "
#define dbg(...)                                                              \
cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << "\n"


 ~ ~~~~~

I think it is because i may be using older c++ compiler,i do not know how to upgrade to c++ 17,please help

but this is working

Your code here..

#include <bits/stdc++.h>

using namespace std;

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

• -16

By electro177, history, 3 years ago,

I have beem trying this for 2 days but i could not get idea nor understand solutions,could someone please explain it clearly ,i need your help (https://atcoder.jp/contests/dp/tasks/dp_o) someone help please:)

• 0

By electro177, history, 3 years ago,

Please help me with run time error, this is the cses book shop problem

with all type int ,it is accepted ,while with all long long it gives run time error,I thought of always using long long because it is helpful, can u please say when to not use long long

( run time error)//////

# include

using namespace std;

# define ll long long

void task() { ll n,target; cin >> n >> target; vector price(n), pages(n); for (ll&v : price) cin >> v; for (ll&v : pages) cin >> v;

vector<vector> dp(n + 1, vector(target + 1, 0));

// dp[0][0] = 0;

rep(i, 1, n) { rep(j, 0, target) {

dp[i][j] = dp[i - 1][j];
int left = j - price[i - 1];
if (left >= 0)
dp[i][j] = max(dp[i][j] ,  dp[i - 1][j - price[i - 1]] + pages[i - 1] );

}

}

cout << dp[n][target] << '\n'; }

int main() { int case = 1 ;

for (int i = 0; i < case; i++) task(); }

(accepted)//////

# include

using namespace std;

# define ll long long

void task() { int n, target; cin >> n >> target; vector price(n), pages(n); for (int&v : price) cin >> v; for (int&v : pages) cin >> v;

vector<vector> dp(n + 1, vector(target + 1, 0));

// dp[0][0] = 0;

rep(i, 1, n) { rep(j, 0, target) {

dp[i][j] = dp[i - 1][j];
int left = j - price[i - 1];
if (left >= 0)
dp[i][j] = max(dp[i][j] ,  dp[i - 1][j - price[i - 1]] + pages[i - 1] );

}

}

cout << dp[n][target] << '\n'; }

int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr); int case = 1 ; for (int i = 0; i < case; i++) task(); }

• -7

By electro177, history, 3 years ago,

I thought about it for a long time and i am cleearly commenting the code to help understand it easily

i cannot code it here properly for some reason ,so check my submission

• 0

By electro177, history, 3 years ago,

Hello codeforces community ,many of you here are motivated and working towards your goals which is great ,but not all .I am distracted by something or the other .I am addicted to some shitty websites like omegle and some other .But I want to be a good guy and a good coder ,what are the best personal experience of defeating any addiction .please help me and some others like me .addictions can be too dangerous :( . I have already tried to focus many times but could not able to do that. that's why i am asking your help. it can be soo silly but this is most serious issue.

• -19

By electro177, history, 3 years ago,

Hello codeforces, I am currently practicing dp and not getting questions contiously. I am feeling like not doing anything. How to be motivated while doing cp, I don't have any cp friend also. I think this will affect life in general

• +16

By electro177, history, 3 years ago,

This award goes to tourist because of the insane hard work and genius . You can refer (https://youtu.be/nfAnKzyiKTo) Salute to your work man.

• -44

By electro177, history, 3 years ago,

We are all getting older day by day. We are loosing our childhood so easily. I cannot understand how life works. Any ideas? What is your ultimate goal in your life?

• +57