youknowwhoiam1's blog

Invitation to CodeFiesta 2022 on GeeksForGeeks
By youknowwhoiam1, 19 months ago, In English

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

  1. Satyam Kumar Roy satyam343
  2. Hardik Aggarwal cheems
  3. Ritik Gupta

UPD: Editorial

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

Comments Comments (24)
| Write comment?
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

youknowwhoiam1 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

→ Reply
»
19 months ago, # |
  Vote: I like it +3 Vote: I do not like it

How to solve count the subarrays?

→ Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 3   Vote: I like it +3 Vote: I do not like it

    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<ll,ll> track$$$.

    Initially do $$$track[0]$$$++.

    Now move from left to right, and at $$$j_{th}$$$ iteration do following in order.

    • assign $$$hashv[j]=hashv[j-1]$$$
    • subtract hash value of {$$$A_j,freq[A_j]$$$} from $$$hashv[j]$$$
    • update $$$freq[A_j]=(freq[A_j]+1) \mod K$$$
    • add hash value of {$$$A_j,freq[A_j]$$$} to $$$hashv[j]$$$
    • add current value of $$$track[hashv[i]]$$$ to answer and do $$$track[hashv[i]]$$$++

    There are multiple ways to maintain hash value of pair {$$$x,y$$$}. I used hash({$$$x,y$$$})$$$=y \cdot 37^x$$$

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks a lot!

      → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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 ?

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the Optimally 2 problem?

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
  • »
    »
    19 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    You could also solve it using SOS dp.

    → Reply
»
19 months ago, # |
  Vote: I like it +5 Vote: I do not like it

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

→ Reply
  • »
    »
    19 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you explain your approach a bit?

    → Reply
    • »
      »
      »
      19 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let us look at non-increasing portion first.

      So if $$$B[0] \oplus B[1]<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 < 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]) > D(B[1],B[2]) > \cdots > 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]>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 < 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]) < D(B[k+1],B[k+2]) < \cdots < 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$$$).

      → Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it just for indian?? Or everyone is invited???

→ Reply
»
19 months ago, # |
  Vote: I like it +26 Vote: I do not like it

Any update about prizes?

→ Reply
»
19 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Say something pls about prizes

→ Reply
»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

nice way of ghosting

→ Reply
»
19 months ago, # |
  Vote: I like it +20 Vote: I do not like it

scam 2022 by youknowwhoiam1

→ Reply
»
19 months ago, # |
  Vote: I like it +31 Vote: I do not like it

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!!

→ Reply
»
19 months ago, # |
  Vote: I like it 0 Vote: I do not like it

So only Indian participants were eligible for prizes?

→ Reply