Ashishgup's blog

Indian ICPC Regionals
By Ashishgup, history, 6 years ago, In English

Creating this blog for discussion of problems/solutions from Indian ICPC Regionals

Onsite Contest Standings:

Online Replay Contests:

There is also the whole issue with test cases in the regionals so far:

Gwalior-Pune:

  • "Flipping Polygons" had wrong TCs which affected a few teams, with 3 of them getting AC later. Converting WA -> AC after contest is alright, but the time wasted by teams in trying to correct their codes could have been utilized in solving a different question.
  • "Three Strings" had really weak TCs, considering that solutions taking max prefix and max suffix only get AC as well. (Breaking test case: 1 abc cde bcde)

Kolkata-Kanpur:

  • "Chef and Alien Invasion" again had wrong TCs, and teams were affected, with even the teams qualifying for World Finals changing places. ACs were converted to WAs after the contest (although that doesn't affect the ranks), not to mention that it was announced that the problemset for the regional was made 1 day before the contest, which is not what is expected of an ICPC regional.
  • Vote: I like it
  • +258
  • Vote: I do not like it

Comments Comments (142)
| Write comment?
»
6 years ago, # |
  Vote: I like it +67 Vote: I do not like it

Kolkata-Kanpur had an issue with the test data of READCOST. I don't know how many other teams were affected, but we lost around 20 mins before solutions were rejudged and our previously TLed solution was accepted.

Also the problem SNOWMAN is simply Fibonacci nim, which is extremely lazy problemsetting. For someone who happened to know of it beforehand, it would literally take 2 mins to solve versus someone who would have to analyze the game.

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

    can you please share your code for the READCOST Problem? The editorials are not available and the solutions from the replay are also not public.

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

      We solved it onsite so I don't have the code, but you can see accepted solutions of the practice problem. I can also share the approach here. The problem is to calculate for x, n ≤ 1000 and m ≤ 1015. The idea is to find the smallest k for which , for each i starting at 1. You can do this mathematically or with binary search. Accumulate sums in a variable and keep count of how many terms were added. Repeat until m terms are done. You will have to do the above procedure O(n) times.

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

      This can be solved by brute force by interchangin n and m.

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

      The series to be summed is simply an AP with some correction factor. It is easy to find a pattern in the correction factor series. Subtract the sum of correction factor series from the sum of AP to get the answer. I used Python because with this algorithm, long long will overflow in C++.

      Python solution for READCOST:

      from math import gcd

def sap(n, a, d):
    return n*(2*a + (n-1) * d)//2

while True:
    n, m, x = map(int, input().split())
    if m is 0:
        break
    c = gcd(n, m)      # Number of cycles in correction series
    l = m//c           # Length of each cycle
    ans = (sap(m, x, n) - c * sap(l, x % c, c))//m
    print(ans)
      → Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +20 Vote: I do not like it

    VASTLIFE was also a copy of a Google Foo Bar Challenge. So yeah. Very lazy problem setting.

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

      Lol are Kolkata-Kanpur setters more lazy than me? Since nobody has pointed it out last year, here it goes.

      Club of Riders was copy of BearCavalry. I was so surprised to see a problem at ICPC Regional which I solved few weeks back before that regional.

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

    https://codeforces.net/blog/entry/64035

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

    We were also affected similarly. We made 4 submissions and wasted nearly 30 mins before seeing our first submission getting AC. I complained but to no avail.

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

IIIT Pune shouldn't be a host for ICPC.

They don't even have their own campus — they just seemed to have leased two buildings in some other college. They provided bare minimum food, hardly gave a fuck about the participants' needs (they didn't seem to have a working printer at times during the contest, Codechef distributed their t-shirts AFTER the prize distribution ended when half of the teams had already left!) and ffs the campus was in the middle of nowhere. Getting an Uber/Ola was a pain in the ass and we had to scamper to make it to the airport.

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

it was announced that the problemset for the regional was made 1 day before the contest

Why did they announce it? :D

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

So if they are changing the ranklist after the contest ended, are the prizes given to the wrong teams?

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

    Yes, the official results which were declared are different from the current results.

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

The problems were prepared on the night before the contest for gwalior-pune regionals. Anup (Lead at Codechef) himself announced that during the prize distribution ceremony.

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

    Yes. He said that in Kanpur regionals as well.

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

    I have also been to Amritapuri regionals, and the problemset there was really good (i.e., testing and required good skills). The gwalior problemset was really not good. Such a thing is not acceptable for ACM-ICPC, and CC must take care of it in future...

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

Bhai tera wf nhi hua kya (I m from Codechef)

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

    Then you might be knowing it already if you are from codechef, don't you?

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

      that's what I would expect from pipmri chinchwad

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

Can anyone explain the solution of GRAPHAND question from kharagpur regional contest ?? link : https://www.codechef.com/KGP18ROL/problems/GRAPHAND

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

    The idea is to consider acceptable AND values of the final path, which must be  ≥ K. For a particular AND value x, you can find the shortest path in the graph with Dijkstra considering only edges that have v as "supermask" of x (v & x = x). This is a candidate answer.

    But you don't need to repeat this for all x ≥ K. There will be only a few "minimal" x for which you must find the shortest path, because if a x is acceptable then all supermasks of x will also be acceptable. You can find these minimal x by flipping exactly one 0 in K to 1 and 0-ing all lower bits. x = K must also be checked. As an example, for K = 001101, you must try x = {100000, 010000, 001110, 001101}. So you would have to run Dijkstra ~30 times to find the overall answer.

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

      Basically fixing the value "x" (>=k) will ensure that the final "and" value of path b/w source and destination will be >=k right ? But how can we ensure that only those minimal "x" values are needed to get the minimum path cost (if exists) ? Can you give some explanation on this ?? Everything except this is clear .Thank you :)

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

        I should have explained more about minimal x probably. So we want to choose some x such that x ≥ K, let's call these good. Running Dijkstra on a graph with only those edges whose v are supermasks of a good x will result in a shortest path with AND value also a supermask of the good x used. Since the value of a supermask of x ≥  value of x, the shortest path obtained is a possible answer.

        Now the edges that are traversed with a particular x, will also be considered for all submasks of that x. If x' is a submask of x and both x and x' are good, it is pointless to run Dijkstra once for each. Just using x' will take into account all paths you would get with x.

        So the smart thing to do is to find certain minimal good x, so that running Disjktra with each will cover all possible good x. I hope this explains why only using the minimal values work. A minimal good x will be good but not have any good submask.

        Let me also explain why the minimal values are what they are.
        Let's try to find the minimal good x among all good x. Of course K itself is a minimal good x. If you flip any bit in K, it is no longer good. Is K + 1 a minimal good x? For K = 01010 say, K + 1 gives 01011, which is not minimal since K is a submask. But the next value 01100 is indeed a minimal good x. The next 3 values 01101, 01110, 01111 are not minimal. But when the 1s flip again, 10000 forms a minimal good x. It should be clear now why the minimal good x can be obtained how I've described in my previous answer.

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

          Forgive me if I'm being dumb, but I wish to clarify if my understanding is correct.

          If V&X = X, then V is a supermask of X, and X is a submask of V?

          So K = 10, in your example. So we need to find numbers in the range [10, 1000000000] (lets call them P) such that P has no submasks in the range [10, P-1]. If that is possible, then we can claim that P is a minimal good x.

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

            Yes, you are correct on both counts.

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

Based on my observations, ranting about Indian regionals is the easiest way to farm contribution xD

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

    And it has been a monopoly so far xD

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

    Also Indian regionals are the easiest to get to the WF as well.! :D

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

      [Deleted]

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

        I didn't mock anybody. I just simply stated out a fact.

        Indian people do not have much opportunities and resources as many western countries.

        Indian people don't have the internet? India has the cheapest 4G in the world right now. They don't have Codeforces or Codechef or past year world finalists in their college? And the top performing countries in the WF's are Russia, China etc who are not western

        India was a colony for around 300 years and all of its resources were exploited.

        Did britishers take the brains of the people who weren't born in 1947 with them as well?

        Good luck with the learning.

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

    yes its true ,not only for indians but for many in the community, because system for calculating contribution is weird i think so,becos how the hell? Ashishgup has contributed more than tourist,Petr,rng_58,neal,etc for the community? in my opinion ,contribution should only be calculated by any editorial or educative discussing comment ....

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

this guy can literally do anything for contribution

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

    Some fake Indian accounts that don't admit their fault

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

LOL, you were not even close to qualifying for world finals, just accept it and focus on improving rather than crying like a baby/bitch every time you don't do well.

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

    I'm not crying about anything, and I never said anything about being eligible to qualify for World Finals. I'm just posting a discussion blog and stating what happened.

    PS: I know I'm not close to qualifying for World Finals.

    For those of you who think I'm making this blog for contribution, I'm not. I just made one because nobody else did in the past 10 days.

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

      We all know.

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

      So, you are doing this just for contribution? :P

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

      If you didn't want contribution, one of your your team mates could have written the same blog.

      PS : You wrote the contribution thing in reply to my comment not in reply to Swistakk's to avoid downvotes.

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

        Lol, I don't control the actions of my teammates, or anyone else in India.

        As for Swistakk, his and kr_abhinav's comments are light-hearted and funny, and not offensive, as opposed to yours.

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

          "For those of you who think I'm making this blog for contribution, I'm not. I'm already Rank 3rd in Contribution, and Rank 2 is too far away. I just made one because nobody else did in the past 10 days."

          This is the comment I am talking about, I didn't even mention contribution in my first comment, only Swistakk did. So it was a reply for him. :P

          Anyways, you know you are a greedy bitch. You only have the sympathy of people, you don't have their respect.

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

            Damn! That last line.

            He got sympathy from winners + respect from loosers.

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

              Respect from losers? But you don't respect him...

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

                but you do.Thats why anyway,i have sympathy for him and now you too.

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

                  You are not a winner if you don't even compete...

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

Hyouka is the gayest anime out there.

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

Sir, I really don't get the point of making a "post" specifically for raising up concerns over wrong test data of contests being organised by CODECHEF on codeforces. What do you exactly want ? The CC team arent going to be reading your blog posts as quickly as they might read one on Discuss. I dont believe you want to discuss solutions , you only want contribution.

MikeMirzayanov,How can people be #3 on the contributers list by writing DOGSHIT posts which are just Ranting codechef that too twice.

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

    I guess we both can agree that ashish is a karmawhore.

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

      AIex_2oo8 Putting people down does not make you a strong person, you are just another bully, a coward who is just jealous of him. I don't know why people like you exist. Why do people like you enjoy judging and putting down or belittling other people? STFU loser, and stop being jealous of others.

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

    Codechef's discuss is so awful that it's more likely that the CC admins will answer on CF

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

Be a good guy like me. I could grab +127 upvotes(probably more if it was from my original account) with my blog post for my original account.

Don't go for contribution, Go for Rating. Boom!!!!!

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

    So you're not the regional director for Kharagpur after all!

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

Can anyone explain whether this idea about the BUCKETWA problem of Kolkata-Kanpur regionals is correct or had anyone this idea? It seems like the optimum path is like refraction of light from vacuum to a medium of refractive index -k, like a metamaterial. This follows from Fermat's principle of least time. Thus we can say sin(theta1)/sin(theta2)=k and dH*cot(theta1)+dL*cot(theta2)=dR. Solving these simultaneously,the answer is dH*cosec(theta1)+dL*cosec(theta2). Because these equations are difficult to solve, we generate values for sin(theta1) using a loop, and detect theta1 and theta2 for which, the two equations hold.This should work, but my program isn't printing anything. Link: https://www.codechef.com/KOL18ROL/problems/BUCKETWA Sorry for bad typing, I am relatively new to all these, and I am commenting for the first time

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

    What is this refraction stuff?The problem is this.

    Now you have to go from the house to the river and then to the land. So basically you have to cover some distance with empty bucket(k times faster) and the remaining distance with water(k times slower). You will obviously fill the water from the river at some point between the lines dh and dl. So the path will be go from house to this point and then from this point to the land.

    Since there is a factor of k binary search the most optimal point at which you should fill the bucket. Once you get the point calculate the distance appropriately.

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

      Not sure if binary search can be used because the function is not always decreasing. Can you expand on your conditions for binary search?

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

        The function is strictly convex (time taken decreases, reaches a minimum and then increases), so you can use ternary search on it.

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

          Can you prove the function will be convex? I was getting an equation of degree 4 which I couldn't reduce.

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

            Suppose the distance at which you touch the river is at a vertical distance x from the house, as per the above picture.
            Now, the function to minimise would be
            . Now, the first term is an increasing function, and the second is a decreasing function. Initially, the rate of decreasing function dominates over the rate of increasing function (see the trend of differential of both terms), and is eventually overtaken, thereby providing a convex function.
            However, I think it's highly intuitive to imagine a point moving across the border of river, causing the function to decrease then increase and thus I did not prove convexity during solving, hence the weak explanation, sorry about that :(

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

              Rearrange a bit to get

              We only care about the roots in [0, dr] . f(0) < 0, f(dr) > 0, and f'(x) is obviously monotonically increasing from the second equation. This implies that f(x) was a convex function as f'(x) will have exactly one root in [0, dr]

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

                Yeah, we also solved it by intuition based on the number of solves. This prove doesn't seem enough to me. We get a cubic derivative and it can also have the same property (f'(0) < 0, f'(dr) > 0) and have  > 1 root.

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

                  Yes, it can. However, if it is monotonic is [0, dr] then it must have exactly one root in that region. Not that we do not care about the roots outside the region

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

      What is this refraction stuff?

      Maybe you should not be so dismissive? The problem is actually equivalent to refraction of light where the relative refractive index of the two media is k.

      rupayan if you provide your solution it will be easier to figure out the problem. Ternary search is a possible solution as mentioned by Beebabalooo.

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

    The question asks for minimising the time and not the distance so this approach cannot be used.

    My approach involved ternary searching along the river to find the optimal point from where minimum time will be taken.

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

      The question asks for minimising the time and not the distance so this approach cannot be used.

      Is there some kind of physics where minimizing the distance does not minimize the time?

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

        The factor of K will come into account while minimising the distance as speed will decrease after touching the river.

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

    I have used binary search and Snell's law to solve the problem. Basically, I take a distance from the base and find the corresponding sin(i) and sin(r). Then, I compare sin(i)/sin(r) to k and do a binary search as it is a monotonous function.

    https://www.codechef.com/viewsolution/22050337

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

1,2,3,4 Ashishgup is karmawhore.

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

How is it possible that teams that topped one regional were BOTH not even in top 5 of the other regional? Were the harder problems from Kolkata regional more hard than the harder problems from Pune Regional?

The best regional this year will be Amritapuri. They have taken the top teams without any best from the college bullshit criteria. Also the problemset will be more nice because last year they had akashdeep and GlebsHP as the problem setter.And if I remember correctly, last year, nobody solved any of the problems that were set by GlebsHP.

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

Just searched through the net and collected problems for the contest Typical 'Indians'

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

    SORRY.

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

      Typical Indians are the ones who copy problem ideas from other sites (like old Topcoder Contests and CF Contests) and use them as their own (while setting wrong test cases sometimes)in Indian Regionals and making money for the same.

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

SORRY.

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

    Why are this all haters are ignoring the fact that it is true CC has rrally messed up experience of the candidates. Team ToLazyToPropagate was 2nd in kolkata regional but after changing AC to WA they are 3rd and might miss the chance to WF. If the judgement was right at that time they could have performed well to maintain their rank. Instead of saying he just wants contribution say CC gave him chance to do so and no one else had balls to put this up so he did. There is nothing wrong in it.

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

      SORRY.

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

        That wouldn't change the fact that team were affected. Pehle original account se comment kar then we will talk

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

          SORRY.

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

            A bully can never be a friend. Didn't know people can go to such extent that they are creating fake accounts just to bully someone. The only loser here is YOU.

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

T-Gay

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

Guys, seriously, what is going on in these comments? I see a lot of unfair disrespect towards Ashishgup. Why do you use such words as "idiot" :|? RejectByLifeCompanyGirls the_pacifier1 AshishChup AIex_2oo8 and maybe some other guys as well — who do you think you are? Get your behaviour straight. By the way, saying things like "This comment should be taken as funny/light-hearted." or "No offence, but (...)" or "it's a prank bro" doesn't invalidate what you say and doesn't justify you offending other people or acting in any other inappropriate way.

My previous comment was to be treated humorously, but of course there is substantial difference between what I wrote and following comments using words like idiot or whore. All people that complain seriously that someone just wants contribution or whatever is a huge cancer and adding unjustified offending to this is next level. If someone gets contribution it means that community appreciates his content /eot

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

    I think codeforces should start banning accounts like quora does.

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

    Thanks for opening my eyes Swisknife.

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

    We are sorry for our inappropriate behaviour, Swischeese

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

Hi, I participated in the Gwalior regionals (for schools). I couldn't figure out the last two problems, Flipping polygons and polygon and Strings. Could someone elaborate the solutions?

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

    Polygon and strings: It is given that the convex hull of the given set of points is the set of points itself. Also no 3 points are in a line and no 2 points have same X or Y coordinate. One more important constraint is that in the solution no line segment should intersect with other line segment. Imagine you sorted the points clockwise/counter clockwise ( does not really matter which ) . We know that our solution has to include all the given points since query length is N-1.

    Now imagine you have taken the 1st point in the answer to be the jth point in the sorted order. what can be the possibilities for the 2nd point? If you take the Kth point in sorted order and there are >0 number of points between jth to kth point AND >0 points in between kth to jth point ( points array is circular so there are two intervals between jth and kth points ), then at some point in the future you will have to intersect the segment j to k because you must cover all points.

    What this tells us is that after taking jth point the only possibilities for the next point are j+1 or j-1. Which tells us that at any instant, the set of "taken" points forms a contiguous segment in the sorted order. If the segment L to R is taken then the next point can be either R+1 or L-1 and nothing else. However,information which one of L and R was placed in previous step is also needed. this leads us to a simple DP solution bool dp[which][L][R] where "which" tells us if L was placed in previous step or R. dp array tells us whether it is possible to proceed with these parameters or not. To print the actual solution just store the optimal next moves for each state. Total time complexity is n*n*m, given constraint on n*m makes this solution optimal.

    Flipping polygons: I do not know why the setter has given Fibonacci numbers in the problem. Interpret updates in this manner: instead of rotation points, let us rotate the y axis. So the y axis will have a direction, and a counter indication which point (or side in case when N is even) it is passing through. So rotate polygons in L to R by X rotations means basically adding X to all elements in L to R. However if some polygon is flipped X rotations mean subtracting X from it counter instead of adding.Fortunately, this can be done using a single segment tree with some smart lazy propagation. I recommend you to look at the AC codes on codechef in the replay contest ( look for the ones which have a single seg-tree). The code is quite simple to understand.

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

      I dont think your solution for flipping polygons is correct. when u invert, not only do u change the state to subtraction, but also shift the y axis rotation by a certain amount. This shifting information is based on the number of sides of the polygon. This is why i think the fibonacci numbers was given because, upto 1e9 , there are only around 43 fibonacci numbers, so in our segtree we can store the information regarding all different types of polygon.

      thanku for the solution of polygon and strings though :D

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

        Well i think my solution for flipping polygons is correct, and i am just not able to explain it properly..that is my bad..take a look at this code : https://www.codechef.com/viewsolution/22006349

        You can also checkout Praran's code which does the same thing with 43 segments trees but his solution does not really required 43 seg-trees. The same thing can be done in a single seg-tree.

        Edit: i think i understand what you are saying now, however simply subtracting if flipped is still correct. We do not have to shift anything. We can handle that during the query.

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

Can someone please explain their solution for this expectation based problem from the Kolkata-Kanpur regionals: TILEBAG ?

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

    A tile with number S can be formed: This means that atleast one of X or Y is of the form S / (2^k).

    X and Y are not divisible by each other: This (along with the previous statement) means that exactly one of X or Y can lead to S.

    Assume X can lead to S in 2^k moves. Expected number of turns before you get an X is 1 / p. So expected number of turns to get 2^k X's is 2^k / p.

    Do a similar analysis for Y (replace p by 1 — p).

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

      Sorry, it is not clear to me still.

      This means that atleast one of X or Y is of the form S / (2^k): I didn't get it.

      This means that exactly one of X or Y can lead to S.: But what if say X = 3, Y = 5, S = 15.

      A tile with number S can be formed: Does this mean that X = 3, Y = 5, S = 8 is an invalid case since the tile may or may not be formed ?

      Please elaborate a little.

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

        So the only numbers you can encounter by getting tiles of type X are: X, 2X, 4X, ....(2^k1)X, ....

        Similarly due to Y, you can get Y, 2Y, 4Y, .... (2^k2)Y, ....

        Now because the solution exists (**A tile with number S can be formed**), S must be of the form (2^k1)X or (2^k2)Y.

        But what if say X = 3, Y = 5, S = 15.: This is in invalid case since you can never reach S using those 2 tiles. Even your other example in invalid for the same reason.

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

          Thanks a lot. I seem to have misunderstood the problem slightly. But your comment was very helpful. :)

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

