Bank and vulnerable passwords

All submissions for this problem are available.

There is a bank which gives their customers a password 'only' for transactions(there is no username) via ATM. Also the ATM does not have any enter key, it automatically logs you into your account as soon as you enter the right password. There is a huge problem in such type of system,i.e., suppose that if two people A and B have “aadil” and “aadilahmad” as their passwords respectively, so whenever B will try to login, the machine will automatically login B into A’s account.

Input:

First line of the input contains an integer N,the number of users in Bank. Next N lines contains strings which are passwords of the users. Tell if the bank is vulnerable or non-vulnerable.

Output:

Print "vulnerable" if the bank is vulnerable or "non vulnerable" if the bank is not vulnerable.

Program constraints - 

N <= 10^5

All passwords consists of lower case english alphabets

1<=length of password<=50

Sample Input - 

2

likemeifyoucan

likeme

Sample Output - 

vulnerable

--------------------------------------------------------------editorial------------------------------------------------------------------------------

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Trie

PROBLEM:

Problem: Given a list of passwords (word) you need to tell whether any word is the prefix of any other word in the list.

EXPLANATION:

First of all I would like to enlighten that some of the contestents have solved the problem by just sorting them and finding the substring due to weak test cases. But the problem was intended to be solved using the data structure trie. You are given a list of words; you need to find if any word is the prefix of another word in the list. You can do so by inserting each given passwords in the trie and simultaneously checking if insertion of the password makes conflict with the condition, if so then print “vulnerable” else print “non vulnerable”. Remember to scan all the words even if the conflict occurs in between.

--------------------------------------------------code-----------------------------------------------------------------------

1. #include<stdio.h>
2. #include<string.h>
3. #include<iostream>
4. using namespace std;
5. struct node
6. {
7. int word_count;
8. struct node * has[26];
9. bool ispre[26];
10. };
11. int exist=0;
12. node* init()
13. {
14. node *node1=new node;
15. node1->word_count=0;
16. for(int i=0;i<26;i++){
18. node1->has[i]=NULL;
19. node1->ispre[i]=false;
20. //cout<<"here"<<endl;}
21. }
22. return node1;
24. }
25. node *root;
26. void build(char arr[])
27. {
28. node *present=root;
30. int len=strlen(arr);
31. // cout <<arr<<endl;
33. for(int i=0;i<len;i++)
34. {
35. // cout<<"building "<<endl;
36. int flag=0;
37. if(present->has[arr[i]-'a']==NULL)
38. {
39. // cout<<" creating "<<arr[i]<<endl;
40. flag=1;
41. ////cout<<"making"<<endl;
42. present->has[arr[i]-'a']=init();
43. }
45. if(present->ispre[arr[i]-'a']==true)
46. {
47. exist=1;
48. // cout<<"herer "<<endl;
49. }
50.  
52. if(i==len-1)
53. {
54. // cout<<"word formed with "<<arr[i]<<endl;
55. present->ispre[arr[i]-'a']=true;
58. }present=present->has[arr[i]-'a'];
59. if(i==len-1 && flag==0)
60. {
61. exist=1;
62. }
63. }
66. }
68. int main()
69. {
70. int t;
71. cin>>t;
72. node *node1=init();
73. root=node1;
74. while(t--)
75. {
77. char arr[100000];
78. cin>>arr;
79. build(arr);
81. }
82. if(exist==1)
83. {
84. cout<<"vulnerable"<<endl;
86. }
87. else
88. cout<<"non vulnerable"<<endl;
89. }

Nikitosh and xor

Nikitosh the painter has a 1-indexed array A of N elements. He wants to find the maximum value of expression 

(A[l₁] ⊕ A[l₁ + 1] ⊕ ... ⊕ A[r₁]) + (A[l₂] ⊕ A[l₂ + 1] ⊕ ... ⊕ A[r₂]) where 1 ≤ l₁ ≤ r₁ < l₂ ≤ r₂ ≤ N.

