Croc Champ 2013 — Round 1
By HolkinPV, 12 years ago, translation, In English

Good day)

Soon is coming Round 1 of the All-Russian Programming Championship CROC-2013. Contestants who gain a score equal to the 400-th place finisher score or greater will advance to the Round 2 (also you need to gain positive score).

Round will be held by usual Codeforces rules (with hacks and decreasing values of the problems). During the round the problems are judged only on pretests and system testing will take place after the end of the contest. The pretests do not cover all possible cases of input data, test your programs carefully.

Before the end of the round it is strictly forbidden to publish the problem statements/solutions/any thoughts and ideas about them elsewhere. It is forbidden to talk about the problems, discuss the statements, solutions and so on.

The problems were prepared by the group of authors: Pavel Kholkin (HolkinPV), Gerald Agapov (Gerald) and Michael Mirzayanov (MikeMirzayanov). I will add that our team have already prepared for you qualification round and answered the questions during the whole competition. Traditionally thanks to Mary Belova (Delinur) for translating the problems.

UPD1: The problems are sorted by increasing of estimated difficulty. The score dustribution is decided to be not standard a little bit : 1000, 1000, 1500, 2000, 2500.

UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated.

We wish all the participants good luck and successful advance to the next round of competition.

Announcement of Croc Champ 2013 - Round 1
  • Vote: I like it
  • +40
  • Vote: I do not like it

Comments Comments (134)
| Write comment?
»
12 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Seems like really tough competition.. Did you mean under 400 amongst all Red,orange and purple coders ?

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

Will the round be rated?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    "UPD2: due to the large number of participants, it is decided that it will not be able to participate out the competition. For official contest participants the round will be rated."

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      So what does a official contest participant mean?

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 5   Vote: I like it -15 Vote: I do not like it

        it's rated for both Divisions.

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

          I guess it means all eligible registered participants.

          When a Div2 contestant participates in a Div1 contest, he is considered unofficial, because although he registered for the contest, he is non-eligible to participate in a Div1 contest, and vice versa.

          → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +5 Vote: I do not like it

          In my view, all the participant who read the problem will be rated, as normal CF contests.

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +28 Vote: I do not like it

            You need to submit something to be rated, be it normal CF round or competition one

            → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How would the rating be calculated for both division 1 & division 2 participants ?

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

how many rounds will this series of contests have，is there any T-shirts to give the winners ?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -26 Vote: I do not like it

    It seem that there's only one round.

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

The problems will be more suited for div1, div2 or half way? :)

→ Reply
»
12 years ago, # |
  Vote: I like it +21 Vote: I do not like it

How to register when registration is private? It seems too private for somebody to enter :)

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

    I have the same problem. I have to register now because I will not have internet acces until the start of the competition

    → Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

I receive an Email tell me that I need to register on Codeforces for Round 1, but it seems that I cannot register because the registration is private. Did I really need to register or it will be done automatically?

→ Reply
»
12 years ago, # |
  Vote: I like it +15 Vote: I do not like it

"Registration is private", does it mean that all participants who passed qualification round will get registered automatically?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    Well, when I click "register now", a message box "The contest does not allow self registration" pops up. So I suppose that the registration will be automatically done.

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

      I hope

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      I hope so because our dorm cut the wired internet access at 23:00(UTC+8), 30min before the round start, every workdays and it will be very crowded at the public WIFI, which cause it crash frequently.

      → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

"For official contest participants the round will be rated" ... for only the contestants the round is rated ??? am I misunderstanding ???

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    it is decided that it will not be able to participate out the competition.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      if there is no participant out of the competition then all the participants are official so now whats the need of the "For official contest participants the round will be rated" statement ? they can simply say "this round is rated"

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      haha you quoted that sentence as if it were in correct English :D

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If there is problems with the registration I suggest to open the registration durig the contest. Because not all of us can register. I am going to miss school for the competition. I will be home at the 4-5 min from the start. I will mis the competition if i don't register now.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Registration is fixed now.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -23 Vote: I do not like it

Edit

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +66 Vote: I do not like it

    Why some of you cares so much about the ratings calculations and the score distribution? Every round about ten such messages appear.

    What will change if your rating changes will depend on only Div-2 or both Div-1 and Div-2 coders? Won't you participate in one of these cases?

    → Reply
»
12 years ago, # |
  Vote: I like it -19 Vote: I do not like it

put off 5 minutes?

→ Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

Lots of hacks specially Problem 4.

→ Reply
»
12 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Could anyone tell me what's wrong with this generating code for problem E? I kept hacking and got "invalid input". Making the right input specification is so tough :(

