inzva's blog

By inzva, 5 years ago, In English

Attention: The Grand Contest 2019 starts on June 22, 2019 at 10:00 am!

This is the first international programming contest organized to take place on Saturday, June 22, 2019 at 10:00 am (UTC + 3), by inzva and in collaboration with algotester.com.

We are inzva, a non-profit organization based in Istanbul, Turkey; bringing Turkish computer science students, AI and Algorithm enthusiasts and academics together.

We invite you to test yourself and your team at the Grand Contest on Saturday, June 22 at 10:00 am.

20 best teams will get prize t-shirts for each team member. The contest duration is 5 hours. The allowed programming languages are C/C++, Pascal, Java, C# and Python.

The Grand Contest is an ICPC-oriented contest in which experienced university students will have the opportunity to test their skill level in teams, and prepare for international contests. It will be onsite at places such as Istanbul, Lviv, Belgrade and Minsk; as well as taking place online.

The round will be held according to the rules of ICPC. Please note that you must be in teams of two or three students. Do not forget to register for the contest..The registration will be closed 5 minutes before the contest.

If you have any questions, please feel free to send an email to [email protected].

Good luck and have fun!

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

| Write comment?
»
5 years ago, # |
Rev. 2   Vote: I like it +15 Vote: I do not like it

Me and my teammates ykaya and KayacanV will participate. Hope to see you guys in the contest.

»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Do you have to be eligible for ICPC to participate? Can a team use multiple computers?

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

    No, you don't have but you can not use multiple computers.

»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

Are high school students eligible?

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

    yes, of course. Just join as a team.

»
5 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Official sites are: - Lviv - Minsk

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Are online participants eligible for prizes?

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

101 team registered. Good luck!

»
5 years ago, # |
  Vote: I like it -12 Vote: I do not like it

