I_love_Tanya_Romanova's blog

ACM ICPC Practice Contest invitation — easy prizes!
By I_love_Tanya_Romanova, 9 years ago, In English

Hello everyone!

I want to invite you to another contest at HackerEarth, and this time it is not Clash :) But ACM ICPC Practice Contest. Contest is scheduled on October, 4.

You'll face ICPC-style problemset with quite a lot of problems) Contest is focused on ICPC preparation, so are the rules — it will be 5h long team event with ICPC scoring rules (only full solutions count, ranking by number of problems and then by penalty time, giving penalty for wrong submissions), and only C/C++/Java in list of allowed languages.

Problemset was prepared for you by FatalEagle, memset123, pkacprzak, shef_2318, xennygrimmato, Sokolov and tanmaysahay94. There will be also statements in Russian, prepared by shef_2318. After contest editorials by pkacprzak will be presented to you. I was working on this contest as a tester. Also I want to thank to belowthebelt for technical help and doing his best on fixing all issues, processing all our feedback and improving HackerEarth platform)

I believe that problemset is quite easy, at least for experienced contestants. And I hope it is actually easy, not just another "I will say that problems are easy to make you feel even more miserable". If I am wrong — please exuse me :) If your team is strong one — it will be a nice warm up for you; otherwise I believe you'll find some challenging problems there and learn a few new things.

Another good reason to try this contest — there are some nice prizes. Easy problems — easy prizes, right? :)

The top 3 Indian teams in this contest, who also qualify for ACM ICPC Regional will have their ACM ICPC travel expenses reimbursed.

The top 3 teams will get $100, $80 and $50 vouchers respectively.

Good luck, waiting to see you in scoreboard!

UPD. Congratulations to winners!

Top3 teams:

1) Anta (anta)

2) bloody_unko (uwi, sugim48)

3) Lewin (Lewin)

Top3 Indian teams:

1) FacelessMen (alecsyde, gsahil, abhilak)

2) DAFruitsSalad (yashkumar18, Sumeet.Varma, kuldeeppatel)

3) Rex_Regum (usaxena95, aditya1495, harshil)

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

»
9 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Shall teams use one PC or we can code in parallel?

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

    You should act like you have 1 PC. This is ICPC practice — I believe that part about one PC should be intuitively obvious for you, unless you are representing some region with very strange rules (like GNY).

    I would say that team can use more than one PC — for example if you don't have printer, you can use another PC to read statements from it, or to look for bugs in your code (like it has been printed — without compiling it etc.), or maybe you are writing it from different places, then you can share access to one PC, imagining that it is your contest PC (while in fact everybody will be accessing it from his own machine); but coding in parallel is clearly a violation.

    I believe all of you are going to play fair:)

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

      I believe all of you are going to play fair:)

      Today, I returned from a (physics seminar for secondary schoolers) camp. During one game, there was a place where people who "died" went until they were revived; they were forbidden to communicate in any way (a lot of info in that game was supposed to be secret). It worked roughly like this: using their phones and refusing to give them up. Fortunately, they found a different way to pass time soon enough or it would've screwed up the whole game...
      With this anecdote, I'm trying to say that people just tend to cheat.

      If a rule isn't enforced at all, then it's a suggestion. After all, it doesn't make sense to tell people "if you don't simulate ACM rules, you're cheating, and you're going to be punished by nothing and nobody's going to know", as compared to "look, you aren't going to gain anything by cheating — the prizes are for those who gained skill by making it a habit not to cheat — so why not make it really an ACM practice and use one computer?". Even so, chances are that there will be cheaters, but well, they truly aren't going to gain much that way, so whatever.

      Not like it matters to me... since I'm going to try it unplannedly and from an internet cafe...

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

Can anybody please tell me how to create a team in hackerearth ?

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

