optimized this code

Pages: 12
closed account (jLCX216C)
#include <iostream>
using namespace std;
int main() {
int t;
cin>>t;

while(t--){
int flag=0;
int n;
cin>>n;
int a[n+1];
for(int i=1;i<=n;i++){
cin>>a[i]; // entering the elements into the array.
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]!=a[j] && a[a[i]] == a[a[j]]){
flag=1;
break;
}
}
}
if(flag!=1){
cout<<"No "<<endl;
}
else{
cout<<"Yes "<<endl;
}
flag=0;
}
return 0;
}
Last edited on
int a[n+1];
This is illegal (i.e. not C++ code) and dangerous.

What is this program meant to do?
closed account (jLCX216C)
That not the problem I can also take it as a[10000]
main problem in the complexity of this code
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(a[i]!=a[j] && a[a[i]] == a[a[j]]){
flag=1;
break;
}
}
}
please help in optimizing this
What are you trying to do? What is the requirement on this code? What about the numbers that the user enters are you looking for?
closed account (jLCX216C)
I am trying to compare whether in a given array I can found this sequence or not
A1,A2,…,AN. we need to determine if it is possible to choose two indices i and j such that Ai≠Aj, but Asub(Ai) = Asub(Aj).
sub==subscript
So for this sequence: { 2 , 3, 7, 7 }