Here, x ⊕ y means the bitwise XOR of x and y.

Because Nikitosh is a painter and not a mathematician, you need to help him in this task.

Input

The first line contains one integer N, denoting the number of elements in the array.

The second line contains N space-separated integers, denoting A₁, A₂, ... , A_N.

Output

Output a single integer denoting the maximum possible value of the given expression.

Constraints

• 2 ≤ N ≤ 4*10⁵
• 0 ≤ A_i ≤ 10⁹

Subtasks

• Subtask 1 (40 points) : 2 ≤ N ≤ 10⁴
• Subtask 2 (60 points) : Original constraints

Example

Input:
5
1 2 3 1 2

Output:
6

Explanation

Choose (l₁, r₁, l₂, r₂) = (1, 2, 3, 3) or (1, 2, 4, 5) or (3, 3, 4, 5).

----------------------------------------------------------------------editorail------------------------------------------------------------------------------

IFFICULTY:

Medium

PREREQUISITES:

Tries, Properties of Bitwise XOR

PROBLEM:

Given is an array A containing numbers in the range 0 to 109. We have to find l1, r1, l2 and r2 (l1≤r1<l2≤r2) such that (A[l1]⊕A[l1+1]⊕⋯⊕A[r1]) + (A[l2]⊕A[l2+1]⊕⋯⊕A[r2]) is maximised. Here x⊕yrefers to Bitwise XOR of x and y.

EXPLANATION:

Subtask 1
Let's start off by thinking of the simplest algorithm that we can. We we will then optimise it step by step by making certain observations.
So, the simplest thing to do is to implement what the problem says. We can run four loops, one each for l1, r1, l2 and r2. This gives us an O(N4) algorithm which will exceed the time limit for all the subtasks.

How can we optimise this? Let's make an observation. If we know for each i = 1 to N, the maximum value we can get for (A[l1]⊕A[l1+1]⊕⋯⊕A[r1]) and (A[l2]⊕A[l2+1]⊕⋯⊕A[r2]) such that r1≤i and i<l2, then we can tell the answer in O(N) by simply taking the maximum of the sum of the two terms over all i.

What remains now is to calculate efficiently for each i the max (A[l1]⊕A[l1+1]⊕⋯⊕A[r1]) and (A[l2]⊕A[l2+1]⊕⋯⊕A[r2]) such that r1≤i and i<l2. Let's call the two terms lbest[i] and rbest[i]respectively. For calculating lbest[i], we iterate from j = i to 1 and find the j such that val = (A[j]⊕A[j+1]⊕⋯⊕A[i]) is maximised. Then, lbest[i] = max(lbest[i−1],val). Similarly, we can fill the array rbest.

Calculating the arrays lbest and rbest require O(N2) time. After that, the answer can be computed in O(N). For this subtask, an O(N2) solution will pass.

Subtask 2
We need to somehow speed up the calculation of arrays lbest and rbest. Up till now, we haven't utilised any property of XOR operation in our solution. Let's try to optimise our algorithm using the following property:
Let cumul[i] = (A[1]⊕A[2]⊕⋯⊕A[i]).
Then for some j≤i, cumul[j−1]⊕cumul[i] = (A[j]⊕A[j+1]⊕⋯⊕A[i]).
The proof behind this is left to the reader as a simple exercise.

We can now say that lbest[i] = max(lbest[i−1],val) where val = maximum of (cumul[j−1]⊕cumul[i]) for j = 1 to i.

Calculating lbest this way still takes O(N2). For i = 1 to N, we need to somehow optimise finding the index j such that (cumul[j−1]⊕cumul[i]) is maximum. If we can do it in O(logA[i]), then we can compute the array lbest(and analogously, rbest too) in O(NlogAmax).