int main() {
  int n = 1e5,Q = 1e5;
  printf("%d %d\n", n, Q);
  for (int i = 0; i < n; i++) {
    printf("%d", 100);
    if (i == n - 1) printf("\n"); else printf(" ");
  }
  for (int i = 0; i < n; i++) {
    printf("%d", 100);
    if (i == n - 1) printf("\n"); else printf(" ");
  }
  for (int i = 0; i < Q; i++) printf("%d %d %d\n", 1, 1, n);
}
→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    what is error message?

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    Looks like you forgot to output request's type in the last for

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

    Did you mean printf("1 %d %d %d\n", 1, 1, n); in the last line?

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

      Oops, I forgot that the 1-typed query needs three parameters. Thanks everyone :). (I need to practice generating input more regularly).

      → Reply
»
12 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Just one second to click submit button for problem E. :|

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

    And one second for my C, please :(

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

      Thanks God! Mine was wrong :)

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

    Just one second to click submit button for my 100% corect sources for A, B,C,D,E :/

    → Reply
»
12 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What is the solution for D? Or is it just a DFS per query?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I use disjoint set, with total complexity O(K * (N + UnionSet cost)).

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      How do you achieve that complexity? Don't you need to traverse the edges that are not taken? I mean, isn't it O(K * (N + M))?

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

        oh yes, sorry I miss calculation :). N that I wrote first, I mean is M, total edge not total vertex.

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

        Given M = 10000, K = 20000, will 2*10^8 survive?

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

        You can make it faster by pre-computing spanning forests for all edge prefixes [0..i] and all edge suffixes [i..N]. Then you only need to merge two disjoint-set forests for each query.

        That brings the total cost down to roughly O(N * (M + K)).

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +6 Vote: I do not like it

          How could one merge 2 DSUs ?

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

            I iterated through every (vertex: root) pair in one forest and merged them in the other forest. It seemed logical, but I have no idea if it's actually correct or not...

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

              OK, it seems to be correct.

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

            It can be done in O(N) by DFS using only edges v — parent[v].

            → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
              Vote: I like it +8 Vote: I do not like it

            each DSU has O(n) edges, just use them.

            → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 4   Vote: I like it +4 Vote: I do not like it

    DFS per query:

    void dfs(int v){
      used[v]=true;
      for (int j=0;j<g[v].size();j++)
          if (!used[g[v][j].v] && (g[v][j].ind<l || g[v][j].ind>r))
             dfs(g[v][j].v);
 };
    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      It fails on half of hacks. Probably systest will fail most of them.

      I solved in such way. Let's have to sets of edges. First is edges, which connect vertexes, which is not connected by edges with less numbers. Second is edges, which connect vertexes, which is not connected by edges with greater numbers. There sizes is O(n) and other edges is not need. So we can answer query in O(n) time.

      It's easy to implement this solution with dsu.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +15 Vote: I do not like it

        thanks for your response,I am interested why this solution get TLE,I only changed positions and get ac:

        TLE41:

        if (!used[g[v][j].v] && (g[v][j].ind<l || g[v][j].ind>r))

        ACCEPTED:

        if ((g[v][j].ind<l || g[v][j].ind>r) && !used[g[v][j].v])

        why system test is so strictly what is difference ? :(

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it +17 Vote: I do not like it

          Consider "if ( A && B ) {}" code. If A is false, then B isn't checked. B is checked only when A is true. So if we know that A is false more often than B is false, it's better to write "if ( A && B) {}", otherwise "if ( B && A ). In our case (g[v][j].ind<l || g[v][j].ind>r) statement is false more often than !used[g[v][j].v] is. Therefore, if ((g[v][j].ind<l || g[v][j].ind>r) && !used[g[v][j].v]) is the best way.

          → Reply
»
12 years ago, # |
  Vote: I like it +36 Vote: I do not like it

CROC's English is very very difficult and long... I took hard to read even using translation machine.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

Very nice problem D. I knew my solution in wrong, but I've locked my code and hacked 7 people!!

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

    Lucky you, I wanted to do the same but tourist hacked me first :(

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +21 Vote: I do not like it

      It can be considered a privilege being hacked by him. :)

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

    Could you tell me what's the tricky case for problem D ?

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

      Just a random test with 500 vertexes and 10000 edges and 20000 queries that all of them are : 1, 10000

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

        if N = 2, M = 2, edge are = {1, 2} {1, 2} and the query is {1, 1} The answer is 1 or 2 ?

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

          I think there could not be any multiple edges.

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

            There could be multiply edges.

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

            "Note that a pair of computers can be connected by multiple cables." But the problem say so. .

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              12 years ago, # ^ |
                Vote: I like it +1 Vote: I do not like it

              Very good! now I think my solution besides time limit, will get wrong answer!! :D

              → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Cool strategy..!

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

What's the solution to C and E? Thanks.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    for C the most important thing you should consider is that you can obtain the hole string by determining the length of each of 4 number O(3^4) and the material of the first half of the string O(n^(half of the length <=6)) and then you should check whether it is legal or no for more info see my C++ code : 355108 for E you should use segment tree data structure (read about it here )segmnet tree and keep for each node of the tree that what is the last copy that contains this node and then easily find the answer for each query if you need more info see my C++ code : 3550844 I hope it will be useful for you.

    → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Too strange, why I can't see the system testing? Are they really testing now?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    you sure you know what "pending" means? xD

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +6 Vote: I do not like it

      You mean there are some delays and they are just waiting?

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

        Yes and no. the aren't waiting (its pointless isn't it?), they most likely are master basing

        → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +136 Vote: I do not like it

→ Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Why testing won't start?

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please tell me when i can submit my solution for problem 5??? and where i can do that???
my brain is exploding, because i submitted my code 5 seconds before the end, and because of the stress i had, i made a little mistake and 10 seconds after i noticed that!! if i submitted that my score was about 1400 and i would advance to the Round 2.
my brain is exploding now! help please :(

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

    well my story is more tragic. Cause of Iran’s f*** network I wasn’t able to submit my E code in 1:10 when I have already submitted A,B,D. My network re-concocted after the contest. what should I have to do ???

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

    excuse me! i mean 4500(not 1400)! it's because of my brain!

    → Reply
»
12 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Hey guys, Is there any one to start system test? Mike? Gerald? Pavel?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    it seems there is no one to start system test

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +16 Vote: I do not like it

      It will be started soon. Please, a little patience.

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it +2 Vote: I do not like it

        Is there any technical problem? I Can't understand this to much delay.

        → Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

One hour of pending system test should be something unusual. In that case, we contestants all expect some announcements/explanations from admins :(

Edit: ok, just saw Mike's comment :)

→ Reply
»
12 years ago, # |
  Vote: I like it +204 Vote: I do not like it

Meanwhile in CodeForces HQ:

→ Reply
»
12 years ago, # |
  Vote: I like it -126 Vote: I do not like it

Plus this comment to see how many people are waiting for the system test. :D

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +121 Vote: I do not like it

    Okay, keep downrating it :D. I'll take the abs :D

    → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 2   Vote: I like it +14 Vote: I do not like it

    We can minus your comment to see how many people are waiting for the system test. Same result :D

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -20 Vote: I do not like it

    you wanted to say "minus this post to see how many people are waiting for system test"

    → Reply
»
12 years ago, # |
  Vote: I like it -8 Vote: I do not like it

I'm staying up for the system test! Please get this done ASAP, I want to sleep!!

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it -19 Vote: I do not like it

Well,I have to thanks all Codeforces team. They taught me what does error 502,504 and server busy means :D . I was kidding but I really expect codeforces to be more faster in this contest :D.

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

no wonder tourist completed the contest in just 35 minutes.

3000+ on the cards.

→ Reply
»
12 years ago, # |
  Vote: I like it +9 Vote: I do not like it

haha, in my B i had "unknown toplogy" instead of "unknown topology" in one minor case, WA on 38 :-))

→ Reply
»
12 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

in problem D: Why was K limit so low?? some people got AC with O(mk), but some people didn't.

the problems were are implementation and coding and non-algorithmic. and very slow system testing I did not like this contest

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

    More than 1200 contestants, it isn't slow system testing!

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      it is really slow. just remember last 3 contests, this contest had less contestants than them.

      → Reply
    • »
      »
      »
      12 years ago, # ^ |
      ← Rev. 2   Vote: I like it -39 Vote: I do not like it

      yes it is! most div 2 contests more than 2000 people participate and it takes less than 30 min and i'm not just talking about system testing, it took about an hour for the system testing to start

      i think this round should be unrated for these reasons:

      1. the contest was uneven : i see a lot of RED contestants which their ranks is more than 300.

      2. the problem difficulty's were close to a div-2 contest

      3. Problem D is very unfair and they could have set limit of k to 10^5 so people know that the MK soloution would not get AC

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

        I don't see how it's unfair. All had same chances

        → Reply
        • »
          »
          »
          »
          »
          12 years ago, # ^ |
            Vote: I like it -17 Vote: I do not like it

          Because there are participants who got Ac on O(mk) soloution And if the k limit was higher, people would think on another soloution

          → Reply
          • »
            »
            »
            »
            »
            »
            12 years ago, # ^ |
            ← Rev. 2   Vote: I like it +12 Vote: I do not like it

            If the k limit was higher, then many coders would have discarded the O(mk) solution.

            But it isn't. The problem statement clearly said k <= 10^4, so, if a coder doesn't realize that the O(mk) solution will work, it's his fault. I don't see how it can be unfair. The constraints were very clear.

            → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
          Vote: I like it -6 Vote: I do not like it

        agree with your reasons, specially with third one.

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

        Anyway it's too late! The ratings have been updated

        → Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it -7 Vote: I do not like it

    I have the same problem, One of my friend's code got acc although his code had to be very slower than mine.

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    I got back to division 2 and didn't make to the next round because of this So I am completely in agreement with you.

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

