Greetings Codeforces Community!
We invite you to participate in CodeFiesta, to be held on this coming Wednesday, 12th October 2022. The contest is hosted by DotSlash Community, Coding Club of Indian Institute of Information Technology, Nagpur. The contest is part of the annual tech fest TantraFiesta.
The contest will feature 6 problems of varying difficulty.
There will be more than ₹75,000 in prizes awarded!
The contest will be open to everyone. Please check the contest page for details.
The Contest starts on 12th October 2022 at 20:00 IST. You will have 2 hours to solve 6 problems. The problems were invented and prepared by the GeeksForGeeks team. Do visit the contest page and make yourself familiar with the rules and scoring.
Huge thanks to GeeksForGeeks for their invaluable support and great platform.
We hope you guys will have an amazing time. Good Luck & Have Fun!!!
UPD: The results will be declared on the instagram page of Tantrafiesta. The top 3 Indian participants will be contacted through mail for the distribution of the prizes. The next 5 participants will recieve GFG t-shirts.
UPD: Top 3 Indian Participants
UPD: Editorial
anshumandas7 my same java code gave tle for the 1st time then got AC with the same code for the 2nd time, please look into this, unnecessary penalty has been put because of this
How to solve count the subarrays?
You can use hashing.
First maintain a vector(say $$$freq$$$) of size $$$MAX+1$$$, where $$$MAX=10^5$$$.
Initially $$$freq[i]=0$$$ for all $$$i$$$.
Suppose $$$hashv[i]$$$ represents the hash value of $$$freq$$$ when we have processed first $$$i$$$ elements.
Take $$$map \lt ll,ll \gt track$$$.
Initially do $$$track[0]$$$++.
Now move from left to right, and at $$$j_{th}$$$ iteration do following in order.
There are multiple ways to maintain hash value of pair {$$$x,y$$$}. I used hash({$$$x,y$$$})$$$=y \cdot 37^x$$$
Thanks a lot!
If I take hash value as y.37^x it is working and it is not working for x.37^y what may be the reason ?
How to solve the Optimally 2 problem?
You can represent each string as a mask of 20 bits. Let the mask of a string be x. Notice that all submasks of x can be treated as subsequence of the string. So you can generate submasks for each string. If that submask has been visited previously then stop(as it is subsequence of an earlier string) otherwise update the value of the submask to the current index of string and do the same for its submasks as well. As there are only 20 bits so there are only 2^20 (1e6) strings/submasks possible. Now for each query just output the value of the corresponding mask value . Sample Implementation : https://pastebin.com/uZ8dWpDD
Damn it! I was trying the same thing in the contest. I tried to explicitly construct the graph first (instead of directly producing the neighbors of a particular node in the dfs function itself) . This approach gave me a TLE. Now, I tried it by directly producing the neighbors in the dfs itself and it passed. Accepted Solution vs TLE solution. Could you please help me understand why this is happening? The worst case time complexities of the two solutions look the same to me.
You could also solve it using SOS dp.
Can you pls share your code?
Submission
What is the intended time complexity of Minimum Deletions? My $$$O(30 \cdot N ) $$$ solution is getting TLE.
Another interesting fact is that sum of $$$N$$$ over all test cases exceeds $$$5 \cdot 10^5$$$ in some cases.
My code for reference
Can you explain your approach a bit?
Let us look at non-increasing portion first.
So if $$$B[0] \oplus B[1] \lt B[1] \oplus B[2]$$$, there exists a bit $$$j$$$ such that $$$S(B[0],j)=0,S(B[1],j)=1$$$ and $$$S(B[2],j)=1$$$. Also $$$S(B[0],k)=S(B[1],k)=S(B[2],k)$$$ for $$$j \lt k \leq 30$$$. Here $$$S(X,p)=1$$$ if $$$p_{th}$$$ bit is set in $$$X$$$ otherwise $$$S(X,p)=0$$$. Arrangement of bits should be in this way becuase $$$B$$$ is increasing.
Now if $$$[B[0] \oplus B[1], B[1] \oplus B[2], \cdots, B[k-1] \oplus B[k]]$$$ is a non-increasing array, we should have $$$D(B[0],B[1]) \gt D(B[1],B[2]) \gt \cdots \gt D(B[k-1],B[k])$$$, where $$$D(X,Y)$$$ gives the highest bit $$$j$$$ such that $$$S(X,j) \neq S(Y,j)$$$.
You can easily implement this using trie.
Now we have similar stuff for non-decreasing portion.
If $$$B[0] \oplus B[1] \gt B[1] \oplus B[2]$$$, there exists a bit $$$j$$$ such that $$$S(B[0],j)=0,S(B[1],j)=0$$$ and $$$S(B[2],j)=1$$$. Also $$$S(B[0],k)=S(B[1],k)=S(B[2],k)$$$ for $$$j \lt k \leq 30$$$. Here $$$S(X,p)=1$$$ if $$$p_{th}$$$ bit is set in $$$X$$$ otherwise $$$S(X,p)=0$$$. Arrangement of bits should be in this way becuase $$$B$$$ is increasing.
If $$$[B[k] \oplus B[k+1], B[k+1] \oplus B[k+2], \cdots, B[m-1] \oplus B[m]]$$$ is a non-decreasing array, we should have $$$D(B[k],B[k+1]) \lt D(B[k+1],B[k+2]) \lt \cdots \lt D(B[m-1],B[m])$$$, where $$$D(X,Y)$$$ gives the highest bit $$$j$$$ such that $$$S(X,j) \neq S(Y,j)$$$.
So for non-increasing portion, move from left to right($$$1$$$ to $$$N$$$), and for non-decreasing portion, move from right to left($$$N$$$ to $$$1$$$).
Is it just for indian?? Or everyone is invited???
Everyone, but it's over now.
Any update about prizes?
Say something pls about prizes
nice way of ghosting
scam 2022 by anshumandas7
The results will be declared on the instagram page of Tantrafiesta. The top 3 Indian participants will be contacted through mail for the distribution of the prizes. The next 5 participants will recieve GFG t-shirts.
This is what 75k+ prize looks like omg!!
So only Indian participants were eligible for prizes?
Yes
It should has been mentioned in announcement, so that everyone was aware beforehands