[gcj] Manhatten distance problem
My code solves the samples perfectly and i also believe its true for all cases
but still i got a WA in my submission, can anyone see an issue with this code?
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Scanner;
public class Solution {
public static void main(String[] args) {
Scanner scanner = new Scanner(new BufferedReader(new
InputStreamReader(
System.in)));
int testCasesNum = scanner.nextInt();
for (int i = 1; i <= testCasesNum; i++) {
int p = scanner.nextInt();
int q = scanner.nextInt();
Integer[][] sortedArrayX = new Integer[p*2][];
Integer[][] sortedArrayY = new Integer[p*2][];
for (int j = 0; j < p; j++){
int xj = scanner.nextInt();
int yj = scanner.nextInt();
char dj = scanner.next().trim().charAt(0);
switch (dj){
case 'N':
sortedArrayX[j*2] = new
Integer[] {0, 0};
sortedArrayX[j*2 + 1] = new
Integer[] {q , 1};
sortedArrayY[j*2] = new
Integer[] {yj + 1, 0};
sortedArrayY[j*2 + 1] = new
Integer[] {q , 1};
break;
case 'S':
sortedArrayX[j*2] = new
Integer[] {0, 0};
sortedArrayX[j*2 + 1] = new
Integer[] {q , 1};
sortedArrayY[j*2] = new
Integer[] {0, 0};
sortedArrayY[j*2 + 1] = new
Integer[] {yj - 1 , 1};
break;
case 'E':
sortedArrayX[j*2] = new
Integer[] {xj + 1, 0};
sortedArrayX[j*2 + 1] = new
Integer[] {q , 1};
sortedArrayY[j*2] = new
Integer[] {0, 0};
sortedArrayY[j*2 + 1] = new
Integer[] {q , 1};
break;
case 'W':
sortedArrayX[j*2] = new
Integer[] {0, 0};
sortedArrayX[j*2 + 1] = new
Integer[] {xj - 1 , 1};
sortedArrayY[j*2] = new
Integer[] {0, 0};
sortedArrayY[j*2 + 1] = new
Integer[] {q , 1};
break;
}
}
Arrays.sort(sortedArrayX, new Comparator() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
int res = o1[0] - o2[0];
if (res == 0)
res = o1[1] - o2[1];
return res;
}
});
Arrays.sort(sortedArrayY, new Comparator() {
@Override
public int compare(Integer[] o1, Integer[] o2) {
int res = o1[0] - o2[0];
if (res == 0)
res = o1[1] - o2[1];
return res;
}
});
int maxIntersectionsX = 0;
int xStart = 0, xEnd;
int currentIntersectionsX = 0;
for (int j = 0; j < p; j++){
if (sortedArrayX[j][1] == 0){
currentIntersectionsX++;
if (currentIntersectionsX >
maxIntersectionsX){
xStart = sortedArrayX[j][0];
maxIntersectionsX =
currentIntersectionsX;
}
}
if (sortedArrayX[j][1] == 1){
if (currentIntersectionsX ==
maxIntersectionsX){
Re: [gcj] Question about Code Jam 2019 Round 1B second problem - Draupnir
Quick fix of my typos: Day 64: R1 * 2^64 ≡ 0 (mod 2^63) 2^64 is a multiple of 2^63 so the remainder MUST be 0 OR R1 * 2^(63 + 1) ≡ 0 (mod 2^63) 2^64 is NOT less than 2^63 and therefore a multiple 2^63 so the remainder STILL MUST be 0. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/97b516e6-316b-4642-b3b2-2caa5ed1c0b9%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Question about Code Jam 2019 Round 1B second problem - Draupnir
Hello, >> "But, for example after 68 days, it will contribute R1*2^5 rings to the total rings, right?" That's wrong! It still does contribute 0. The number of R1 contributes 0 total for ANY day larger then 62. Why is that? : Day 63:R1 * 2^63 ≡ 0 (mod 2^63)2^63 is a multiple of 2^63 so the remainder MUST be 0 Day 64:R1 * 2^64 ≡ 0 (mod 2^63)2^63 is a multiple of 2^63 so the remainder MUST be 0 R1 * 2^(63 + 1) ≡ 0 (mod 2^63)2^64 is less than 2^63 and therefore a multiple 2^63 so the remainder STILL MUST be 0. So when querying day 324, you can ONLY identify R(6) at day 0. Am Di., 30. Apr. 2019 um 17:35 Uhr schrieb Ramesh Kumar < rameshkuma...@gmail.com>: > On Tuesday, April 30, 2019 at 8:18:56 PM UTC+5:30, /dev/joe wrote: > > The 1-day rings duplicate every day, so their contribution to the sum > moves one bit left in the binary representation every day. After 63 days, > since we only get the value mod 2^63, the 1-day rings make no contribution > to the value you get. > > > > > > On Tue, Apr 30, 2019 at 10:05 AM Ramesh Kumar > wrote: > > Hi All, > > > > > > > > It was mentioned we can use two chances for Code Jam 2019 Round 1B > second problem - Draupnir. But I think we can use only one number 324 > which is sufficient and find the solution. But, I am unable to get the > accepted answer. Is there anything wrong to use only 324 number to find all > the required six numbers? Please help me to understand. > > > > > > > > -- > > > > You received this message because you are subscribed to the Google > Groups "Google Code Jam" group. > > > > To unsubscribe from this group and stop receiving emails from it, send > an email to googl...@googlegroups.com. > > > > To post to this group, send email to googl...@googlegroups.com. > > > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/10442015-c57d-4edd-9ac4-dce29cd20eb2%40googlegroups.com > . > > > > For more options, visit https://groups.google.com/d/optout. > > But, for example after 68 days, it will contribute R1*2^5 rings to the > total rings, right? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/c27fe3f0-935e-4ce9-bdcf-b3f31fb422f9%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAEWn8ogz54D5zbosjyk0zZvhiCkZbUT4N5z5d6F8Zh-Ew7hoZQ%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Question about Code Jam 2019 Round 1B second problem - Draupnir
On Tuesday, April 30, 2019 at 8:18:56 PM UTC+5:30, /dev/joe wrote: > The 1-day rings duplicate every day, so their contribution to the sum moves > one bit left in the binary representation every day. After 63 days, since we > only get the value mod 2^63, the 1-day rings make no contribution to the > value you get. > > > On Tue, Apr 30, 2019 at 10:05 AM Ramesh Kumar wrote: > Hi All, > > > > It was mentioned we can use two chances for Code Jam 2019 Round 1B second > problem - Draupnir. But I think we can use only one number 324 which is > sufficient and find the solution. But, I am unable to get the accepted > answer. Is there anything wrong to use only 324 number to find all the > required six numbers? Please help me to understand. > > > > -- > > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > > To unsubscribe from this group and stop receiving emails from it, send an > email to googl...@googlegroups.com. > > To post to this group, send email to googl...@googlegroups.com. > > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/10442015-c57d-4edd-9ac4-dce29cd20eb2%40googlegroups.com. > > For more options, visit https://groups.google.com/d/optout. But, for example after 68 days, it will contribute R1*2^5 rings to the total rings, right? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/c27fe3f0-935e-4ce9-bdcf-b3f31fb422f9%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Is the scoring rule strange？
During the contest, you can't see whether you solved hidden inputs correctly or not. The score you see on the scoreboard, which I'll call your "apparent score," is what your score would be if you solved every possible hidden input correctly. If you make an additional attempt, your apparent score can only get worse -- but your real score might get better. For example, if you first submit O(N^2) code for a problem with a hidden input of size 10^6, then later submit O(N) code, your apparent score goes down (because your submission is now later), but your actual score could go up. Does that help? Bartholomew On Tue, Apr 30, 2019 at 8:05 AM 姚炫容 wrote: > Once your attempt solve all the test set(visible and hidden), then any > additional attempt will lower your final score for penalty time, or even > for the score. > > Is it right? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/033b23a0-066c-43b2-8499-ac06b80872df%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAHaiWHOJ1GxHCF43D47ii-ZWZzxLp1MbhOti8KenZnLwGg5Crw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Question about Code Jam 2019 Round 1B second problem - Draupnir
The 1-day rings duplicate every day, so their contribution to the sum moves one bit left in the binary representation every day. After 63 days, since we only get the value mod 2^63, the 1-day rings make no contribution to the value you get. On Tue, Apr 30, 2019 at 10:05 AM Ramesh Kumar wrote: > Hi All, > > It was mentioned we can use two chances for Code Jam 2019 Round 1B second > problem - Draupnir. But I think we can use only one number 324 which is > sufficient and find the solution. But, I am unable to get the accepted > answer. Is there anything wrong to use only 324 number to find all the > required six numbers? Please help me to understand. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/10442015-c57d-4edd-9ac4-dce29cd20eb2%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhzho0Ld2mfWKTPs2ELsWKVOCG0KXO98_MMUkOiHm1NrzWw%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Python/pypy viability for future Codejam rounds
Also, no the problems are not specifically tested to be solvable in Python On Tue, 30 Apr 2019, 3:08 pm Luke Pebody, wrote: > I did Problem C large in Python > > On Tue, 30 Apr 2019, 3:05 pm Alex Wice, wrote: > >> In 2019 round 1B, problem C large doesn't seem to be possible with Pypy. >> If this is true, are the problems not specifically tested to be possible >> with Python? >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Google Code Jam" group. >> To unsubscribe from this group and stop receiving emails from it, send an >> email to google-code+unsubscr...@googlegroups.com. >> To post to this group, send email to google-code@googlegroups.com. >> To view this discussion on the web visit >> https://groups.google.com/d/msgid/google-code/720185a5-eddf-4977-8058-377f23c5574f%40googlegroups.com >> . >> For more options, visit https://groups.google.com/d/optout. >> > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-OVB1mZi-6XYb5RyqBfqJBBobMsGMn7wo6CNUnn3gG9Eg%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] Python/pypy viability for future Codejam rounds
I did Problem C large in Python On Tue, 30 Apr 2019, 3:05 pm Alex Wice, wrote: > In 2019 round 1B, problem C large doesn't seem to be possible with Pypy. > If this is true, are the problems not specifically tested to be possible > with Python? > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to google-code+unsubscr...@googlegroups.com. > To post to this group, send email to google-code@googlegroups.com. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/720185a5-eddf-4977-8058-377f23c5574f%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAECKw-PnM4qED7adeVmjWD_dm60yPbhTCVvnGp_WOK4p6B_R1w%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Python/pypy viability for future Codejam rounds
In 2019 round 1B, problem C large doesn't seem to be possible with Pypy. If this is true, are the problems not specifically tested to be possible with Python? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/720185a5-eddf-4977-8058-377f23c5574f%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Question about Code Jam 2019 Round 1B second problem - Draupnir
Hi All, It was mentioned we can use two chances for Code Jam 2019 Round 1B second problem - Draupnir. But I think we can use only one number 324 which is sufficient and find the solution. But, I am unable to get the accepted answer. Is there anything wrong to use only 324 number to find all the required six numbers? Please help me to understand. -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/10442015-c57d-4edd-9ac4-dce29cd20eb2%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
[gcj] Is the scoring rule strange？
Once your attempt solve all the test set(visible and hidden), then any additional attempt will lower your final score for penalty time, or even for the score. Is it right? -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to google-code+unsubscr...@googlegroups.com. To post to this group, send email to google-code@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/033b23a0-066c-43b2-8499-ac06b80872df%40googlegroups.com. For more options, visit https://groups.google.com/d/optout.
Re: [gcj] question about alien rhyme
Hey Lasse, you are getting it wrong. Its about different ACCENT-SUFFIXES. If you pair CODEJAM and NODEJAM, then the ACCCENT-SUFFIX is "ODEJAM", with the ACCENT on O. If you then pair MODEJAM and JAM, then the ACCCENT-SUFFIX is "JAM", with the ACCENT on J. So the two pairs WITH THEIR accents are: 1st pair2nd pair v v CODEJAMMODEJAM NODEJAMJAM ^ ^ ODEJAM and JAM are NOT THE SAME ACCENT-SUFFIXES, so they all the pairs are valid. CODEJAM and NODEJAM will rhime "ODEJAM", MODEJAM and JAM will rhime on "JAM". Thats 2 different ACCENT-SUFFIXES The ACCENT-SUFFIXES of different pairs must be different! But that does not mean that an accent-suffix can not be part of a LONGER accent-suffix. Am Sonntag, 28. April 2019 01:36:59 UTC+2 schrieb Lasse: > Hi, thank you for the example. In this case, I think we should make a pair > with "ODEJAM" and only this one. When the other word is matched to "JAM" with > "JAM", then the rule "and with none of the words in other pairs" is invalid. > > On Friday, April 26, 2019 at 12:30:07 PM UTC+2, DahliaSR wrote: > > Hi Lasse, > > > > > > another example to make this clear: > > > > > > Let the given words be: > > > > > > CODEJAM > > NODEJAM > > MODEJAM > > JAM > > > > > > The longest common suffix to of at least 2 words currently is "ODEJAM". > > So if you choose to put the accent on the "O" of that suffix, then you can > > pair 2 words with that suffix: > > - either CODEJAM <==> NODEJAM > > - or CODEJAM <==> MODEJAM > > - or MODEJAM <==> NODEJAM > > > > > > BUT you can ONLY pair EXACTLY TWO of them. > > Lets choose to pair CODEJAM <==> NODEJAM. > > If you now remove all the words ending on "ODEJAM" only JAM will be left in > > the list of words and can not be paired. > > > > > > But MODEJAM and JAM are pairable with the accent suffix "JAM", so MUST > > NEVER remove UNPAIRED words, just because they share > > a suffix with a pair you already build, because there is a chance, that one > > of the unpaired words shares a SHORTER suffix with another > > unpaired word. > > > > > > Am Do., 25. Apr. 2019 um 13:30 Uhr schrieb Lasse : > > On Wednesday, April 24, 2019 at 7:28:41 PM UTC+2, Xiongqi ZHANG wrote: > > > > > why would you ignore “scent”? even though “scent” > > > > > also has “cent” as a suffix, it can still be used to match other words > > > with different suffix, e.g “went” with rhyme “ent”. > > > > > > > > > > > > > > > > > > > > > > > > > On Wed, Apr 24, 2019 at 8:12 AM Lasse wrote: > > > > > Hi /dev/joe, > > > > > > > > > > > > > > > > > > > > thank you for the reply. I think our understanding is the same. With your > > > example, I first match rhyme "cent", which is shared by "cent" and > > > "recent", then "scent" must be ignored in the other matches, right? > > > > > > > > > > > > > > > > > > > > I did so and my submission is wrong, but when I retained "scent" and only > > > ignored "cent" and "recent", my code works with small dataset. > > > > > > > > > > > > > > > > > > > > Lasse > > > > > > > > > > > > > > > > > > > > On Tuesday, April 23, 2019 at 10:59:35 PM UTC+2, /dev/joe wrote: > > > > > > > > > > > The problem is about matching pairs of rhymes. Apparently we know that > > > > the poems in this alien language only ever use each rhyming-ending > > > > twice. Or maybe it's that we want to see how complex the rhyme scheme > > > > could be, in terms of different rhyming endings. Since rhymes are > > > > determined based on the location of an accent in the word, and we don't > > > > know where the accents go, you are placing the accents anywhere and > > > > trying to determine the maximum number of rhymes possible as a way of > > > > helping to decide whether these words are from a poem. Here's the > > > > relevant text from the problem: > > > > > > > > > > > > > > > > > > > > > > You believe that you can discard zero or more of these words, assign > > > > accented letters to the remaining words, and then arrange those words > > > > into pairs such that each word rhymes only with the other word in its > > > > pair, and with none of the words in other pairs. > > > > > > > > > > > > > > > > > > > > > > You want to know the largest number of words that can be arranged into > > > > pairs in this way. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > Example: Suppose you get the words bent, cent, dent, gent, lent, rent, > > > > recent, sent, scent, tent, and went. > > > > > > > > > > > > > > > > > > > > > > You can make two words rhyme with ending t, two with nt, two with ent, > > > > and two with cent. You will have three leftover words, but no more > > > > common endings which are not already used, so you can't make another > > > > pair even though the words have a common ending. > > > > > > > > > > > > > > > > > > > > > > > > > > > >