This is translation of my russian answer.

We carefully try to make constraints more fair. Our naive solution get TL on our tests. All (except one, that isn't written optimally) our correct solutions passed with 3times reserve. So we decide that our constraints is very good.

Here I should say that polygon shows that all TL solutions fits into 2TL. Buy I didn't notice that thing. That's my great fault.

I truly apologize for this fault. We will try not to make such faults.

→ Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Would it be possible to hold the CROC rounds on Sunday instead of Monday? For US competitors who work or are students it's difficult to compete in a round that takes place at 11:30 AM EST on a weekday. I was able to participate in round 1 (and qualify for the next round), but I don't think I will be able to participate in the 2nd round.

I don't think this will conflict with the TopCoder Open, or make competing more difficult for participants in Asia or Europe, so maybe it's possible?

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    People may already have plans based on published schedule. Also Codechef Cookoff is scheduled for Sunday

    → Reply
»
12 years ago, # |
  Vote: I like it +4 Vote: I do not like it

My solution to problem D was bfs for each query having a total time complexity of O(Q * (E + N)), why didn't it pass the time limit? M = 10000 N = 500 Q = 20000 Total number of calculations would be around 2*10^8, I have accepted many problems here in codeforces with the same number of calculations? I had the idea of using DSU but it was a little bit harder to implement and to prove, For further contests how can I be sure if the solution will pass or not whit this number of calculations?

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

    I do the same too :(

    → Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    When you're that near the limit, there's no guarantee it will work in time. It's just your decision if you want to take the risk and go the easy way, or spend some time thinking a faster solution.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +28 Vote: I do not like it

      You can always use "Custom test" to approximate the running time in worst case. I first submitted a naive solution. Then I used this and figured out it was too slow and resubmitted it later. (Tips: there's a limit for input size in "Custom test", however we only need to measure the running time, so simply assign some random numbers directly in the code itself)

      → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In question D: Can somebody tell me why this submission using dfs worked. 3545286 and mine using bfs is giving TLE. 3551854 Thanks in advance..:) KrK

→ Reply
  • »
    »
    12 years ago, # ^ |
    ← Rev. 3   Vote: I like it 0 Vote: I do not like it

    R_R_ You hacked in during contest. Comments please.

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

    The constant factor in your solution seems to be a little higher. You're using two arrays (color and marks), when you only need one (one that states whether the node has been assigned a component). Try using only the color array and see if you get it AC.

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

      3552076 Still not..

      → Reply
      • »
        »
        »
        »
        12 years ago, # ^ |
        ← Rev. 2   Vote: I like it +1 Vote: I do not like it

        I think it doesn't work in time because you are using stl queue, which might allocate memory somehow slower when compared to static array used as queue (see 3552315)

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

          Haha.. That was really awesome..!! Never thought using STL queue will make it this much slower..:P

          Thanks a lot. ondrah..:)

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

          ondrah Hey, the one you used in your submission is not BFS. It's is still dfs because you actually implemented a stack using array.:)

          Even queue implemented through array is not working. See 3553686

          → Reply
»
12 years ago, # |
  Vote: I like it -29 Vote: I do not like it

292D - Connected Components

can anyone tall me why is [ if(!fix[v[i][j].fi] && (v[i][j].se<x || v[i][j].se>y)) ] this wrong and this [ if((v[i][j].se<x || v[i][j].se>y) && !fix[v[i][j].fi]) ] true?????

→ Reply
»
12 years ago, # |
  Vote: I like it -58 Vote: I do not like it

such a long questions . it was hard to translating specially for persons that their english are not too good .

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it -47 Vote: I do not like it

    I made a mistake . It is the participants' duty that have a good English .You can give the questions somehow you want . at last thanks for the contest .

    → Reply
»
12 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Round 2 will be rated for people who did not get in the first 400 in round 1 ? Thanks.

→ Reply