the answer would be "true", because A[2] = 7 and A[3] = 7?
closed account (jLCX216C)
No Let me give you the example
for this sequence
1 1 2 3
it is true because Asub(A3)=Asub(A1) and A3≠A1
and for this the answer is no
2 1 3 3
because Asub(A3)=Asub(A4) but A3=A4,
I am starting from 1 index in all the example
Last edited on
The only "optimization" I can see of your brute-force method is to terminate the outer loop when flag becomes true:

 
for (int i = 1; i <= n && !flag; i++) {

I'll think about other possibilities, though.
closed account (jLCX216C)
@tpb what are those possibilities would you please elaborate
I couldn't think of anything.
Did you try adding the flag test to the outer loop?
Is that not good enough?
If you're trying to solve a programming problem, it's best to give a link to it so I can see the details.
closed account (9LzTpfjN)
Can anybody help me getting 100 in this problem.

Chef has a sequence A1,A2,…,AN; each element of this sequence is either 0 or 1. Appy gave him a string S with length Q describing a sequence of queries. There are two types of queries:

'!': right-shift the sequence A, i.e. replace A by another sequence B1,B2,…,BN satisfying Bi+1=Ai for each valid i and B1=AN
'?': find the length of the longest contiguous subsequence of A with length ≤K such that each element of this subsequence is equal to 1
Answer all queries of the second type.

Input
The first line of the input contains three space-separated integers N, Q and K.
The second line contains N space-separated integers A1,A2,…,AN.
The third line contains a string with length Q describing queries. Each character of this string is either '?', denoting a query of the second type, or '!', denoting a query of the first type.


Output
For each query of the second type, print a single line containing one integer — the length of the longest required subsequence.

Constraints
1≤K≤N≤105
1≤Q≤3⋅105
0≤Ai≤1 for each valid i
S contains only characters '?' and '!'

Subtasks
Subtask #1 (30 points):

1≤N≤103
1≤Q≤3⋅103
Subtask #2 (70 points): original constraints

Example Input
5 5 3
1 1 0 1 1
?!?!?
Example Output
2
3
3


Explanation
In the first query, there are two longest contiguous subsequences containing only 1-s: A1,A2 and A4,A5. Each has length 2.
After the second query, the sequence A is [1,1,1,0,1].
In the third query, the longest contiguous subsequence containing only 1-s is A1,A2,A3.
After the fourth query, A=[1,1,1,1,0].
In the fifth query, the longest contiguous subsequence containing only 1-s is A1,A2,A3,A4 with length 4. However, we only want subsequences with lengths ≤K. One of the longest such subsequences is A2,A3,A4, with length 3.


I have got 30 pts.plz help me getting 100.
closed account (jLCX216C)
@yoyohoney what concept are you using for this I have got 100 pts I could optimize your code
Or can you just share the code I will optimize that code itself
closed account (9LzTpfjN)
i m using segment tree but i don't know how to update the binary string.
maybe u can share ur code or help on how to update segment tree.
closed account (jLCX216C)
I think segment tree is not needed here that why I am telling you to share code that will help me in solving your problem
closed account (9LzTpfjN)
I m using brute force so no way my code with which i got 30 pts can fetch me 100 pts.
Can u plz tell me method that u used to solve the problem?

I don't know how to update the binary string .plz explain.what should i write in else condtion?

this is segment tree method

#include <bits/stdc++.h>
#define mp make_pair
#define pii pair<int, int>
#define MA 10000001

using namespace std;

struct node{
int val;
pii left, right;

node(){
val= 0;
left.first = left.second = MA;
right.first = right.second = -1;
}

void merge(const node& n1, const node& n2, int l, int r){
val = max(n1.val, n2.val);
left = n1.left;
right = n2.right;

int l1 = n1.right.first, l2 = n1.right.second, r1 = n2.left.first, r2 = n2.left.second;
if(l1 != -1 && r1 != MA){
int t1 = l1, t2 = r2;
val = max(val, t2 - t1 + 1);
if(t1 == l) left = mp(t1, t2);
if(t2 == r) right = mp(t1, t2);
}
}
};

node seg[300001];

int val[100001] = {0}, n;

void build(int l, int r, int i){
if(l == r){
if(!val[l]) return;
seg[i].val = 1;
pii p = mp(l, r);
seg[i].left = seg[i].right = p;
return;
}
int mid = (l+r)/2;
build(l, mid, i*2+1);
build(mid+1, r, i*2+2);
seg[i].merge(seg[i*2+1], seg[i*2+2], l, r);
}

void update(int l, int r, int i, int pos){
if(l == r){
seg[i].val = 1;
pii p = mp(l, r);
seg[i].left = seg[i].right = p;
return;
}
int mid = (l+r)/2;
if(mid >= pos) update(l, mid, i*2+1, pos);
else update(mid+1, r, i*2+2, pos);
seg[i].merge(seg[i*2+1], seg[i*2+2], l, r);
}

void print(){
for(int j = 0; j < 9; j++)
cout << j << " --> " << seg[j].val << " (" << seg[j].left.first << " " << seg[j].left.second << ") , (" << seg[j].right.first << " " << seg[j].right.second << ") " << endl;
}

int main(){
ios_base :: sync_with_stdio(0);
cin.tie(0);

int q,k;
cin >> n >> q>>k;
char s[n];
for(i=0;i<n;i++)
{
cin>>a[i];
s[i]=a[i]+'0';
}
for(int j = 0; j < n; j++)
if(s[j] == '0') val[j] = 0;
else val[j] = 1;

build(0, n-1, 0);
while(q--){
char type;
cin >> type;
if(type == '?') cout << seg[0].val << endl;
else{
}
}
return 0;
}
Last edited on
closed account (jLCX216C)
@yoyohoney I have got 100 by using brute force itself ,It is not a completely a brute force but still its work for all cases
I cann't share the same ans as judge would banned both account so give me your brute force method I would optimize it with some specific conditions
closed account (9LzTpfjN)
u can send me ur code.I myself will optimize my code by looking through which i can get to know my mistake
Last edited on
closed account (jLCX216C)
I am using bitmasking this is not the complete code but you will get the idea
#include<bits/stdc++.h>
using namespace std;
#define MAX 100000
int main()
{
int n,q,k,count;
string str;
cin>>n>>q>>k;
bitset<MAX>s,c;
//inserting bits in array
for(int i=0;i<n;i++)
{
int temp;
cin>>temp;
s[i]=temp;
}
cin>>str;
for(int i=0;i<q;i++)
{
//making duplicate bitset
c=s;
if(str[i]=='?')
{
count=0;
while(c!=0)
{
//using bitmask to count maximum no of continuous 1's-O(1's bit)
c=(c&(c<<1));
count++;
}
if(count>k)
cout<<k<<"\n";
else
cout<<count<<"\n";
}
else
{
//shifting each bit to right and updating first bit with previous last bit
bool lb=s[n-1];
s=s>>1;
s[n-1]=lb;
}
}
return 0;
}
If you share your brute force code then it would be good as I would love to do by that method also
So please do share that as well I am willing to do that also
closed account (9LzTpfjN)
getting tle using your method
closed account (9LzTpfjN)
Has anybody got 100 in hmappy1?
Can you plz share ur approach.
Last edited on
Pages: 12