Hi!

Tomorrow at 4:00 MSK will be held Topcoder SRM 696.

Let's discuss problems after contest!

Hi!

Tomorrow at 14:00 MSK will be held Topcoder SRM 695.

Let's discuss problems after contest!

Tomorrow at 19:00 MSK will be held Topcoder SRM 694.

Let's discuss problems after contest!

Thanks to dened for pointing out the mistake.

I have seen many competitive programmer who are working in different companies. I am just thinking how do they get time to practice the coding? I mean there are lots of topic to learn and lots of things to work on ....

Well there are some of them who are already better when they entered into the Job, so at least they don't need to learn new things but I guess everyone needs some time to workout. But there is other people who also learned after getting into a job I guess.. and also there is a social life in which even if someone doesn't want to attend he/she had to sometimes. Also there are always a deadline to meet in a company work schedule.

I will be really glad if you people (Codeforces community) share your experience on this regard. Please if possible also provide the company name in which you belong.

The key things I guess everyone wants to know is :-

1. How much time you get after end of the day for learning or practice or learning+practice?

2. what is your work hour in company?

3. Is it stressful to do what you do?

4. Is it possible to become a neat competitive programmer like that (I mean doing CP and job both)?

5. How is your social life? // what I want to ask is How do you cope up with?

Feel free add to your experience on this regards. Take care everyone and thanks.

I thought I would see many answers. There are so many awesome coders who are maintaining both so efficiently. Don't know why any of them was not interested in answering it here. If I had the chance to meet with them I would do that for sure. Anyway if any of those coders want to tell their way of working ..feel free to message me. I will let other users know (not disclosing the name of course) about their experience if they wish me to do it. Thanks to all people who has read and answered this post."

** None of them seemed to answer. Any coder from any organization may feel free to share their experience on any of the question. It will be helpful to many fellow coders joining the software Industry or Job life."

Message

You are given 2 strings :- S and t.

You have to convert any sub-string of S to t with 3 operations

1.  Delete char from sub-string of S (from the endpoints only).
2.  Add char to sub-string of S (at endpoints only)
3.  Change any char of S.

There are few ideas that help you solve this problem:-

=== First of all there always exist an answer. Using |t| operation we can always have string t.

So the first question is do we have to consider those sub-strings of s that are greater than |t| in length? Well you might think you have to but let's analyze the situation a bit:-

=== (a) No matter what we do we have to end in string t. But this sub-string of S [we call it SS from now on] has length > |t| That means we have to delete few characters. |---> Characters can only be deleted from both the end points. So we have to delete few from end points. Now the thing is those that we are going to delete, is there any meaning for considering in the first place? For example: Then we could have just considered the stripped string and then we have saved few delete operations. So we will never need a delete operation.

=== What is the case for addition?

There are two possibilities:-

1. We have sub-string SS. Then we add at beginning some character which was actually at the beginning of sub-string SS in the original string S. It's similar to the previous case will not be necessary as we can avoid this operation by adding to the sub-string originally.

2. We have added a completely different character. Now that does not match that of original string. so it will be added. But if we think carefully...isn't it an change operation?

S = ABBCBA

t = BBCD

Now in case of sub-string "BB" we will add 'C' but it is already in the string immediate next to the end of the string..so why don't we consider sub-string "BBC"

Now when considering "BBC" we will try to add 'D' and there is no match with the immediate next of that 'C' in string S. So we will add it. But this add is equivalent to a change if we consider sub-string "BBCB".

And also we don't need to consider any string < |t|. So we have to check all |t| length sub-strings.

Now it indicates we use |t| length sub-strings and then compare with the target t. Is this ok? Ah we have missed a small case.

for example:- S = ABCD T = XA How we will check?

   [AB]CD   A[BC]D   AB[CD]
    XA        XA        XA  ANS = 2 --->WRONG
   But we can do it in 1.
    [A]BCD  --> prepned X..[XA]. 

So why does this happen? We have to check whether A matches with or not with every position in the array. We were not doing it earlier. How to do that?

  ##ABCD##
  XA
  ##ABCD##
   XA
  ##ABCD##
    XA
  ##ABCD##
     XA
  ##ABCD##
      XA
  ##ABCD##
       XA

Well this way we checked every character against every character. So by this we are sure that we won't miss anything.

This is what I got from the problem..anybody is suggested to clarify or modify this idea to have a better explanation. Thanks.

EDIT: 1. I dont care about upvote but I wrote this so that I can verify my understanding and also to provide with a English version of the editorial on my own words. Whatever it is just point out if there is any error on what I said? Thanks. ****

Why is it taking 30-40 mins to judge a solution?? Anybody knows any reason or how long will it be like this?

Edit: Thanks to Mike and his team.

Is it because of some maintenance issue? It has returned before. As some user mentioned.

In the last Div-2 Contest Div2E can be solved using MO's sqrt decomposition.

I couldn't solve the problem that day. I read the editorial and understood it.

The thing left to do is to implement it.

While implementing I realized the most difficult part of the algorithm (or as it seems to me!). And it 2 things:-