We can use Tries to get the required complexity. We will keep a trie which holds the binary representation of elements in the array cumul. While processing for i from 1 to N, we will first use the trie to get the value which is maximum of (cumul[j−1]⊕cumul[i]) for 1≤j≤i, and then insert cumul[i] into the trie. This will allow us to calculate lbest in the required complexity. Similarly, we can calculate rbest also.

Inserting into a trie is a standard operation. Let us look at how we do the other operation, i.e., for a value x, finding the value y in the trie such that x⊕y is maximised. Since, the trie stores binary representations of numbers, we first convert x to its binary representation. Then, we can go down the trie and for each bit in the representation of x, we try to find whether bit of opposite value exists or not. It is easy to see why we seek opposite; because 1⊕1 and 0⊕0= 0 while 0⊕1 = 1.

COMPLEXITY:

--------------------------------------------------------editorial----------------------------------------------------------------------------------

1. #include<iostream>
2. using namespace std;
3. #include<bits/stdc++.h>
4. void calc(int val[])
5. {
6. val[0]=1;
7. for(int i=1;i<=31;i++)
8. {
9. val[i]=val[i-1]*2;
10. }
11. // cout<<" generation done "<<endl;
12. return;
13. }
14. class node
15. {
16. public:
17. node * ll,*rr;
18. node()
19. {
20. ll=NULL;
21. rr=NULL;
22. }
23. };
24.  
25. int join(node * head,int val[],int num)
26. {
28. node *var=head;
29. int ans=0;
30. for(int i=29;i>=0;i--)
31. {
32. //cout<<" insert "<<num<< " i is "<<i<<endl;
33. if(num&val[i])
34. {
36. if(head->rr!=NULL)
37. {
38. head=head->rr;
40. }
41. else
42. {
43. head->rr= new node();
44. head=head->rr;
45. }
47. if(var->ll!=NULL)
48. {
49. var=var->ll;
50. ans+=val[i];
51. }
52. else
53. {
54. var=var->rr;
55. }
56. }
59. else
60. {
61. // cout<<" here "<<endl;
62. if(head->ll!=NULL)
63. {
64. // cout<<" kasdkas"<<endl;
65. head=head->ll;
67. }
68. else
69. {
70. // cout<<" creating "<<endl;
71. head->ll= new node();
72. head=head->ll;
73. }
75. if(var->rr!=NULL)
76. {
77. var=var->rr;
78. ans+=val[i];
79. }
80. else
81. {
82. var=var->ll;
83. }
84. }
85. }
86. return ans;
87. }
88.  
89. int main()
90. {
91. int n;
92. cin>>n;
93. int arr[n+10];
94. int val[100];
95. calc(val);
96. int right[n+10000];
97. int left[n+1000];
98. int till_now=0;
99. for(int i=0;i<n;i++)
100. {
101. scanf("%d",&arr[i]);
102. }
103. node *head1=new node(),*head2=new node();
104. till_now=0;
105. join(head1,val,0);
106. //cout<<" o inserted "<<endl;
107. right[0]=arr[0];
108. for(int i=0;i<n;i++)
109. {
110. till_now =till_now ^ arr[i];
111. int ans=join(head1,val,till_now);
112. if(i>0)
113. right[i]=max(right[i-1],ans);
114. //cout<<" f "<<ans<<endl;
115. }
117. // cout<<" fw done "<<endl;
118. join(head2,val,0);
119. left[n-1]=arr[n-1];
120. till_now=0;
121. for(int i=n-1;i>=0;i--)
122. {
123. till_now =till_now ^ arr[i];
124. int ans=join(head2,val,till_now);
125. if(i<n-1)
126. left[i]=max(left[i+1],ans);
127. // cout<<" b "<<ans<<endl;
128. }
130. //cout<<" bw done "<<endl;
131. int ans=0;
132. for(int i=0;i<n-1;i++)
133. {
134. ans=max(ans,right[i]+left[i+1]);
135. }
136. printf("%d\n",ans);
137. return 0;
138. }
139. 
     

O(NlogAmax)
--------------------
---------