Rather than showing hate, can't we discuss the problems?

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

How to solve Yet another shortest path problem from Kanpur regionals YASPP

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

    Use 0-1 BFS while maintaining the set of colors of previous edges(corresponding to only shortest path) for each node. Code

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

      So this code is wrong as pointed out by sauravray2587. Here is the test case provided by him for which the code fails.
      5 5
      1 2 1
      1 3 2
      2 4 1
      3 4 2
      4 5 2
      1 5
      Answer should be 0 but the code outputs 1.

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

        This wrong code passes on codechef which means another case of weak test cases in regional.

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

    Another approach is as follows: Modify the given graph as follows. For each node present in the graph, make some copies of the node equal to the number of distinct colors attached to it. Let the copies of the node (say u) be numbered v1, v2, ... , vk. Connect these nodes to u with weight 1. These edges represent changing of color. Now, for an edge some color, connect their corresponding copies with weight 0. Now, run any shortest path algorithm from S to T and let it be L. So, ans = (L — 2) / 2. Complexity: O(n + m) if you use 0-1 BFS, or O((n + m) * log(n + m)) if you use dijkstra. See my code: https://www.codechef.com/viewsolution/22043601.

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

Can anybody tell me how to solve Subset Sums Revisited SUBSUMX from icpc Kharagpur regionals? Also if somebody could explain me how to extend my idea that I have explained below, it would be of great help. It happens that the same solution was explained after the contest in regional site but that person too explained only upto the point I had already solved. So it was of not much help for me :(

MY SOLUTION
We can easily construct an array x[64] from a[n] given such that x[i] = frequency of ith bit 'on' in B[0 ... n].
For example if A[] = {1,1,2} then B = {2,2,4} hence x[1] = 2, x[2] = 1 and every other x[i] = 0.
DP State : dp[i][j] = j number of 2i s required.
Recurrence :
dp[i][j] = (  ×  dp[i-1][2  × (j-m)]).
Base Case dp[i][0] = 1
EXPLANATION OF MY DP : dp[i][j] = we want j number of 2i s. So we take m number of 2i s from x[i] in ways and the rest (j-m) 2i are taken from 2(i - 1) s. Now to obtain (j-m) 2i s we require 2  ×  (j-m) 2(i - 1) s which we can obtain in dp[i-1][2  ×  (j-m)] ways. We do this for all m from 0 ... j and sum them to obtain the final answer.
PROBLEM IN MY DP
My dp works well if k has only one bit set in its binary representation and so I could just call dp[log2 k][1] but I don't know how to generalize this idea for any k. Can you please help me?

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

Can anyone please explain their solution to GAMOFNUM from Gwalior-Pune regionals?

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

    First observation which is really important here is that for a number Ai in the array, say it's prime factorization is Ai = p1 * p2 * .. * pk. Then, you can treat each prime as a different pile and solve. You can consider the moves as choosing a prime factor of Ai and replacing it with some number x which can in turn be decomposed into more piles. Now, basically you have to calculate the grundy of a prime number. Another observation is that the grundy of the kth prime number is k. Why? This is because from a prime p, you can go to any prime less than p and 1 itself. So when you do the mex operation, grundy comes out to be k. See the code: https://www.codechef.com/viewsolution/22010093.

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

      Thanks for the explanation. But I have a doubt, let's say Ai = 21, so we are considering this as a nim game with piles (7,3). If I choose p=7,i=4 I end up with the state (2,2,3) and not with (4,3) as it should happen in a nim game. So, how can we treat each prime as a different pile of nim?

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

        Yes, you would end up with the state (2,2,3) and Grundy of its state is g[(2,2,3)] = g[2]^g[2]^g[3].

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

Another issue was that there were lot's of announcements for the problems that were not reflected in the printed statements (Almost every problem had an announcement). Thankfully, they weren't mid contest, but was still annoying.

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

Can someone explain their solution to Chef and Alien Invasion? ALIENCOW

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

    We just need the areas of the closed regions formed by the fences. (The answer then is just the sum of squares of areas over the total area.) Imagine that all of the rectangles' edges are extended both ways — the field now looks like a grid of kit-kat pieces. Any regions formed by the fences must be a disjoint union of these small pieces of land, which are only at most O(k^2). So we can use a DSU / perform a DFS to join adjacent pieces of land that don't have a fence between them.

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

      Thanks. That makes sense. I'm guessing each piece of land would represent a node and each free side would correspond to an edge in the graph. What would be an efficient way to build this graph? Any hints? Edit: Nvm. Got it.

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

How to solve Palindromic Paths (PALPATH) from Amritapuri regionals?

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

    Consider any valid walk. The ith edge on the walk and the ith edge from the end have the same character on them. So try building the walk from both directions. Define dist[a][b] as sum of lengths of the shortest walks from s to a and from t to b such that the concatenation of the (ordered) edge set of these walks is a palindrome. Then min(dist[x][x]) gives us the shortest even length walk. Odd length walks can be considered by enumerating every edge in the graph.

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

We were the only team significantly affected at the Gwalior-Pune regionals. We finished 7th with 9 problems solved but our rank increased to 5 after the contest since the test data for NGONS was wrong. We would have had at least half an hour to solve POLYSTR (which is similar to a problem from Indiahacks 2017) and managed to come second, thus qualifying for world finals.

We spoke to Anup in person but he smiled and said nothing can be done about it. We also emailed the regional directors but to no avail. Since we're the only team affected, everybody seems to be ignoring the issue. It's our last attempt for ICPC and we're potentially missing out on qualifying because of someone else's mistake. Isn't Codechef's credibility in question if they can do whatever they want without being answerable to anyone?

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

    Indian Regionals are a joke.

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

    As much as I agree with you, unfortunately ICPC rules state that "In consultation with the judges, the Regional Contest Director determines the winners of the regional contest. The regional contest director and judges are empowered to adjust for or adjudicate unforeseen events and conditions. Their decisions are final."

    It's really sad we can't do anything.

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

      Perhaps we can appeal to the regional directors to ensure necessary problem quality rather than leave it to CodeChef to prepare the night before the contest?

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

        What makes you think RCDs will be responsible?

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

          Since RCDs are the ones who are all-powerful here, that seems to be the only course of action available.

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

            We emailed the RCDs, they dismissed the issue immediately. I don't think appealing is a thing in India lol.

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

              Not that it would matter, but you have to email to [email protected] for an official appeal. (within 1 day, it's too late now)

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

                Yeah we did at that time, but no proper response. We were told about the error late as well. But yeah, nothing can be done now. Thanks though. :)

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

How to solve SQRTRI of Kharagpur regional.

Problem Link : https://www.codechef.com/KGP18ROL/problems/SQRTRI

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

    Just pure mathematics. Find the intersection of lines in all 4 directions and check the coordinates of that point to the boundary condition of the square.

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

Can anyone tell me how to solve ALIENINV from Amritapuri regionals. I have been struggling with this for days.

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

How to solve INFDIV from KGP onsite. Editorial/link to discussion thread is also fine.

→ Reply