a) The intilization of Mo's left and Mo's right .(ML and MR) respectively. b) Movement of them.

Now I couldn't get correct answer even for the given test cases in my computer. So I move to see the code.: There are 2 ways people solved the problem:-

a) some of the coders initiliazed ML=1,MR=0. and then go on adding and removing as required. b) some initialized ML=0,MR=0 but cnt[0]=1..(occurences of 0 is 1) and then solved it.

Then I observed that no movement of pointers are different.

End result: I am utterly confused. My question is

1. For query [l,r] we have to be sure that pref[l-1] to pref[r] must be present in this problem. Now how can I write the code keeping in mind the range and should I follow 0 based or 1 based. How to do this? Is there any idea/trick/concept that will clear this MO's pointer movement?

Can someone provide a general idea on left and right pointer movement? (post incremment ,pre increment,..,initialization whole thing made me confuse..I am trying for 3 hours...reading the tutorials..but I can't write the code for pointer movement on my own..)

Thanks.

Note: Somebody please explain to me. No matter how dumb this question sounds to you.

I have tried these problem.(link). But I am stuck still now after getting the hint (Dijkstra+ BFS). Can anybody please provide me with an editorial(algorithm)? What do we need to do to solve this problem?

I mean it would be better "if some one provides me with the thinking process". Thanks.

I have tried to solve this... I have tried Brute force. Can anybody provide a intuitive idea — how to solve this. The thing is here we can't divide the range in blocks as the update in the array are not consecutive. This is my first sqrt decomposition problem.

Problem statement

Editorial

For articulation point and bridge these following code is shown in "Competitive Programming-1: Steven Halim" (yes edition-1 because it is free):-

void articulationPointAndBridge(int u) {
  dfs_low[u] = dfs_num[u] = dfsNumberCounter++;      // dfs_low[u] <= dfs_num[u]
  for (int j = 0; j < (int)AdjList[u].size(); j++) {
    ii v = AdjList[u][j];
    if (dfs_num[v.first] == DFS_WHITE) {                          // a tree edge
      dfs_parent[v.first] = u;
      if (u == dfsRoot) rootChildren++;  // special case, count children of root

      articulationPointAndBridge(v.first);

      if (dfs_low[v.first] >= dfs_num[u])              // for articulation point
        articulation_vertex[u] = true;           // store this information first
      if (dfs_low[v.first] > dfs_num[u])                           // for bridge
        printf(" Edge (%d, %d) is a bridge\n", u, v.first);
      dfs_low[u] = min(dfs_low[u], dfs_low[v.first]);       // update dfs_low[u]
    }
    else if (v.first != dfs_parent[u])       // a back edge and not direct cycle
 [1]     dfs_low[u] = min(dfs_low[u], dfs_num[v.first]);       // update dfs_low[u] <---------------
} }

My doubt is [1]..In this line why are we using

1. dfs_low[u]=min(dfs_low[u], dfs_num[v.first]); Can anybody explain this..why are we using the dfs_num value not the dfs_low value in case of visited nodes? I mean what is wring with dfs_low[u]=min(dfs_low[u], dfs_num[v.first]);?

2. Second thing is when we are going in line [1] can't we say for sure that the v->first's dfs_num is smaller than dfs_num of u? (dfs_num is also considered as the dfs discovery time).

3. Third one is for verification--- In the bridge discovery case the condition is if (dfs_low[v.first] > dfs_num[u]) because we have to find another node among the child of u whose dfs_low is strictly greater than dfs_num otherwise we will select a single node as an edge --which is wrong! Is this line of logic correct?

Note: If anybody has any key insight in this algorithm he/she may help others (me also) users by posting it.

UPD-1: I have studied and searched about bridge tree and bridges. But no tutorial clearly states the answer of my questions. So anybody having any idea is requested to post here.

It's almost a year I am in competitive programming, doing problems here and there. I realized that I have to solve problems to be good at this. Now what happened to me repeatedly is this-

1. Be in a virtual or actual contest.
2. Try hard.
3. I can only solve 1 or 2.
4. Contest ends.
5. Check the editorial for unsolved ones.
6.  **Can not understand the idea or feel confident enough to solve the problem.**
7. Try an hour to understand.
8. Leave it...

I have found that for this reason I an still green and I have to write this. In case of practice problems I take this approach

1. Read the question.
2. Understand and try to solve.(I try exactly for 10-15 mins..)**(Is this correct or should I try longer?)**
3. If I can't solve then I read the editorial.
4. Can not understand the idea or feel confident enough to solve the problem. 
5. Try an hour to understand.
6. Leave it...

The problem is similar here also.

My question is

1. What should I do? I mean is there any strategy to overcome this (How can I understand editorials)?
2. How much time should I give to a practice problem?

I am trying to search answer of these questions for probably a year. I want to grow but how can I if I don't understand the editorials? I want to know the art and be a "RED" someday. [For example I can't understand the #509C and #156C (div2) problems editorials..these are only the last 2 of hundreds of editorial I have read in a year.]