Are unofficial teams eligible for prizes? I accidentally registered my team as unoffficial :(

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

How to solve F ?

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

    F

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

    Binary search the answer. Now we have 1 — we can take, 0 — we can't take.

    Firstly, let's solve this problem when we have exactly N zeros and N ones. Now each move is removing 00 from one array and 11 from the array.

    Lemma:
    The solution exists iff
    1. We can remove both arrays separately by removing 00 or 11 on each move.
    2. We can make the last move in first array 00 and in second 11(or vice versa). For example, if array is equal 0110 we can't make last move 11. So if both array are 0110, the solution doesn't exist.
    Let we have 2 types of brackets for each consecutive group of 0 or 1 of odd length. The last move can't be 11 iff whole array is enclosed in brackets of type 0.
    To prove this lemma we can show that for each good state we can make a move such that smaller arrays will be also good.

    Now let's solve the original problem when the number of 1 can be greater than N. Let's find for each array separately the minimum number of 1 that should be changed into 0 such that this array is solvable and the last move is 00 (same for 11).
    Such problem can be solved with dp[prefix][stack_size(for bracket sequence)][first_element_of_stack][last_element][number_of_same_last_elements_modulo_2][was_ballance_0]

    Total complexity is $$$O(n^2 \log n)$$$

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Where and when will we be able to see the whole scoreboard?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice tasks, I really like problems D and E.

How to solve I ?

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

    You can modify so that the permutation isn't necessary, the problem becomes how many ranges $$$[l, r]$$$ such that vertices from $$$l$$$ to $$$r$$$ make a connected component.

    Iterate over $$$r$$$. We keep the number of connected components in each range $$$[l, r]$$$ for every $$$l$$$. By doing this, you can easily update from $$$r - 1$$$ and find the number of $$$l$$$ such that the number of connected components in range $$$[l, r]$$$ is 1 using a segment tree.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it +8 Vote: I do not like it

    Remap the vertices, and forget about permutation.

    Let's orient every edge so it goes from A to B, where A < B.

    Let C[i] be incoming degree of vertex $$$i$$$.

    Let's look at some prefix [0,r]. We can see that $$$\sum_{i=0}^r C_i <= i-1$$$ and it's a connected subtree if equality is achieved. Proof comes the fact that each edge in $$$C_i$$$ is from some $$$j < i$$$ that is in our prefix as well.

    Let's build a segment tree $$$s[i] = i - \sum_{i=0}^r C_i$$$. For current start answer is number of minimums if those minimums are equal to 1. Moving to the next starting vertex includes subtracting 1 from each value (from $$$i$$$) and updating $$$C_i$$$ and $$$s_i $$$ by removing edges from current vertex.

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

    Can you please explain how to solve problem D and E??

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

      Sure, I can explain solutions for the problems in a few words.

      For $$$D$$$

      • The biggest value is the most important. Let's say the biggest value is $$$x$$$, and all other values are $$$x-1$$$, the player who took $$$x$$$ will have at least $$$N^x$$$ points and other one will have $$$(N-1) \cdot N^{x-1}$$$ which is smaller value.

      • If there is only one biggest value at position $$$i$$$. Than game is equivalent to the NIM game with piles of sizes $$$i-1$$$ and $$$N-i$$$. If there is for example three bigesst values at positions ($$$i$$$, $$$j$$$, $$$k$$$), the game is equivalent to the NIM game with piles $$$i-1$$$, $$$j-i-1$$$, $$$k-j-1$$$, $$$N-k$$$. Reasoning behind this: first we will remove subarrays without biggest value, and who removes last of that smaller values he will take smaller amount of the biggest one.

      • The trick is when we have even amount of the biggest value, then we will try to find out the biggest value $$$y$$$ which appears odd amount of times (because all values $$$x>y$$$ will be taken same amount of time from both of players). Now all values not smaller then $$$x$$$ will be "separators" for the piles. In case all values appears even amount of time result is "Draw".

      For $$$E$$$:

      The main observation is that in case we satisfy condition at least one painting for each person, we will have answer for sure. We can repeat next procedure untill second conditions is not satisfied for all person:

      • Find person $$$i$$$ which has smaller than half of painted interval

      • Paint $$$a_i$$$ more stones in interval $$$[l_i, r_i]$$$ — it is possible because I supposed that I satisfied first condition on correct way, so in case half has not painted yet and I have painted stones by each person at least once, than $$$2 \cdot a_i < r_i - l_i +1$$$.

      For satisfying first condition we can try next greedy. Go stone by stone from $$$1$$$ to $$$n$$$ — paint current stone by person which has still some unpainted stone (from its first $$$a_i$$$ stones) and its right end of interval is leftmost.

      For all this stuffs you need structures like set and Fenwick tree. This is my code. Complexity of solution is $$$O$$$($$$n$$$ $$$log$$$ $$$m$$$)

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Who gets t-shirts? Top 20 or 10

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

    Top 20 for onsite teams and top 10 for online teams. But I don't know are unofficial teams eligible for T-Shirt ?

»
5 years ago, # |
  Vote: I like it +2 Vote: I do not like it

I saw only other countries rank list in my case. My team came 9th there so are we eligible for T shirts?

»
5 years ago, # |
Rev. 2   Vote: I like it +33 Vote: I do not like it

Are you guys really coded I in 3 minutes? -_-

»
5 years ago, # |
  Vote: I like it +16 Vote: I do not like it

when will the problems be available for practice or are they already available?

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve J?

  • »
    »
    5 years ago, # ^ |
    Rev. 6   Vote: I like it +8 Vote: I do not like it

    I used segment tree. Let us say the interval is l to r. I made 2 precomputations, the value of bracket sequence from left to right and right to left, adding i to $$$f_i$$$ if it is ( else -1. Same for right to left. Now if I have to reverse l to r. The dip in value from r to l (that is right to left) should not exceed $$$f_{l - 1}$$$. So just get RMQ for l to r and check if $$$f_{l - 1}$$$ + rmq >= 0. if it is then answer yes else no. PS: dip is $$$rightf_{r + 1} - rmq(of rightf)$$$. Since we are dealing with dip in right to left direction, we will use this array to build segtree.

»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

We've sent email to top 20 teams. Please check your inbox.