Hi,

Can people who quickly solved todays Codeforces Round 468 (Div. 1, based on Technocup 2018 Final Round) please share their thought process? It would be great to know how you reduced those problems to standard stuff so quickly. (Particularly for Div-1 B and Div-1 C, but other questions are welcome too).

Thanks

25044141 779D - String Game

t = raw_input()
p = raw_input()
aa = [int(x) - 1 for x in raw_input().split()]

l = len(p)
r = lt = len(t)
while l < r:
    m = (l + r) // 2
    sa = set(aa[:lt-m])
    it = (a for i, a in enumerate(t) if i not in sa)

    if all(c in it for c in p):
        r = m
    else:
        l = m + 1

print(lt - l)

In particular, how does the line

if all(c in it for c in p):

work? How is it able to ensure that p is a subsequence of it by a simple containment check over all the letters of p? I expected it to output 2 (instead of 1, which is the correct answer) for the following case, but it worked correctly.

abab

ab

1 4 3 2

I was trying to implement the following functions on a N * N grid in O(log^2(N)) time:

1. Update: Add v to all grid points in specified rectangle. (v, rectangle are specified in this update)

2. Query: Print maximum value in specified rectangle. (rectangle is specified in this query)

I tried implementing a 2-D segment tree, but got stuck with the range updates part (lazy propagation in 2-D dimensions is not pretty)

Is it even possible to do so? (anything below O(N) per operation is fine).

Problem

TL;DR version: You are given a bipartite graph with atmost 1000 vertices on each side. M (upto 1,000,000) edges are added one by one. Compute the minimum vertex cover after each addition.

Clarification: You need to compute the minimum vertex cover / maximum matching everytime an edge is added.

Any ideas?

http://wcipeg.com/problem/noi99p3

Could someone please help with this problem? Best I could come up with was a (n^2.5) *m dp solution which will obviously timeout.

Found this blog online, but couldn't understand the idea (search + pruning). https://www.byvoid.com/blog/noi-1999-solution

Thanks!

Statement

Is it possible to solve this question using splay trees (without using any sort of randomization)?

I have tried the following:-

• Treaps (isolate range for query): TLE Code

• Treaps (query by traversing BST): AC Code

• Splay (isolate range for query): TLE Code

• Splay (query by traversing BST): TLE Code (This one fails when all the updates are before the queries.The updates might lead to a straight chain BST even with splaying. And since the query by traversing BST never calls splay(), every query takes linear time)

Suggestions please. An AC code (Splay Tree only) would be really helpful.

Hi,

I have been unable to update my SPOJ,Timus profiles on a2oj.com for quite some time, but the feature is working perfectly for my codeforces profile. The profile links are correct( they take me to to correct page when I navigate by pressing the number next to the Update button, but the number itself does not get updated).

Could someone please suggest a way to correct this? Thanks.

PS: I already tried re-adding the SPOJ profile, and it shows the count as 0 now(after updating).

Original problem

If we were asked for the maximum length contiguous bracket sequence, how would this problem be solved)? Constraints may be slightly lower(n=10^5 instead of 10^6).

I would like to invite you all to Coder 2015 jointly organized by Computer Science Association and Information Systems Association, BITS-Pilani, as a pre-Apogee event.

The contest will be held on HackerRank for 24 hours from 24th March 8pm to 25th March 8pm (IST)

It will be team contest with a maximum team size of 3.

Cash prizes worth INR 10,000 along with other HackerRank goodies are up for grabs.

The problems have been set and tested by akulsareen,pranet, Zzyzx, StoneCold_ and flashfire, amit9oct, and saurabh14. We do hope that you will enjoy the problem set. Southpark fans are in for a treat =)

Please visit the facebook page for updates.

Update:

With more than 14 hours to go, savinov from Moscow IPT has already finished our problemset! We just got schooled.

From India, mode_warrior is currently leading with 12 problems solved, with believe_iiith1 and lazy_propagation not far behind.

The leader board is currently as follows :

.

8840553

Could anyone please point out my error in this one? I'm getting a runtime error whenever I call the following assertion in my lca() function

int x=firstOccurance[u];
int y=firstOccurance[v];
assert(x>=0 && x<m);
assert(y>=0 && y<m); 

which is weird since I specifically ensure that this is not possible by running the following in main() after generating firstOccurance[]

for(int i=1;i<=n;++i)
  {
    assert(firstOccurance[i]>=0);
    assert(firstOccurance[i]<m);
  } 

and this part happens to pass the assertion tests.

I have tried many random samples with n=100000 on my system, but could not replicate this error.

Thanks

Update: Corrected thanks to catlak_profesor_mfb

Since n was 100000,I had taken a size of 500000 for my segment tree which seemed to be sufficient. Unfortunately since the segment tree was on my order[] array, which has a size of 2*n-1, 500000 wasn't sufficient after all.