Is it possible to look at the full standings board (not only first 5 problems)?

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

    Right arrow or the bottom scrollbar (it's really at the bottom of the page, you need to scroll down to see it) does the trick for me.

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

What's the running time of solution for "Legendary Graph" problem? I guess simple is not passing.

I thought about the solution based on randomness of input, but I'm not sure if it passes or not.

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

    My solution's running time is , and it does not use randomness of input (PRNG's purpose is to avoid 100MB input files). I didn't think of any solutions that used randomness of input, so if you have one it would be interesting to hear.

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

      My guess is: if you randomly add edges to the graph, then every time when the new edge is merging two different components these components have almost the same size.

      If the guess is true, then you can maintain a structure that contains O(number of segments in the component) elements in it and can calculate the sum of a segment in O(log) time.

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

        Merging such structures sounds like the hard part. If you use segment trees, it would still take total time time to merge, right? Each element uses time to update and it is updated times in total. If you had such a structure that can do this fast, then I think the trick of merging small component into larger component would work fast enough too.

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

          Splay tree works right? I don't know how to prove this, but merging splay tree into splay tree in the proper order works extremely fast. in fact,

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

            That is not my solution, but you can code it and submit it. I have a feeling that the constant might be too high for a splay tree, even if it is theoretically fast.

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

      For truly random behaviour of given randomInt() we can expect only one very big connected component (with size O(n)) and not many medium components (let's say size about 100 - 1000). I analysed it with program using rand().

      For one big component we can keep a segment tree with two operations: add  + 1 to interval, find sum on interval. We deal with smaller components by brute force. Or maybe we should keep tens of segment trees, each for component of size at least e.g. 70. Then we are left with very small other components and brute force works even faster.

      During a contests I made some bugs or my implementation of seg tree is too slow — because even without brute force for smaller components I got TLE.

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

can anyone please tell me what is wrong with my solution for problem 2 ( Sonya clears the array ) . code

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

    got AC with this code . All time i was debugging my Call function but main problem was in my DP call . I didn't handle odd call :(

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

The power of bitset for "Game of sweet".

inline int Solve() {
	sort(a, a + n);
	bitset<N> s;
	s[a[1] - a[0]] = 1;
	bitset<N> ans;
	ans = s;
	for(int i = 2; i < n; i++) {
		int dif = a[i] - a[i - 1];
		bitset<N> ns = (s << dif);
		s = ns;
		s[dif] = 1;
		ans |= s;
	}

	return ans.count();
}
→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it +13 Vote: I do not like it

    My bitset solution was even more naive :P

        bitset<100000 + 1> bs;
    bool zero = false;
    while(N--) {
        scanf("%d", &a);
        if(bs[a])
            zero = true;
        bs[a] = true;
    }
    if(zero)
        ct = 1;
    for(int i = 1; i <= 100000; ++i)
        if((bs & (bs >>i)).any())
            ++ct;
    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +6 Vote: I do not like it

    What is the complexity for << operator in bitset?

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

Hey guys,If anybody has got some time please do me a favour.Please mention the difficulty of problem set like problem 1-> Jumping champa was like div 2A and Big travel Div 2C like that.So that I can assess myself.It would be even better to hear from problem setter.Thanks

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

How can we find our team in standings ?!!

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

Here's the link to the editorials of all the problems, curated by pkacprzak: http://hck.re/aCkfXM :)

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

Before the prizes are distributed and sent, we need to clear the mess regarding the final standings of the contest. Everyone who was watching the contest, or took part knows what happened in the 10th question (Game of sweets!) — the language of the question was not the desired one by the team involved, which resulted in a lot of teams interpreting the question differently than they should have — and ended up submitting a lot of apparently wrong solutions — some of them were correct according to the interpretation of the problem statement back then.

So, to sort that out, we decided to manually evaluate the submissions for the top people in the ranklist — by checking if their solution passes on either of the two interpretations of the given problem and then update the rank list for the top 3 people and the top 3 Indian teams!

The final standings will be updated in the post soon! :)

→ Reply